# In an $8×8$ table one of the square is colored black and all the others are white . Prove that one cannot make all the boxes white by recoloring the r

In an $$8×8$$ table one of the square is colored black and all the others are white . Prove that one cannot make all the boxes white by recoloring the rows and columns . "Recoloring" is the operation of changing the color of all boxes in a row or in a column .

This is a problem taken from Mathematical Circles by Dimitri Fomin , Sergey Genkin and IIa Itenberg.

My solution goes like this:

We have a square colored black while all other squares are white. So, in order to make it white we must first recolor its row or its column in which the black colored square is present . Now , if we recolor the row or the column the number black squares will be increased and it's parity will still be odd as we now have $$7$$ black squares in that particular row or column . Now, if we again recolor that row or column it will again get reverted back to its initial configuration. So, we must now color each of the row or column in which we have one of those $$7$$ black sqaures . But this will also result in an odd number of black squares as we have then $$7-1+7=13$$ black squares in total. So, after any transformations we are left with an odd number of black squares. If all the squares are colored black then we have $$0$$ black squares . This has an even parity. So, this is not possible to have all squares colored white.

I want to verify my proof whether it is alright or not? Is this valid? Of course there is a duplicate link about this question but that asks for a different thing. I am asking whether thus proof is valid or not...that link asks probably for a verification of a different proof ...but I want to know whether this proof is valid or not?....

Also if we have a $$3×3$$ square like the one given in the figure can we do the do the same thing.

Can we solve this using the same above reasoning?

Your analysis for the $$8 \times 8$$ square amounts to saying that each operation leaves the parity of the total number of black squares unchanged. This assertion is accurate, and therefore, the analysis is valid. The assertion critically depends on the idea that $$(8-1)$$ has the same parity as $$(1)$$.

For the $$3 \times 3$$ square, this specific approach is invalid, because (for example) $$(3-1)$$ does not have the same parity as $$(1)$$.

At this point, it is unclear whether the same conclusion is accurate in the $$3 \times 3$$ square. That is, there may exist a similar but different valid argument that involves $$\pmod{n}$$, where $$n$$ is some positive integer other than $$(2)$$.

For what it's worth, an alternative (convoluted and therefore inferior) approach for the $$8 \times 8$$ square is to recognize that the computation of $$(W - B)$$ (i.e. # of white squares - number of black squares) is unchanged $$\pmod{4}$$ because (for example) $$[(+6) - (-6)] \equiv 0\pmod{4}$$.

This yields a similar contradiction, as your analysis of the $$8 \times 8$$ square, because $$(63 - 1) \equiv 2\pmod{4}.$$

• ...so my first approach is correct right?...but the 2nd one it holds invalid, right?...
– user992622
Commented Apr 24, 2022 at 15:51
• @Franklin Yes, although the 2nd approach might yield to minor modifications, to make it valid. Of course, if the 2nd assertion is false, then it will be more difficult to prove. Proving false assertions is usually more difficult than proving true assertions. Commented Apr 24, 2022 at 15:52
• ....Thank you ! I do get it now...Thanks a lot!....
– user992622
Commented Apr 24, 2022 at 17:23

For the general $$N\times M$$ case, your approach works exactly when both $$N$$ and $$M$$ are even. In other cases (for $$N,M\ge2$$), you can reduce to the $$2\times2$$ case by considering only the corners of the grid, or indeed the corners of any rectangle contained in the grid. That is, you can't clear the board if you can't even clear the corners.

In fact, this insight gives an immediate and powerful necessary condition on the initial configuration: Every (orthogonal) rectangle in the grid must have an even number of corners initially black. I think this is sufficient as well? But I don't know.

EDIT: Indeed, the condition in bold above is sufficient, as can be seen by a simple greedy solving algorithm:

Clear the first row (so that it’s all white) using column moves. The rectangle condition is conserved after any moves, and it follows that all rows are either all black or all white now, which is clearly a solvable state.

• It seems like that condition comes down to: each row is either identical to, or the reversal of, the top row. (or equivalently, the same statement for columns)
– Ned
Commented Apr 27, 2022 at 22:16
• @Ned Of course, you’re right. I had a feeling there was a much simpler way, thanks Commented Apr 28, 2022 at 6:02
• So you can generate all admissible starting positions by assigning the first row and first column squares arbitrarily (or any one row and any one column), and then the rest is determined, giving $M+N-1$ arbitrary choices out of $MN$ spots in the grid. Or we an think of these assignments as what's obtainable from the all-white initial position ... I wonder if there's an existing name for them.
– Ned
Commented Apr 28, 2022 at 12:58
• @Ned Yes, I understand, and I agree. I don’t know any name for this either though... Commented Apr 28, 2022 at 14:06

The only moves that affect the corner cells are the top/bottom rows and left/right columns.

Neither of these alter the total parity of the corner cells, and as the initial parity is $$1$$, parity $$0$$ is unachievable.