A $5 \times 100$ table is divided into $500$ unit square cells, where $n$ of them are coloured black and the rest are coloured white. Two unit square cells are called adjacent if they share a common side. Each of the unit square cells has at most two adjacent black unit square cells. Find the largest possible value of $n$.
Problem
Source: 2019 Junior Balkan MO
Tags: combinatorics, Junior, Balkan, JBMO, 2019
22.06.2019 14:50
Isnt $5 \times 10 = 50$?
22.06.2019 14:51
GorgonMathDota wrote: Isnt $5 \times 10 = 50$? Yeah, it was a typo, thanks for pointing it out
22.06.2019 16:50
Just color the grid with the normal chessboard coloring. Check the black squares first. We want no $3$ of them to surround a white square. Note that in each $5 \cdot 2$ at least $1$ removal is needed. Note though that if a $5\cdot 2$ (not on the rightmost of the table) uses only $1$ removal the next one will use at least $3$. Hence for each column either the number of removals is $2$ or the sum of removals in this and the next are at least $4$ with the exception of the last one where $1$ works. Hence we need at least $99$ removals. The same stands for the white squares. In total we are left with at most $302$ squares. The construction should be the whole square sourrounding and the line $y=3$ minus the second rightmost and second leftmost square of that line.
22.06.2019 17:00
Actually assume we have $k$ $1$' (exluding the last one) s and $r$ $2$'s. Then we have at least $4k+2r+x_{last}$ removals. However it is $2k+r+1 \ge 50$. Hence the result. (there is no reason to use $3$ or more removals in a $2 \cdot 5$ column if we are not forced to by a previous $1$ removal since we could instead use $2$. )
22.06.2019 18:25
If we colour all the squares in the first and fifth row, as well as all the squares in the third row except for the second and second to last black, we get a configuration where $n = 302$, for which we can easily see that it satisfies the given conditions. Let's assume that $n_{MAX} \neq 302$, and let's prove that $n = 303$ doesn't work (if $n > 303$ works then we can remove a number of squares to get to $303$, so by contraposition, if $n = 303$ doesn't work, neither will $n > 303$). Let's define the power of a square as the number of adjacent black squares it has, and the power of the table as the sum of the powers of all the squares (and let us denote it by $M_{T}$). By the given conditions, we get that $M_{T} <= 500 * 2 = 1000$. However, if we have $303$ black squares on the table, the minimum value of $M_{T}$ will be achieved if the $4$ corner squares are black, as well as all the edge squares that aren't corner squares (as they have fewer adjacent squares than the rest, i.e. they will be adjacent to $2$ and $3$ squares, respectively), so we get that the power of the table (taking into consideration the squares that have the black squares as adjacent squares) $M_{T} \ge 2 * 4 + 3 * (2 * 98 + 2 * 3) + 4 * [303 - 4 - 2 * (98 + 3)] = 8 + 606 + 4 * 97 = 1002 > 1000 = M_{T}$, a contradiction. Therefore, the maximum value for $n$ is $302$.
23.06.2019 09:57
2019 JBMO #4 wrote: A $5 \times 100$ table is divided into $500$ unit square cells, where $n$ of them are coloured black and the rest are coloured white. Two unit square cells are called adjacent if they share a common side. Each of the unit square cells has at most two adjacent black unit square cells. Find the largest possible value of $n$. I claim the answer is $\boxed{302}.$ This can be seen with the construction: B B B B ... B B B B W W W...W W B B W B B ...B W B B W W W...W W B B B B B ... B B B Call the degree of unit cell the number of adjacent black squares to it. Clearly, the sum of the degrees of all $500$ squares $S$ is bounded by $S_{\max} = 2 \cdot 500 = 1000.$ Note that our construction gives $S_o = 998,$ as all squares but the two in red have degree two. (Those two black squares have degree one.) B B B B ... B B B B W W W...W W B B W B B ...B W B B W W W...W W B B B B B ... B B B Consider an arbitrary configuration satisfying the problem's conditions. We can classify each square in the grid as a two-square, a three-square, or a four-square. That is, if the square is a corner, it being black contributes two to our degree sum $S_c$ If it is a three-square, ie. it is on the side of the grid, then it contributes three to $S_c$ if it is black, and lastly, all nonboundary black squares, or four-squares, contribute four to $S_c.$ Then, for any configuration, we can write the equation: $$2a \hspace{0.1 cm} + \hspace{0.1 cm} 3b \hspace{0.1 cm} + \hspace{0.1 cm} 4c = S_c \leq S_{\max} = 1000, \hspace{0.7 cm}a \leq 4, b \leq 202, c \leq 294 , \hspace{0.5 cm} (*)$$where $a,b,c$ are the number of black two-squares, black three-squares, and black four-squares, respectively. We wish to maximize $a+b+c,$ the total number of black squares. Now observe that is never more optimal to increase $b$ if $a$ can still be increased. That is, if $a < a_{\max},$ and $b > 0,$ then it is never less optimal to decrease $b$ by one and increase $a$ by one. This will decrease the current value of $2a+3b+4c,$ while keeping $a+b+c$ constant. The same is true for $b$ and $c.$ Thus, clearly, the optimal way to maximize $a+b+c,$ while keeping $2a+3b+4c \leq S_{\max}$ is to (while $S \leq S_{\max},$) greedily maximize $a,$ then $b,$ then $c,$ in that order. (This is basically the same idea as the rearrangement inequality.) Thus, we see that the best we can do is $2\cdot 4 + 3 \cdot 202+4 \cdot 96 = 998 \leq 1000,$ and we can't increase $a,b,$ or $c$ without going over $S_{\max}.$ This shows that $a+b+c \leq 4 + 202 + 96 = 302,$ which we know is achievable. Thus, we have shown that $n=\boxed{302}$ is both optimal and achievable, and we are done.
23.06.2019 11:22
The idea of IMO 99 and EGMO 2019 works well here. See for example the above solution
14.05.2021 14:32
Position the table such that the longer sides are horizontal. We claim the answer is $302$. For a construction, color black all $206$ cells on the border along with the middle $96$ cells in the center row. This clearly works. Next we will assume, towards contradiction, that there exists a configuration with $303$ or more cells that satisfy the condition. We will count the sum, over all cells, of the number of black cells adjacent to each cell in two ways. On the one hand, since each cell is adjacent to at most $2$ black cells, this sum is at most $500\cdot 2 = 1000$. On the other hand, since there are are at least $303$ black cells, this sum is at least $4\cdot 2 + 202\cdot 3 + 97\cdot 4 = 1002$. This is clearly a contradiction, so there are at most $302$ black cells, as desired.
21.10.2023 12:33
The answer is $\boxed{302}$. In general for a $5*k$ board, the answer is $3k+2$. Construction Colour black all $2k+6$ cells on the border along with the middle $k-4$ cells in the center row. This clearly works. Bound Let there be $n$ cells that are colured black. We denote by $a, b, c$ the number of black cells that are adjacent to exactly $2, 3, 4$ cells respectively. So, $\boxed{a+b+c=n}$. Note that $\boxed{a \le4}$ since such a cell uses a corner of the grid and $\boxed{b\le2k+2}$ as such a cell is on the boundary of the grid. We will count the number of pairs ( cell $c$, black cell adjacent to $c$). On one hand, this number is atmost $2(\#\text{cells})$since each cell is adjacent to atmost 2 black cells. Counting from the perspective of black cells, we get: \begin{align*} \#\text{Pairs} &= 2a+3b+4c;\quad\ a\le 4,\ b\le 2k+2\\ &= 2a+3b+4(n-a-b)\\ &= 4n-2a-b\\ &\ge 4n-8-(2k+2)\\ &= 4n-2k-10\end{align*}This gives us the following inequality: \begin{align*} &4n-2k-10\le\#\text{Pairs}\le 2(\#\text{cells})\\ \implies &4n -2k-10\le 10k\\ \implies &n\le \frac{12k+10}{4} \text{ or } \boxed{n\le 3k+2}.\end{align*}. So, we are done. $\square$