20
$\begingroup$

Under every grid cell of a chessboard, I put either one bean or nothing.

Now if you choose a (grid) rectangular area on the chessboard, then I will tell you the parity of the number of beans under that area.

How many rectangular areas do you have to inquire, before you can be sure to know the parity of the number of beans under all black cells?

$\endgroup$
18
$\begingroup$

This puzzle could have almost have been given the

tag, though that may have given a big hint.

You can think of each rectangle you pick as a move,

which you want to combine, like lights-out, such that each black square is picked an odd number of times, and each white square an even number of times. You can do this by picking the 8 rectangles consisting of every other row, and every other column, such that they intersect on only white squares. Those intersected white squares have obviously been picked twice. There are also white squares that are not included in any chosen rectangle, so are picked zero times. Every black square lies inside exactly one of the chosen rectangles.
If you then combine the parity results of those 8 rectangles, you get the parity of just the black squares because the white squares at the intersections are included twice and therefore do not affect the parity.

This solution is not unique. You can make the four horizontal rectangles wider, letting them overlap, as long as every other row is used in an odd number of rectangles, and the other rows an even number of times. The same is true for the set of four vertical rectangles.

Here is a proof for why this is the minimal number of rectangles:
(Thanks to loopywalt for plugging the final gap in the proof)

Consider two adjacent squares, one black, one white. If every rectangle we pick contains either both or neither of those squares, then we would not be able to distinguish a bean under the white square from a bean under the black square. Therefore at least one of our rectangles has an edge going inbetween the two squares. This is true for all adjacent squares, so we need the rectangles to cut along all the seams of the board.

Let's only consider adjacent squares that lie on the border of the board. There are 14 vertical pairs and 14 horizontal pairs that need to be cut. A rectangle can cut through at most 4 such pairs - and then it will cut only 4 horizontal pairs if it 8 units high, and only cut 4 vertical pairs if it is 8 units wide. If a rectangle does not cut 4 pairs of the same type, then it cuts only 2 or 0. This shows that 7 rectangles are not sufficient because each would have to cut 4 pairs of the same type, and the number of pairs of each type is not a multiple of 4. It can be done with 8 rectangles however, so 8 is optimal.

There exist optimal solutions in which some rectangles are used that are not 8 units long or wide. For example, you could use three horizontal rectangles consisting of rows 2, 4&5, and 7, three similar vertical rectangles, together with two 4x4 rectangles at diagonally opposite corners of the board.

$\endgroup$
9
  • $\begingroup$ Hi Jaap, thanks for answering! Although I didn't state explicitly, it would be preferable if you can also prove that your result is minimal (: $\endgroup$
    – WhatsUp
    Apr 29 at 15:27
  • 4
    $\begingroup$ I think you can proofify your argument by instead of regarding seams between entire ranks/files using only those between squares on the outermost ring. That way you get two groups of 14 requirements, only rectangles spanning the entire length or width can satisfy the maximum 4 of them and contributing to both groups at the same time can only be done in increments of one each. $\endgroup$
    – loopy walt
    Apr 30 at 0:49
  • 1
    $\begingroup$ "proofify", I like that word. $\endgroup$
    – justhalf
    Apr 30 at 4:42
  • $\begingroup$ @loopywalt Thank you, that does the trick! I'll update my proof. $\endgroup$ Apr 30 at 6:53
  • $\begingroup$ Now it's a perfect answer (: Good job both Jaap and @loopywalt! $\endgroup$
    – WhatsUp
    Apr 30 at 10:20
0
$\begingroup$

Since there is already a more bare hands approach, let me instead treat this as

a problem in linear algebra.

For any matrix $A \in \mathbb{Z}_2^{8\times 8}$ Let its dual be $A^\ast : \mathbb{Z}_2^{8\times 8} \rightarrow \mathbb{Z}_2$ defined by $(x_{ij}) \mapsto \sum_{i,j} a_{ij}x_{ij}$. $$~$$ If we let $B$ designate the $8 \times 8$ matrix with $b_{ij}=1$ iff $i,j$ is a black on the chessboard, then the puzzle is asking whether we can get $B^\ast$ as a linear combination of functionals from the subset $\{ R^\ast \mid R \text{ corresponds to a rectangular area} \}$ since the parity information about a rectangular area $R$ of the bean distribution corresponds to knowing the value of the functional $R^\ast$ on a matrix from $\mathbb{Z}_2^{8\times 8}$ representing the bean distribution. Now let $R_{i, \ast} \equiv \text{the $i$-th row is } 1$ and $R_{\ast, j} \equiv \text{the $j$-th coloumn is } 1$ then we can check that $$ R_{1, \ast} + R_{3, \ast} + R_{5, \ast} +R_{7, \ast} + R_{\ast, 2} + R_{\ast, 4} + R_{\ast, 6} + R_{\ast, 8} = B \\ \Longleftrightarrow R_{1, \ast}^\ast + R_{3, \ast}^\ast + R_{5, \ast}^\ast +R_{7, \ast}^\ast + R_{\ast, 2}^\ast + R_{\ast, 4}^\ast + R_{\ast, 6}^\ast + R_{\ast, 8}^\ast = B^\ast $$ where the intuition for the solution is just the same as in Jaap's answer.

Up to this point this framing doesn't really pay off, since we did not benefit from it to figure out the solution. However:

It is now easy to proof that we can not get a solution using less rectangles, i.e. a linear combination with less summands. The reason is that our solution has $8$ matrices for which it is easy to convince yourself that they are linearly independent. This is then also true for the corresponding functionals, making it impossible to represent $B^\ast$ with less summands: i.e. it is not possible to use less than $8$ rectangle parity checks.

$\endgroup$
2
  • $\begingroup$ I'm not convinced by the argument in your last paragraph. For example, if we ask instead the number of parity under the whole board, then we can still write it as $R_{1, *} + R_{2, *} + \dots + R_{8, *}$. These $8$ vectors (or matrices, in your language) are also linearly independent, thus the last paragraph of your argument seems to imply that the answer for this variation is also $8$. This however is obviously wrong, as the whole board is just one single rectangle. $\endgroup$
    – WhatsUp
    May 15 at 16:41
  • $\begingroup$ Yes, I see the point and agree. This needs some fixing. $\endgroup$
    – Lereau
    May 15 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.