The question goes as follows:
You are presented with a 8x8 square board, with some of the squares filled with red, and some white. You can study the board for as long as you wish, then look away while another person flips the color of one square. When you look again at the board, you are to identify exactly which square flipped in color. 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?
Obviously, one possible answer is 64 bits.
How can I prove 64 bits is the minimum bits required to do this job?
Or, if there is another way, how can I prove that this way has the minimum bits?
The required memory is six bits. One bit for the parity of red squares in each of the six shaded groups of 32 squares shown in the image below. For each group in which the parity changes, the altered square is in that group. For each group in which the parity does not change, the altered square is not in that group.