Bariz - Problem

Source:

Tags: Chessboard, combinatorics, square table, Coloring

parmenides51

23.03.2020 01:18

There is a $8\times 8$ table, drawn in a plane and painted in a chess board fashion. Peter mentally chooses a square and an interior point in it. Basil can draws any polygon (without self-intersections) in the plane and ask Peter whether the chosen point is inside or outside this polygon. What is the minimal number of questions suffcient to determine whether the chosen point is black or white?

Obviously one question is not sufficient, but we claim two questions is. We draw the following two polygons whose interior coincides exactly with the squares of the chessboard. \[ \begin{bmatrix} A && A && A && A & \\ A &A& A && A && A & \\ A && A && A && A & \\ A && A &A& A && A & \\ A && A && A && A & \\ A && A && A &A& A & \\ A && A && A && A & \\ A && A && A && A &A \\ \end{bmatrix} \]\[ \begin{bmatrix} B & B & B & B & B & B & B & B \\ & B &&&&&& \\ B & B & B & B & B & B & B & B \\ &&& B &&&& \\ B & B & B & B & B & B & B & B \\ &&&&& B && \\ B & B & B & B & B & B & B & B \\ &&&&&&& B \\ \end{bmatrix} \]Then one can determine the color for Peter's square by whether the point is in $A$, $B$, both, or neither.