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.
$\begingroup$
$\endgroup$
8
-
$\begingroup$ Surely it would just have to be guessing in a checkerboard pattern, which would be minimal 50? I can't really see how you could narrow it down for a 2x1 target. Could be wrong though $\endgroup$– Beastly GerbilFeb 7, 2021 at 22:55
-
1$\begingroup$ You would have to show how this 50 move actually works. @BeastlyGerbil $\endgroup$– nonuserFeb 7, 2021 at 22:58
-
1$\begingroup$ I wont answer as it seems too simple, there is probably a better solution. But worst case scenario 51 moves. Guess the checkerboard, and then one of the adjacent cells to the correct cell $\endgroup$– Beastly GerbilFeb 7, 2021 at 22:59
-
$\begingroup$ Which adjacent cell? It may have 4 adjancent cells, so in worst case 3 more moves? $\endgroup$– nonuserFeb 7, 2021 at 23:00
-
1$\begingroup$ Actually, if the cell was towards the middle then it wouldn't be one of the last cells guessed. So 51 I think would actually be the worst. If its in the middle itll be guessed earlier so wont be the worst case scenario $\endgroup$– Beastly GerbilFeb 7, 2021 at 23:01
|
Show 3 more comments
2 Answers
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ You should prove 49 is impossible. If you start with such an asumption there is nothing to prove. $\endgroup$– nonuserFeb 8, 2021 at 7:41
-
3$\begingroup$ @Greedoid I proved the statement: if we have only 49 moves, regardless of how we choose the 49 moves, we cannot determine the position of the treasure in the worst case. Therefore 49 is impossible, and the 50th move is needed. $\endgroup$– BubblerFeb 8, 2021 at 7:46
$\begingroup$
$\endgroup$
6
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:
....__...
...xx
..xoox
...xx
Which is impossible with only 49 x marks.
-
$\begingroup$ Move #48 must be on an edge or corner, and move #49 must be in a corner. Otherwise you could run out of moves trying to identify the second adjacent square. $\endgroup$ Feb 13, 2021 at 15:27
-
$\begingroup$ These moves can be anywhere as long as you leave a corner square out. $\endgroup$– NautilusFeb 13, 2021 at 15:35
-
$\begingroup$ If I've guessed a1, a3, a5, a7, a9, b2, b4, ..., i9, j2, j4, j6 for the first 48 moves, and guess j8 as move #49 (leaving corner j10 out), and find treasure on j8, the other treasure could be on j7, j9, or i8, and I can't count on knowing which with just move #50 left to help. $\endgroup$ Feb 13, 2021 at 15:39
-
$\begingroup$ I understand the trouble with that now. Then I pick the dark red ones first to get the squares with the most neighbors out of the way, then the red ones, leaving the pink ones for the last. $\endgroup$– NautilusFeb 13, 2021 at 15:59
-
$\begingroup$ Isn't this now just the same as Bubbler's answer? $\endgroup$ Feb 13, 2021 at 16:42