The cells of a $100 \times 100$ table are colored white. In one move, it is allowed to select some $99$ cells from the same row or column and recolor each of them with the opposite color. What is the smallest number of moves needed to get a table with a chessboard coloring? S. Berlov
Problem
Source: St Petersburg 2021 11.2
Tags: combinatorics, grid
03.01.2022 18:01
Claim-1: We need at least $100$ moves to make the chessboard coloring. Proof: In every move we can make at most 50 white squares black. There are a total of 5000 black squares in the $100 \times 100$ chessboard. So we need at least $\frac{5000}{50}=100$. So we need at least 100 moves to do that.[N.B THIS PROOF IS WRONG SORRY. @BELOW DID THE JOB.] Claim-2: There exist a way by which we can make the chessboard coloring in $100$ moves. Process: We name the rows and columns by number $1$ to $100$ (the left most column is 1 the next is 2 and so on)(The top row is 1 the adjacent down as 2 and so on). Now we select a diagonal of the whole board. Let us take the diagonal having cells $(1,1),(2,2), \cdots ,(100,100)$. Now in every moves we will not take the cell in the diagonal in our chosen $99$. So our moves will be: We take all the even columns and make moves on them. Taking the 99 cell except the one from the diagonal. A total 50 moves are made. Next we use our move on every even row in the same way as before. Thus 100 moves are made, and we have a chess board coloring. $\square$
12.01.2022 18:22
Since I was not clever enough to do the counting properly (couting only the 50 "relevant cells" changed instead of all 99), here is an alternative proof of Claim 1: Suppose we do it in at most 99 moves. Thus, at least one row and at least one column was never chosen. Clearly, their intersection then has to be a white cell, so their union contains exactly $100$ black cells. But at most one of them can be changed in each move, contradiction.
13.01.2022 18:55
Or suppose we do it in at most 99 moves, A move change row and B change column. If A < B so A < 50, we consider 1 column not change in any move. That column will have 50 black but 1 move change row only can add 1 black square in that column so that column will have < 50 black square ,contradiction.
06.08.2022 11:19
let $(x,y)$ denote the cell in the column $x$ and row $y$: Proving of minimality: notice that the chess coloring requires having a diagonal with black cells only, the set $S$ denote those cells. Since each cell in $S$ lie in a different row and column from another cell in $S$, we need at least $\left | S \right |=100$ moves to get the desired coloring. Construction for $100$ moves: Just apply the special move for the cells $(2i,2(51-i))$ as $i$ varries through $\{1,2,...50\}$. the special move for a cell $C$ in the grid is to change the color of the $198$ cells in its row and and column (except the cell $C$ itself), notice that this requires 2 moves. $\blacksquare$