2
$\begingroup$

Alice draws a standard chessboard in the plane. (This means that she draws it in the middle of a big piece of paper). She then secretly chooses a point inside some square of the board. Bob can now draw any polygon (without self intersections) in the plane and ask Alice whether her point is inside or outside his polygon. Bob can continue to ask about other polygons until he is sure of the color of the square that contains Alice’s point. What is the minimum number of polygons sufficient for Bob to find out whether Alice’s point is black or white?

If Bob always draw a polygon that contain half of the remaining possible squares, then it took $\log_2 64=6$ steps to find out the exact square that contains the secret point. However, to find out the color of such point, I believe there is a strategy that takes less than 6 steps. Since there are connected squares with the same color on the chessboard, I have no idea how to determine the color of the square that contains the secret point. Anyone can help me out? Thanks a lot.

$\endgroup$
  • $\begingroup$ Bob's polygon may not intersect itself, but does it have to be convex? $\endgroup$ – David K Feb 27 '16 at 22:54
0
$\begingroup$

You can use this two-step process (obviously any one-step process is impossible):

image

If the square is inside both (1) and (2a), then it is black.
If the square is outside (1) but inside (2b), then it is black.
Otherwise it is white.

$\endgroup$
  • $\begingroup$ What about the top square in the third column from the left?? It's black, and is in first polygon, so we go to 2a. However, it's not in the second polygon, which would imply it's white by your test, correct? $\endgroup$ – Brevan Ellefsen Feb 27 '16 at 23:17
  • $\begingroup$ @BrevanEllefsen Whoops, that's a mistake. The odd-numbered squares on the first row were supposed to be part of the polygon. $\endgroup$ – Frxstrem Feb 27 '16 at 23:19
2
$\begingroup$

A "comb-shaped" polygon can be used to find out if the row is odd or even. Same goes for odd or even column. Combining these two tests suffices (and "obviously" a single test does not work).

$\endgroup$

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.