A hunter and an invisible rabbit play a game on the integer lattice plane ( being the set of all integers). Before the game begins, the hunter first colors each point of with exactly one color using finitely many colors. Then, after seeing the hunter's coloring method, the rabbit secretly chooses a point as its starting point. In each subsequent minute, the rabbit first tells the hunter the color of the point it is currently at, and then secretly chooses one of the four adjacent points (up, down, left, right) that it has never visited before, and moves to that point.
If within finite time the rabbit can no longer move, or the hunter can determine with certainty the starting point chosen by the rabbit at the beginning of the game, then the hunter wins. The question is: does there exist a winning strategy that allows the hunter to win within finite time?
, 2022
Solution
First, note that if there are two coloring methods, where the first method colors point with color and the second method colors point with color , then we can let , and color with color , thereby obtaining a coloring method that simultaneously achieves the functions of both coloring methods. Therefore, we will give five coloring methods below, which together allow us to determine the rabbit's position, thus achieving what the problem requires.
1. First let be . This coloring tells us whether the rabbit moved left, right, or vertically.
2. Next let be . This coloring tells us whether the rabbit moved up, down, or horizontally.
3. Define
and let satisfy
Note that the gaps between adjacent numbers in are all different, so combined with , when equals 1 for the second time, we can determine with certainty the -coordinate of the rabbit's location.
4. Similarly, let satisfy
Then when equals 1 for the second time, we can determine with certainty the -coordinate of the rabbit's location.
Then when equals 1 for the second time, we can determine with certainty of the rabbit's location.
Now, suppose the rabbit is able to move every round; then among the three quantities , at least two must be unbounded, which means that among , at least two of them will equal 1 for the second time. In other words, we must be able to determine at least two of , and thereby determine . Combining all of the above, the hunter necessarily wins.