1

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?

gowrath
  • 3,573
  • 13
  • 31
  • You can memorise one less bit (63). If you detect no flipped bits, then the bit that was flipped must be the one you didn't memorise. And this is optimal. – Parcly Taxel Sep 28 '16 at 22:47
  • @ParclyTaxel This is true. Is there any way to prove that 63 is optimal besides saying, no one can do better so it must be the best way? – gowrath Sep 28 '16 at 22:59
  • Suppose you memorise two less bits (62). Then if the opponent flips one of the two bits you didn't memorise, you can't tell which one. If the opponent doesn't have to flip a square, then you do need all 64 bits; if you didn't memorise some bits you wouldn't be able to tell between the opponent flipping an unmemorised bit and leaving everything untouched. – Parcly Taxel Sep 28 '16 at 23:04

1 Answers1

1

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.

Jens
  • 5,686
  • 2
  • 20
  • 38
  • I had a feeling there would be way like this. Again, I pose a similar question I asked before to another answer. Is there any way to rigorously prove that this is the lowest possibly number of bits you can use besides stating, 'well no one can do better'? – gowrath Oct 02 '16 at 21:59
  • The minimum is six bits. See my answer in this recent duplicate. Note that the question guarantees that exactly one square was flipped. 'No flip' is not an option. – Daniel Mathias Nov 19 '23 at 02:34