Somebody sent me a competition Math problem recently (an old one so don't worry about ongoing problems). It goes as follows:
You are presented with a 8 × 8 square board, with some of the squares black and some white. You can study the board and when you are done, you will look away and an opponent will flip on of the square's colors. After he/she has done this, you are to identify which square was flipped.
What is the minimum number of bits of memory that you need (during the period when you are not looking) in order to guarantee that you can achieve this?
64 is obviously the naive answer but I was just curious if this is actually the minimum. Any hints/ideas?
It can be done using just 15 bits.
For each row, determine whether the number of black squares is even or odd. That's 8 bits of information. Now do the same for each column, except column 1. That's another 7 bits.
Now, when the flip has been done you check which (if any) row has changed parity. If no row changed, no flip was done. If a row changed, then find which of the 7 columns also changed. If none of the 7 columns changed, then the change happened in column 1.
You now know both the row and the column where the change happened.