In a 10x10 square table, two neigbouring 1x1 cells contain a hidden treasure. John needs to guess these cells. In one move he can choose some cell of the table and can get information whether there is treasure in it or not. Determine the minimum number of moves, and explain the strategy, that always allows John to find the cells in which the treasure is hidden.
I think I can do it in
50 moves, which can be shown to be optimal.
How to achieve it:
First, try the following 32 positions. If one of them has a treasure, the other part can be found in three more moves in the worst case (by trying the four neighbors sequentially; you know it is in the fourth if it's not found in the first three)........... .X.X.X.X.. ..X.X.X.X. .X.X.X.X.. ..X.X.X.X. .X.X.X.X.. ..X.X.X.X. .X.X.X.X.. ..X.X.X.X. ..........
Next, try the following 16 positions. If a treasure is found, proceed as in the first case; this time we only need to check two neighbors out of three, so the treasure can be identified in 50 moves total...X.X.X.X. . . . . .X X. . . . . . . . . .X X. . . . . . . . . .X X. . . . . . . . . .X X. . . . . .X.X.X.X..
Now, we only have two corners left. Here comes the trick to reliably identify the positions in 50 moves. For the 49th move, check X. If it has a treasure, try one of its neighbors (50th move) to identify if the treasure is horizontal or vertical. Otherwise, check Y (which is NOT the corner) as the 50th move, to identify if the treasure is horizontal or vertical at the opposite corner.X. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Y . . . . ..
Now, why is this optimal?
Imagine a board, which is fully covered with horizontal 1x2 dominoes. Let's assume we have only 49 moves available, and all 49 moves resulted in a miss (no treasure). If the 49 moves are covered by 48 or fewer dominoes, we obviously have at least two possibilities left for the treasure domino. If the 49 moves are on 49 distinct dominoes, consider the uncovered domino (U) and any of its vertically adjacent ones (V). V has one cell not yet identified by our 49 moves, so U and V combined has a vertical uncovered domino (W). So we don't know the treasure is at U or W. Therefore, we can't identify the treasure in 49 moves in the worst case.
It can be done in 50 moves.
If we paint it like a chessboard, one of the squares is black and one is white. So, we need to search through all the squares of the same color first, which requires at most 49 moves.
Dark red: Picked first
Red: Picked later
Pink: Picked last
After the 49th move, the remaining square is one of them, and if we leave one of the corner squares for the last, we only need to check one of the two squares adjacent to it.
Pink squares have 2, red ones 3 and dark red ones have 4 neighbors, so all non-pink squares must be exhausted before the 49th move. Similarly, all dark red squares must be exhausted before the 48th move. We don't even need to strictly follow the dark red-red-pink order as long as those conditions are met.
For 49 moves to be enough, only one possible combination of two adjacent squares must remain:
Which is impossible with only 49 x marks.