The cells of a square $100 \times 100$ table are colored in one of two colors, black or white. A coloring is called admissible if for any row or column, the number $b$ of black colored cells satisfies $50 \le b \le 60$. It is permitted to recolor a cell if by doing so the resulting configuration is still admissible. Prove that one can transition from any admissible coloring of the board to any other using a sequence of valid recoloring operations.
Problem
Source: Saint Petersburg 2016
Tags: combinatorics, Coloring
15.12.2016 20:40
Any solution $?$
15.12.2016 20:52
Very nice problem.
21.12.2016 19:00
We use a kind of reverse engineering. For some cell $c$ of the table let $col(c), row(c)$ denote the corresponding column/row, where $c$ is positioned. Take a cell $c_1$, which for example is white, but should be black in the final configuration. Coloring it black perhaps breaches the admissible condition on its row or column. (or possibly on both, in which case we call $c_1$ double breaching cell). Suppose the black cells of the row, where $c_1$ belongs to, become too much. Then there should exist a cell $c_2$ on $row(c_1)$, which is black but at the end should become white. If we color $c_2$ white without breaching the restriction, after that we can color also $c_1$. Otherwise, there exists a cell $c_3$ on the column $col(c_2)$, which is white, but should be black. Continuing that process, there are two possibilities. Either we come to a cell $c_n$ that can be recolored without troubles, or we make a deadlock loop $c_1,c_2,\dots,c_n=c_1$. In the first case we can recolor the chain $c_1,c_2,\dots,c_n$ backwards to the first $c_i$ which is not double breaching, and thus increasing the right colored cells. In the second case we leave that chain intact, and take a different cell. It's impossible all chains to be deadlocked, so at the end, we will increase again the number of right colored cells.
07.03.2020 10:30
dgrozev wrote: We use a kind of reverse engineering. For some cell $c$ of the table let $col(c), row(c)$ denote the corresponding column/row, where $c$ is positioned. Take a cell $c_1$, which for example is white, but should be black in the final configuration. Coloring it black perhaps breaches the admissible condition on its row or column. (or possibly on both, in which case we call $c_1$ double breaching cell). Suppose the black cells of the row, where $c_1$ belongs to, become too much. Then there should exist a cell $c_2$ on $row(c_1)$, which is black but at the end should become white. If we color $c_2$ white without breaching the restriction, after that we can color also $c_1$. Otherwise, there exists a cell $c_3$ on the column $col(c_2)$, which is white, but should be black. Continuing that process, there are two possibilities. Either we come to a cell $c_n$ that can be recolored without troubles, or we make a deadlock loop $c_1,c_2,\dots,c_n=c_1$. In the first case we can recolor the chain $c_1,c_2,\dots,c_n$ backwards to the first $c_i$ which is not double breaching, and thus increasing the right colored cells. In the second case we leave that chain intact, and take a different cell. It's impossible all chains to be deadlocked, so at the end, we will increase again the number of right colored cells. Why is it impossible that all chains are deadlocked?
07.03.2020 21:24
I don't remember my thoughts back then, but I think it is possible. Sorry and thanks! Anyway, we can fix it as follows. Let $c_1,c_2,\dots,c_n=c_1$ be a loop and as assumed $c_2$ is in the row of $c_1$ ; $c_{n-1}$ is in the column of $c_1$ and $c_1$ is white, $c_2$ - black, $c_{n-1}$ - black. So, we want to make $c_1$ be black and recolor the rest of them accordingly. As shown above, it boils down to make $c_{n-1}$ white and then go back to $c_1$. If we cannot make $c_{n-1}$ white it means (in the context) the white cells in $col(c_1)$ are exactly $50$. If the row of some white cell in this column contains less than $60$ black cells, then we can make this cell black, then $c_{n-1}$ white and back to $c_1$ and finally recover the cell that was white. If not, then we have at least $50\cdot 60+50\cdot 50=5500$ black cell in the entire table. We also can recolor $c_1,\dots,c_{n-1}$ in another way. Consider $row(c_1)$ which has $60$ black cells. If in the column of some of these black cells there are less than $50$ white cells, then we color this auxiliary black cell as white, then $c_1$ - black, then $c_{n-1}$ - white, then back to $c_2$ and finally recover the auxiliary cell as black. If it's not the case then the white cells in the table are at least $60\cdot 50+ 40\cdot 40=4600$, which means the black cells are at most $5400$. Composing the two cases, we see it's not possible both to hold, so in one way or another, we can recolor $c_1,c_2,\dots,c_{n-1}$.