Problem A. 935. (May 2026)
A. 935. A criminal starts at the origin and escapes by moving on the integer lattice points of the plane. At each step, they move to a neighboring lattice point, with the restriction that they never move in the same direction twice consecutively. It is known that their first move is upward, and that their path visits every lattice point exactly once. An agent also starts at the origin but cannot see the criminal. Fortunately, the headquarters can track the criminal's movement, but they can communicate with the agent only in the following way: a predetermined infinite set \(\displaystyle S \subseteq \mathbb{N}\) is given, and for each \(\displaystyle s \in S\), after the \(\displaystyle s\)-th step of the criminal, a message consisting of either \(\displaystyle 1\) or \(\displaystyle 2\) is sent to the agent. The agent moves only when a message is received, and always makes exactly as many steps as the criminal has taken since the last message.
What is the value of \(\displaystyle I=\inf_{S} \left(\lim_{n\rightarrow \infty} \frac{|S \cap \{1,2,3,\ldots,n\}|}{n} \right)\) taken over all sets \(\displaystyle S\) for which the agent can uniquely reconstruct the movement of the criminal?
Both the agent and the headquarters are aware of the rules restricting the criminal's movement.
Proposed by Márton Németh, Budapest)
(7 pont)
Deadline expired on June 10, 2026.
Solution. We show that the value of the infimum is \(\displaystyle I=1/2\).
Upper bound: We have \(\displaystyle I\leq 1/2\). To prove this, we show that the set
\(\displaystyle S=\{2,4,6,8,\ldots\} \)
is suitable.
Suppose that the criminal has already taken several steps and has visited the cells
\(\displaystyle (x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n). \)
Clearly,
\(\displaystyle (x_0,y_0)=(0,0),\qquad (x_1,y_1)=(0,1). \)
For a value \(\displaystyle 0\le i\le n-3\), we call \(\displaystyle i\) a left twist if the fourth vertex of the square determined by the lattice points
\(\displaystyle (x_i,y_i),\ (x_{i+1},y_{i+1}),\ (x_{i+2},y_{i+2}) \)
does not occur among the lattice points \(\displaystyle (x_j,y_j)\), and after the \(\displaystyle (i+1)\)-st step the criminal turned left and departed from \(\displaystyle (x_{i+1},y_{i+1})\).
Similarly, we call it a right twist if the turn was to the right.
Claim: If there exists a continuation
\(\displaystyle (x_{n+1},y_{n+1}),\ldots \)
of the criminal's path satisfying the conditions, then
\(\displaystyle (x_0,y_0),\ldots,(x_n,y_n) \)
cannot contain both a left twist and a right twist.
Proof: Without loss of generality, suppose that \(\displaystyle i\) is a right twist and \(\displaystyle j\) is a left twist, where
\(\displaystyle 0\le i<j\le n-3. \)
Figure 1: The missing cell of the right twist cannot be visited.
Let \(\displaystyle (a,b)\) be the fourth vertex of the square associated with the right twist indexed by \(\displaystyle i\), and let \(\displaystyle (c,d)\) be the fourth vertex associated with the left twist indexed by \(\displaystyle j\).
There are two possibilities. In the first case, the point \(\displaystyle (a,b)\) appears earlier in the continuation
\(\displaystyle (x_{n+1},y_{n+1}),\ldots. \)
Observe that the criminal moves vertically on odd-numbered steps and horizontally on even-numbered steps. Furthermore, the parity of \(\displaystyle x+y\) agrees with the parity of the step number on which the criminal reaches \(\displaystyle (x,y)\). Therefore, we can uniquely determine that \(\displaystyle (a,b)\) is entered from the same direction as \(\displaystyle (x_{i+1},y_{i+1})\).
Accordingly, one of the two situations shown in the figure must occur. In the first situation (since we assumed \(\displaystyle j<n-3\)), the criminal can no longer visit the cell \(\displaystyle (c,d)\). In the second situation, the criminal has completely trapped themselves.
Similarly, we obtain a contradiction if we assume that \(\displaystyle (c,d)\) is reached before \(\displaystyle (a,b)\). This proves the claim.
Returning to the original statement, we show that the criminal can make his \(\displaystyle (2k+1)\)-st and \(\displaystyle (2k+2)\)-nd moves in at most \(\displaystyle 2\) ways out of the \(\displaystyle 4\) possibilities. Clearly, this implies the upper bound.
For \(\displaystyle k=0\) this is true, since we know that the criminal's first move is upward.
For \(\displaystyle k>0\), translate and reflect the coordinate system so that the \(\displaystyle (2k-1)\)-st and \(\displaystyle 2k\)-th moves are
\(\displaystyle (0,0)\to(0,1),\qquad (0,1)\to(1,1). \)
If either of the lattice points \(\displaystyle (1,0)\) or \(\displaystyle (1,2)\) has already been visited, then the \(\displaystyle (2k+1)\)-st move is uniquely determined, and we are done. Thus assume that both cells are free.
Observe that the next two moves cannot be
\(\displaystyle (1,1)\to(1,0)\to(0,0), \)
so there are already only \(\displaystyle 3\) possibilities.
Therefore the only remaining case is when the cells \(\displaystyle (0,2)\) and \(\displaystyle (2,2)\) are also free. In this case, however, the continuation
\(\displaystyle (1,1)\to(1,2)\to(2,2) \)
creates a right twist and a left twist corresponding to the triples
\(\displaystyle \{(0,0),(0,1),(1,1)\} \)
and
\(\displaystyle \{(0,1),(1,1),(1,2)\}, \)
respectively, and thus we are done.
Lower bound: We have \(\displaystyle I\ge 1/2\).
To prove this, suppose that during its first \(\displaystyle s\) steps the criminal follows the zig-zag path
\(\displaystyle P=(0,0)\to(0,1)\to(1,1)\to(1,0)\to(2,0)\to(2,1)\to\cdots. \)
Figure 2: The path \(\displaystyle P\).
Suppose that \(\displaystyle s\) is even and
\(\displaystyle s\in S,\qquad s+1,s+2,s+3\notin S. \)
We claim that the first \(\displaystyle s\) steps of \(\displaystyle P\) can be extended by \(\displaystyle 3\) further steps in exactly \(\displaystyle 3\) different ways, and each resulting path can be completed to a suitable traversal of the grid.
Indeed, by symmetry with respect to the coordinate axes and the general nature of \(\displaystyle s\), the following pattern covers all three cases:
Figure 3: Continuation of path \(\displaystyle P\).
Let
\(\displaystyle S=\{s_0,s_1,s_2,\ldots\}, \)
where
\(\displaystyle s_0<s_1<\cdots. \)
Then we know that
\(\displaystyle 2\mid s_i \implies s_{i+1}-s_i\le 2, \)
and by the same construction,
\(\displaystyle s_{i+1}-s_i\le 3 \)
for every \(\displaystyle i\).
Let
\(\displaystyle A_n^d= \left|\{1\le i\le n \mid s_i-s_{i-1}=d\}\right|, \qquad d=1,2,3. \)
Without loss of generality, assume that \(\displaystyle s_0=2\).
We claim that for every \(\displaystyle n\),
\(\displaystyle A_n^1\ge A_n^3, \)
and if \(\displaystyle s_n\) is odd, then
\(\displaystyle A_n^1>A_n^3. \)
We prove this by induction.
For \(\displaystyle n=1\) the statement is true.
For \(\displaystyle n+1\), if \(\displaystyle s_n\) is even, then
\(\displaystyle s_{n+1}-s_n\le 2, \)
hence
\(\displaystyle A_{n+1}^3=A_n^3, \)
and we are done.
If \(\displaystyle s_n\) is odd, then
\(\displaystyle A_n^1>A_n^3, \)
hence
\(\displaystyle A_{n+1}^1\ge A_{n+1}^3, \)
and equality can occur only if
\(\displaystyle s_{n+1}-s_n=3, \)
that is, only if \(\displaystyle s_{n+1}\) is even. This completes the induction.
Finally, observe that if \(\displaystyle I\) exists, then
\(\displaystyle I= \lim_{n\to\infty} \frac{n} {1\cdot A_n^1+2\cdot A_n^2+3\cdot A_n^3} \ge \lim_{n\to\infty} \frac{n} {2\cdot(A_n^1+A_n^2+A_n^3)} = \lim_{n\to\infty}\frac{n}{2n} = \frac12. \)
This proves the lower bound and therefore
\(\displaystyle I=\frac12. \)
Statistics:
6 students sent a solution. 7 points: Aravin Peter, Bodor Mátyás, Kis Ágoston (3 students). 5 points: 1 student. 1 point: 1 student. 0 points: 1 student.
Problems in Mathematics of KöMaL, May 2026