Maths Olympiad Prep

Library / /257 of 397

, 2022

Combinatorics Difficulty 6.2 National Olympiad Prove it Taiwan

A hunter and an invisible rabbit play a game on the integer lattice plane Z2:={(x,y):x,yZ}\mathbb{Z}^2 := \{(x, y) : x, y \in \mathbb{Z}\} (Z\mathbb{Z} being the set of all integers). Before the game begins, the hunter first colors each point of Z2\mathbb{Z}^2 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?

Solution

First, note that if there are two coloring methods, where the first method colors point (x,y)(x,y) with color c1(x,y)c_1(x,y) and the second method colors point (x,y)(x,y) with color c2(x,y)c_2(x,y), then we can let c(x,y)=2c1(x,y)3c2(x,y)c(x,y) = 2^{c_1(x,y)}3^{c_2(x,y)}, and color (x,y)(x,y) with color c(x,y)c(x,y), 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 c1:Z2{1,2,3}c_1: \mathbb{Z}^2 \rightarrow \{1,2,3\} be c1(x,y)x(mod 3)c_1(x,y) \equiv x(\text{mod } 3). This coloring tells us whether the rabbit moved left, right, or vertically.

2. Next let c2:Z2{1,2,3}c_2: \mathbb{Z}^2 \rightarrow \{1,2,3\} be c1(x,y)y(mod 3)c_1(x,y) \equiv y(\text{mod } 3). This coloring tells us whether the rabbit moved up, down, or horizontally.

3. Define
K:={0,2,2+22,2+22+23,}{0,3,332,33233,}, K := \{0,2,2+2^2,2+2^2+2^3,\dots\} \cup \{0,-3,-3-3^2,-3-3^2-3^3,\dots\},
and let c3:Z2{1,2}c_3: \mathbb{Z}^2 \rightarrow \{1,2\} satisfy
c3(x,y)={1xK,2xK. c_3(x,y) = \begin{cases} 1 & x \in K, \\ 2 & x \notin K. \end{cases}
Note that the gaps between adjacent numbers in KK are all different, so combined with c1c_1, when c3c_3 equals 1 for the second time, we can determine with certainty the xx-coordinate of the rabbit's location.

4. Similarly, let c4:Z2{1,2}c_4: \mathbb{Z}^2 \rightarrow \{1,2\} satisfy
c4(x,y)={1yK,2yK. c_4(x,y) = \begin{cases} 1 & y \in K, \\ 2 & y \notin K. \end{cases}
Then when c4c_4 equals 1 for the second time, we can determine with certainty the yy-coordinate of the rabbit's location.

c5(x,y)={1x+yK,2x+yK. c_5(x, y) = \begin{cases} 1 & x + y \in K, \\ 2 & x + y \notin K. \end{cases}
Then when c5c_5 equals 1 for the second time, we can determine with certainty x+yx+y of the rabbit's location.

Now, suppose the rabbit is able to move every round; then among the three quantities x,y,x+yx,y,x+y, at least two must be unbounded, which means that among c3,c4,c5c_3, c_4, c_5, 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 x,y,x+yx,y,x+y, and thereby determine (x,y)(x,y). Combining all of the above, the hunter necessarily wins.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.