In a table consisting of $2021\times 2021$ unit squares, some unit squares are colored black in such a way that if we place a mouse in the center of any square on the table it can walk in a straight line (up, down, left or right along a column or row) and leave the table without walking on any black square (other than the initial one if it is black). What is the maximum number of squares that can be colored black?
Problem
Source: 2021 Centroamerican and Caribbean Mathematical Olympiad, P3
Tags: Coloring, combinatorics, game
13.08.2021 14:46
Not sure if this is pretty simple or just me being dumb. I claim the answer to be $8080$. In particular, I claim for all $n \geq 2$, this value is $4n-4$. We proceed via induction. The base case is obvious since it's just the maximal possible. First of all, I claim removing squares (black to white) from the grid preserves the condition. Since obviously, this does not block any path, it's true. Now I claim each black square is either the leftmost or rightmost black square in its row or topmost or bottommost black square in its column. Obviously, if none are true then there is a black square in all four directions, so contradiction. If we think of "[left/right/top/bottom] most in [row/column] x" as a trophy granted to a single black square, then since every black square needs at least one trophy, we get an upper bound on the number of black squares. If there are at least four black squares that have more than one trophy, then since there are $4n$ trophies, there are at most $4n-4$ black squares, so we are done. Assume otherwise. Then from each corner square, move clockwise in a straight direction on the edge of the table until you reach the end or are on top of a black square. If there is at least one black square on each edge of the table, then every corner square will find a black square (which will be itself if it is black). Since these are not all distinct, WLOG the leftmost column is entirely empty with the only exception being the bottom-left block. We can repeat this process while going clockwise instead, so the other fail case must be on a different edge. If it is on the top row, then remove the top-right block and bottom-left block, and by induction on the $n-1$ by $n-1$ table in the bottom right, we finish. If it is on the right row, then start on the top two corners and move toward each other until you hit a black square. If there are at least two black squares on the top row, we get four distinct square with two trophies, contradiction, so there is exactly one black square on the top row. Remove this black square and the on e in the bottom left corner, and take the same $n-1$ by $n-1$ table and we finish by induction. Finally, if it occurs on the bottom row then remove the bottom left square and by induction on the top-right $n-1$ by $n-1$ table, we finish. Therefore, some row has no black squares in it, WLOG it is the top row. Then start at the top left corner and move down, at the bottom left corner and move up, at the top right corner and move down, at the bottom right corner and move up. If there are at least two square in both the left edge and the right edge, then we have a contradiction with those four black squares. So WLOG the left edge at at most one square. Then by induction on the bottom right $n-1$ by $n-1$ table after removing any squares on the left edge, we finish. So we are done. The construction is just black the left column, black the right column, and black the top two rows.
17.08.2021 18:16
Let us generalize to say that the answer is $4n-4$ for odd $n$. In particular $4(2021)-4=8080$. But first, notation dump. Define a unit edge to be an edge of a unit square that faces outside the board. Also, define an edge row or column to be the rightmost, upmost, ect row or column. Finally, call a happy mouse to be a mouse that starts on a black square Claim: All corners are black. Let us show turning a corner from white to black never turns a valid arrangement invalid. Notice that such an operation only blocks the two corner unit edges. Thus, if a mouse was planning to escape through one of those edges, it must be on an edge row or column. Thus, the mouse could escape anyway. Hence, to achieve maximality, one must color the corner squares black. $\square$ Now, let us only consider happy mice. Notice that at most one happy mouse can escape through any given edge. But, recall that there are $4n$ unit edges and $4$ edges that use the same black square (the corners). Thus, one can have at most $4n-4$ black squares. We see the following construction works $\begin{bmatrix} & \blacksquare & \blacksquare & \square & \square & \square & \blacksquare & \blacksquare \\ & \blacksquare & \square & \blacksquare & \square & \blacksquare & \square & \blacksquare \\ & \square & \blacksquare & \square & \blacksquare & \square & \blacksquare & \square \\ & \square & \square & \blacksquare & \square & \blacksquare & \square & \square \\ & \square & \blacksquare & \square & \blacksquare & \square & \blacksquare & \square \\ & \blacksquare & \square & \blacksquare & \square & \blacksquare & \square & \blacksquare \\ & \blacksquare & \blacksquare & \square & \square & \square & \blacksquare & \blacksquare \\ \end{bmatrix}$
21.08.2021 01:20
I am going to post a solution which is similar to the one that I found but was made shorter by some team leader (I don't remember exactly which leader it was, sorry). In general the answer is $4n-4$ which can be achieved using the following configuration: [asy][asy] unitsize(0.5cm); void drawGrid(int r, int c) { for (int i = 0; i <= r; ++i) { draw((0, i)--(c, i)); } for (int i = 0; i <= c; ++i) { draw((i, 0)--(i, r)); } } filldraw((0,0)--(0,9)--(1,9)--(1,0)--cycle,gray); filldraw((8,0)--(8,9)--(9,9)--(9,0)--cycle,gray); filldraw((0,0)--(9,0)--(9,2)--(0,2)--cycle,gray); drawGrid(9, 9); [/asy][/asy] We say that a configuration is restricted if the mouse can walk of the board starting from a black square. Now we pick a black square not on the edge of the board, we put the mouse on that square and we let it walk of the board. Then we paint black the last square the mouse touched before leaving the board and paint white the original square. This new configuration is restricted as the only squares whose escape route could be blocked after the change are the ones on the edge on which the new square lies, which can escape anyways as the lie on the edge. If we apply this operation to every black square we get a restricted configuration that has all its black squares on the edge of the board and has the same number of squares as the original one. This implies that a restricted configuration has at most $4n-4$ black squares. As any configuration of the original problem is also restricted, we get the desired bound. The end
21.08.2021 04:04
The answer with $2021$ replaced by $n$ is $4n-4$. A construction is shown below for $n=9$ that obviously generalizes, with black squares marked by $\blacksquare$ \[ \begin{bmatrix} \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare \\ \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare & \blacksquare \\ \blacksquare &&&&&&&& \blacksquare \\ \blacksquare &&&&&&&& \blacksquare \\ \blacksquare &&&&&&&& \blacksquare \\ \blacksquare &&&&&&&& \blacksquare \\ \blacksquare &&&&&&&& \blacksquare \\ \blacksquare &&&&&&&& \blacksquare \\ \blacksquare &&&&&&&& \blacksquare \\ \blacksquare &&&&&&&& \blacksquare \\ \end{bmatrix} \]To show this bound is tight, we do the following: from each black square, shine a laser towards the edge of the board passing through only white squares according to the path the mouse would take. For black squares that are on the very edge of the board, we specifically choose to shine the laser towards the adjacent wall (i.e.\ of length $1$). Then, each edge of chessboard is hit by at most one laser. Moreover, at the corner of the board, we observe that the walls for the first row and first column can be hit at most once (they are only accessible from the laser at that corner). So this implies a bound of $4(n-1)$, as needed.
17.04.2022 00:36
The answer is $4(2021)-4=8080$. For a construction, make the leftmost two columns, as well as the top and bottom rows black. We now prove thhat $8080$ is maximal. Place a laser pointer on each black cell pointing through only white cells (except for itself) that eventually exits the table, such that no laser passes through a corner cell—it is always possible to do this without the corner condition; to see that this can be done with the corner condition, note that only lasers placed on the edge of the table can pass through corners, and we can place lasers pointing "immediately outwards" for these. Now, note that there are no two lasers which concur (else one laser passes through a black cell), so counting based on the place where the laser exits the table, there are at most $4(2021-1)=8080$ lasers. Thus there are at most $8080$ black cells. $\blacksquare$
16.09.2023 22:25
Very funny problem. The answer for general $n$ is $4n-4$. First, note that we get the corner squares for free. For every black square on the grid, there exists an escape route for the mouse, which passes through a unique cell along the periphery of the table. On the other hand, there are $4n-8$ such cells, so at most $4n-8$ such squares in the interior. This yields the maximum; construction is obvious.
03.02.2024 09:49
Answer: $4(n-1)$. Assume the contrary, assume there are at least $4(n-1) + 1$ black squares. Then for every black square, there exists a direction such that mouse can leave the table without walking on any black square. Since there are $4(n-1)$ squares on the edge of the board, thus by pigeonhole principle, there exists 2 black squares such that they share common direction and same square on the edge. But this is a contradiction. Construction is below: $\begin{bmatrix} & \blacksquare & \blacksquare & \square & \square & \square & \blacksquare & \blacksquare \\ & \blacksquare & \square & \blacksquare & \square & \blacksquare & \square & \blacksquare \\ & \square & \blacksquare & \square & \blacksquare & \square & \blacksquare & \square \\ & \square & \square & \blacksquare & \square & \blacksquare & \square & \square \\ & \square & \blacksquare & \square & \blacksquare & \square & \blacksquare & \square \\ & \blacksquare & \square & \blacksquare & \square & \blacksquare & \square & \blacksquare \\ & \blacksquare & \blacksquare & \square & \square & \square & \blacksquare & \blacksquare \\ \end{bmatrix}$
18.11.2024 17:54
Replace $2021$ with $n$. Then the answer is $\boxed{4n-4}$. The construction is coloring the rectangle with opposite vertices (1-indexed) $(1,1)$ and $(n-1,n-1)$ all white, then coloring $(n,n+1)$ white, then coloring $(1,1)$ black. For $n=5$, this looks like: \begin{verbatim} BWWBB WWWBB WWWBB BBBBW BBBBB \end{verbatim} Now suppose that we have such a board. For each cell, consider one of its paths to the edge of the grid, subject to the condition that the path for a cell on the edge must directly leave. Note that if two things both go to the same edge, one of them is in the path of the other, so at most one of the things going to an edge can be black. But also, note that corners only need one of their edges (for the corner itself), since the other things on the edge are going out directly rather than going to the corner. $\blacksquare$