5

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?

Daniel Mathias
  • 5,415
  • 1
  • 12
  • 21
Chanhyuk Park
  • 274
  • 8
  • 1
    Your question appears to be missing a portion of its text. The phrase for as long as you look back makes no sense. – Daniel Mathias Nov 18 '23 at 16:23
  • If exactly one square changes, then the minimum should be 6 bits because $64=2^6$ – Daniel Mathias Nov 18 '23 at 16:28
  • Are you saying that exactly one square has been flipped and that your task is to express unambiguously exactly which of the 64 squares is the one that was flipped? If so, then @DanielMathias has your answer. You need to be able to uniquely express each of the 64 possible answers, and that requires $\log_2 64 = 6$ bits. – Paul Tanenbaum Nov 18 '23 at 16:32
  • @PaulTanenbaum Can you explain more? What do you mean by uniquely expressing each of the 64 possible answers? – Chanhyuk Park Nov 18 '23 at 16:50
  • One bit can specify whether the flipped square is in the top or the bottom half. A second can specify which of the two pairs of rows within that half, and a third bit for which row within that pair. So 3 bits can specify exactly which row. And similarly, 3 more bits can specify precisely which column. In total, 3 bits + 3 bits tells you which square. – Paul Tanenbaum Nov 18 '23 at 20:12
  • No other way can always do the job in fewer bits because any single bit can only split things into two groups (it’s a yes-no or an above-below, or an include-exclude… that sort of split). So the answer to a single 1-bit question can at best be guaranteed to eliminate only one half of the not-yet-eliminated squares. And the 6-bit approach I just described already achieves the always-chop-off-half-the-remaining-problem. So no approach can always do better. – Paul Tanenbaum Nov 18 '23 at 20:12
  • This question is a duplicate of an older question which has only an incorrect answer. – Daniel Mathias Nov 19 '23 at 02:28

1 Answers1

7

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.

enter image description here

Daniel Mathias
  • 5,415
  • 1
  • 12
  • 21
  • Then how do you know it’s the minimum? – Chanhyuk Park Nov 18 '23 at 16:57
  • 3
    @CHPark Five bits can uniquely determine only 32 possible outcomes, but we must identify one of 64 possible results. – Daniel Mathias Nov 18 '23 at 17:00
  • 1
    Just as an observation, this is perhaps the most natural type of answer, once you interpret the question as a sensing problem: there is a $64$-bit state, and you have access to arbitrary binary functions of the same, of which you select some $N$, as $f_1, f_2, \cdots, f_N$. For a one-hot $y$, given $f_i(x)$ and $f_i(x \oplus y),$ you want to be able to determine $y.$ Question is how big $N$ needs to be (and which $f_i$ do you need) to ensure this. – stochasticboy321 Nov 19 '23 at 02:29
  • 1
    Since $\oplus$ is a linear operation (working in $\mathbb{F}_2$), it's natural to first consider linear $f_i$s, and then recognizing that you just need six such linearly indpendent $f_i$ to determine the state exactly (these are of the form $f_i = \langle a_i,x\rangle$ such that each $a_i$ has weight $64/2 = 32$), which of course works due to the fact that you only need $6$ bits to encode a single number from $1$ to $64$. – stochasticboy321 Nov 19 '23 at 02:29