IMO 2021 Shortlist, C6. A Hunter and a Rabbit Again.

Do you remember problem 3 of IMO 2017? A wonderful problem! I glanced again on the results of that year and still cannot understand why they were so disastrous! The knowledge needed to solve it is just the Pythagoras theorem or an entry level of trigonometry. So, it was not about technique. Absolutely everyone at that level can make those calculations, and still only 1 student had something like 5 points. I am notified every time a guy posts a solution on that AoPS thread, and sometimes I take a glance. Most of them are like: “…the best strategy of the hunter is bla-bla, so he cannot discern whether the rabbit is here or there…” and then a bunch of calculations follows that shows something could increase. The emphasize is always on the calculations! I dare say had the same problem was formulated in another way it could have been completely solved by at least 75% of the contestants. Just changing the wording could make the difference! But, this is a story for another post (maybe the next one). Oh, that problem was a gem!

There is another problem on 2021 IMO’s shortlist worded using a hunter and a rabbit. It was listed as C6 but I think, it would have been solved by many students if it had been chosen as IMO 2021 problem. This problem is more of a technique than any out-of-the-box idea. Let us recall the statement.

Problem (IMO 2022 SL,C6). A hunter and an invisible rabbit play a game on an infinite square grid. First, the hunter fixes coloring of the cells with finitely many colors. The rabbit then secretly chooses a cell to start in. Every minute, the rabbit reports the color of its current cell, and then secretly moves to an adjacent cell that is not visited before (two cells are adjacent if they share a side). The hunter wins after some finite time either

• the rabbit cannot move; or
• the hunter can determine the cell in which the rabbit started.

Decide whether there exists a winning strategy for the hunter.

Solution.

The hunter can color the cells in a way that enables him to guess the starting point of the rabbit, providing the rabbit does not end up in a dead end.
We consider the colors as consisting of some layers, i.e. any color will be viewed as a tuple where each variable (layer) can take a finite number of colors. Each layer has a purpose. The first one is for orientation – to know the directions of each move the rabbit makes (up,down,right, left). The second layer will ensure there are no two paths with identical sequence of colors that start from different cells within a fixed frame around the origin. The third layer is to give us the information about the region (frame) within which the rabbit starts.
This structure of colors is only for convenience, clearly this configuration can be encoded with one dimensional colors. The first layer takes values and its purpose is to control the direction of the rabbit. We put these values on each row starting as and on the next row starting from , on the next one – from , then from and so on. This coloring allows us to translate the sequence of colors into directions, say, up, left, down, down, right, etc. So, if we know the starting cell, this layer helps us to recover rabbit’s trajectory. It also means that two equal sequences of the first layer color correspond to trajectories such that one of them can be obtained by translating the other with the vector determined by their starting points. The second layer of colors will allow the hunter to locate the starting position of the rabbit, providing he knows the rabbit started in a fixed frame. The second layer will consist of only two colors.
Suppose the hunter knows the approximate location the rabbits started from, i.e. he knows that the rabbit started in a cell inside some (big) square (frame), say centered at the origin. Suppose all the cells inside a bigger square (also centered at the origin) have their second layer already colored. We claim that the hunter can consecutively color the second layer of each cell in a bigger square in a way that there are not two paths starting from different cells in and leaving that have the same sequence of colors.
Let us fix two cells and be the vector . For any cell outside , but having a common side with we consider the cells . They cannot be both in (then q’ would have been inside since is convex). So, in case one of them is outside , say , and is inside this square, we set the second layer of to differ the second layer of , and the second layer of be thae same as that of that is, we color them alternatively. If both are outside we also color the second layers of alternatively. We do this procedure for all outside but with a common side with .
Suppose now, there exists two paths, say, that start from and respectively, and with the same sequences of colors. Suppose, is the first cell that one of them hits outside the frame . At this moment the other path hits one of the cells . But, we took care and have different second layer color. Thus, there are no paths starting from and respectively, that leave and have the same sequence of colors. Further, we color somehow the second layer of those cells that have a common side with and are still uncolored, and proceed with some other pair of cells and with one unit bigger than frame which we again denote as In the end, we expand the coloring to a frame and are sure that there are no two paths that start inside leave and have the same sequence of colors.

It remains to invent some sign that would show us the approximate location the rabbit started from. That’s the third layer that comes to help. This layer consists of three colors, say, white, black and neutral. Place a strip, two cells wide, symmetrical to the origin, and color the third layer of its inner cells white and its outer cells black. Thus, we will know if the rabbit starts within this strip – it will cross the border as white, black pattern. Now, we set infinitely many concentric strips like that of rapidly increasing sizes. It’s enough to ensure that the shortest path between two consecutive strips is longer than the longest path between the previous strips. We color the third layer of all other cells neutrally. In this way, examining the sequence ot the third layer’s color, we can determine the frame from which the rabbit started.

So, the number of needed colors is . But looking closely to the third layer one may see that in order to determine the frame the rabbit starts in, we actually only need strips one cell wide, colored, say, white, and all the other cells colored neutrally. Hence we can decrease the number of total colors to .