In two neigbouring cells(dimensions $1\times 1$) of square table $10\times 10$ there is hidden treasure. John needs to guess these cells. In one $\textit{move}$ he can choose some cell of the table and can get information whether there is treasure in it or not. Determine minimal number of $\textit{move}$'s, with properly strategy, that always allows John to find cells in which is treasure hidden.
Problem
Source: Serbia Junior TST 2016 P3
Tags: combinatorics
MellowMelon
21.05.2016 23:42
I assume John needs to find both squares with treasure and that he does not need to actually make moves on the squares with treasure, meaning he is done as soon as he can declare with certainty where the treasure is. 50 moves are needed. First we show this is necessary. If 49 moves or less are made, tile the board with horizontal dominoes, and separately tile it with vertical dominoes. There is a horizontal domino and a vertical domino on which no moves have been made. It is possible for John to have never found treasure in his 49 moves, and then he cannot tell whether the two squares withtreasure are that horizontal domino, that vertical domino, or somewhere else. Strategy with 50 moves: color the board black and white. First John checks the 32 white squares on the interior. If any have treasure, he checks the 4 surrounding squares and finishes. Else, he next checks the 16 white squares on the edge but not in a corner. If any have treasure, he checks 2 of the 3 surrounding squares, which is enough to finish. At this point, John has either finished in at most 50 moves or not found any treasure in 48 moves. So if John is not done yet, the only white squares that can have treasure now are the two white corners; call them $S$ and $T$. John checks $S$ first. If it has treasure, his final move is to check a square adjacent to $S$, and the result of that is enough to finish. Else, his final move is to check a square adjacent to $T$, and since he can be certain $T$ has treasure this is enough to finish.