What is the minimal number of steps needed to create a chessboard?
Imagine you have a $8 \times 8$ completely white field of squares on your screen. Now you can click on any square. When you do this, all the squares in that column and line (including the one you clicked on it) will change their color (if it's white it will be black and vice versa). How many steps at least would it take to create a standard chessboard?
I tried it manually but it got too complicated and I lost track of the situation. But if I could tell my problem to Mathematica it could be very easy. Is there a way to write code to calculate this? Or even a formula to do this manually without any program?
Solution 1:
Hint: Try to convert your problem into solving a $64 \times 64$ system of linear equations over $\mathbb{F}_2$.
Solution 2:
A valid proof without advanced math:
No cell should be clicked more than once.
By clicking somewhere two times, you're just reversing your changes. Since the order of clicks does not make a difference, this holds even if you do other clicks between these. So we only need to consider one or zero clicks on each cell.
The number of clicks outside each row/column must be even.
If there was an odd number of clicks outside a given row, the number of cells changed in that row would be odd, leading to an odd number of black cells there. (Clicks in the row don't affect this, since they change all cells in that row).
The number of clicks in total must be even.
Each row changes 15 cells, so an odd number of clicks in total would lead to an odd number of color changes, resulting in an odd number of black cells on the whole board. (thanks user21820)
The number of clicks inside each row/column must be even.
Subtract the number of clicks outside a row (an even number) from the number of total clicks (another even number). The result will be even.
A cell will be changed in the end if and only if it was clicked.
Look at a row. The clicks in that row leave its cells unchanged, since there is an even number of them. Which cells are changed by the clicks in other rows? We can use the fact that there must be an even number of clicks in each column as well to tell.
Look at the cells in the row:
- If it was clicked, there is now one click in its column. There has to be an odd number more in other rows. These are the clicks outside the row that change this cell. Since there is an odd number of them, the cell will be changed in the end.
- If it was not clicked, there has to be an even number of clicks elsewhere in the column. This means the clicks outside the row also leave the cell unchanged.
The optimal solution is 32 clicks.
We proved that we need to click all the cells we want to change to get a chessboard coloring. There are 32 of these, so that's the best we can do. In fact, that's the only number of moves which can lead to a chessboard coloring if we don't click any cell twice.
Solution 3:
Note that on the starting board, assumed all white without lack of generality, there are 32 squares coloured correctly. One then can trivially verify that after a single click on any square of this starting board there are 33, or 32 + 1, squares coloured correctly.
Let's analyze that first move more closely. It accomplishes the reversal of precisely 15 squares: the square clicked; the other seven on its row; and the other seven on its column.
To arrive at a chessboard from an originally all-white board the final white squares must have been swapped an even number of times, and the black squares must have been swapped an odd number of times. It is trivial to verify that by clicking once on every black square, in any order, a chessboard will result. We need to prove that this is minimal.
This 32-move solution performed 32 * (7+7+1) = 32 * 15 = 480 colour swaps of a square. Note further that a single click can only possibly reach 7 black squares (clicking a black square) or 8 black squares (clicking on a white square). Thus to cover all black squares requires a minimum of 8 clicks (A click is required on each of the 8 rows, as well as on each of the 8 columns.)
Any set of 8 clicks will perform 8 * 15 = 120 colour swaps. Any selection of 8 clicks that covers all black squares will have swapped all squares on the board twice, except the 8 squares clicked which will have been swapped once only. Of course 64 + 64 - 8 = 120 as noted above. Therefore only 8 squares (net) will have changed colour.
Four other such patterns can at most also swap a net of 8 squares each.
By composing four such suitable patterns we can finally cover a net of 32 colour swaps, but this is our already discovered possible solution; so it is both possible and minimal. This relies on the commutativity of clicking, which is trivially proven.
This proof does not have all the rigour I would like, but should suffice to guide someone to a rigourous proof.
Solution 4:
Since you had asked this first at Mathematica site. I made a small program where you can play around to see the variations graphically.
Run the code in Mathematica and it will generate the dynamic grid shown below.
chess = Table[0, {i, 1, 8}, {j, 1, 8}]
toggle[m_] := Which[m === 1, 0, m === 0, 1];
click[m_, n_] := Module[{},
Table[chess[[m, j]] = toggle[chess[[m, j]]], {j, 1, 8}];
Table[chess[[j, n]] = toggle[chess[[j, n]]], {j, 1, 8}];
chess[[m, n]] = toggle[chess[[m, n]]];
]
Row[{Column[{Button["Reset", chess = Table[0, {i, 1, 8}, {j, 1, 8}]],
Grid@Array[Button[{#1, #2}, click[#1, #2]] &, {8, 8}]}],
Dynamic[ArrayPlot[chess, Mesh -> True, ImageSize -> 300]]}]
You can click on the elements to see the change.
