Maths Olympiad Prep

Library / /504 of 520

Combinatorics Difficulty 7.6 National olympiad, round 2 Prove it

A hunter and an invisible rabbit play on an infinite square grid, that is, where each cell has four neighbors: left, right, up, and down. First, the hunter colors each cell of the grid, but can only use a finite number of colors. The rabbit then chooses a cell on the grid, which will be its starting point. It then begins to move: each minute, it tells the hunter the color of the cell it is on, and then moves to one of the four adjacent cells. Of course, since it is invisible, the only information the hunter has access to are the colors the rabbit announces each minute just before moving.
The hunter wins if, after a finite time,
\triangleright he can identify the cell the rabbit initially chose, or if
\triangleright the rabbit returns to a cell it had previously visited.
Does the hunter have a winning strategy?

Solution

Indeed, the hunter has a winning strategy, for example, the one given below. First, he identifies the grid with the set Z2\mathbb{Z}^{2}, then associates each cell c=(x,y)\mathbf{c}=(x, y) with the triplet φ(c)=(x,y,x+y)\varphi(\mathbf{c})=(x, y, x+y).
Each time the rabbit moves, two components of the triplet φ(c)\varphi \mathbf{( c )} vary by ±1\pm 1, and the third component does not change. Furthermore, knowing two of the coordinates of φ(c)\varphi(\mathbf{c}) is enough to identify c. In particular, if there exists a finite set EE such that at any time, the rabbit is in a cell c such that at least two of the components of φ(c)\varphi(\mathbf{c}) are in EE, it is known that the rabbit is constrained to evolve within a finite set of cells, which will inevitably lead to its defeat and transformation into civet.
Therefore, at least two of the three components of φ(c)\varphi(\mathbf{c}) will take an infinite number of values. If the hunter can identify, at a given moment, the values taken by these components, he will deduce the actual position of the rabbit and will have won.
By doing so, the hunter has reduced the problem to the following one-dimensional problem: given an invisible rabbit that moves along the axis Z\mathbb{Z} by steps of 1,0-1,0 or +1 and is constrained to pass through an infinite number of integers, how can coloring Z\mathbb{Z} using a finite number of colors allow the hunter to identify the initial position of the rabbit along this axis? Once such a coloring col: Z{0,1,,κ1}\mathbb{Z} \rightarrow\{0,1, \ldots, \kappa-1\} using κ\kappa colors numbered from 0 to κ1\kappa-1 is established, the hunter only needs to use κ3\kappa^{3} colors, identified with the elements of the set {0,1,,κ1}3\{0,1, \ldots, \kappa-1\}^{3}, and to color the cell c=(x,y)\mathbf{c}=(x, y) with the color (col(x),col(y),col(x+y))(\operatorname{col}(x), \operatorname{col}(y), \operatorname{col}(x+y)).
To answer this new one-dimensional problem, the hunter colors Z\mathbb{Z} using three colors, numbered from 1 to 3, and paints in color cc all integers nn such that nc(mod3)n \equiv c(\bmod 3). In this way, he knows at any time whether the rabbit is moving to the left or to the right.
Then he repaints with color 4 the integers, previously colored 3, that are of the form 3×(3)n3 \times(-3)^{n} with nn a natural number. Thus, he does not lose his previous information on the value of the cells modulo 3, nor on the value (1,0(-1,0 or +1) of the rabbit's movements. Consequently, if he ever manages to identify the rabbit's position at a given moment, he knows its position at any time during the game.
Finally, the rabbit will pass through two consecutive elements of the set E={3×(3)n:n0}\mathcal{E}=\left\{3 \times(-3)^{n}: n \geqslant 0\right\}. If these two elements are 3×(3)n3 \times(-3)^{n} and 3×(3)n+23 \times(-3)^{n+2}, the difference between them, in absolute value, is 8×3n8 \times 3^{n}. If they are 3 and -9, this difference, in absolute value, is equal to 12. Therefore, after the rabbit has passed through two consecutive elements of E\mathcal{E}, the hunter easily identifies these two elements and, based on the variations in the rabbit's position, the element of E\mathcal{E} where the rabbit has just arrived. He then deduces the initial position of the rabbit, which allows him to win the one-dimensional game, and thus win the original two-dimensional game.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.