Problem A. 922. (December 2025)
A. 922. Fix two positive integers \(\displaystyle a\) and \(\displaystyle b\). Let \(\displaystyle n\) be a positive integer, and let \(\displaystyle T\) be a black–white coloring of the cells of an \(\displaystyle an\times bn\) grid, containing at least two white cells. Csigusz the snail starts on a white cell, visits all white cells exactly once, and then returns to the starting cell, always moving between side-adjacent white cells. He then notices that he was able to do this in exactly one way (that is, once he made his first move, there was a unique way to complete the cycle). Let \(\displaystyle \mathcal{T}_n\) denote the set of all colorings \(\displaystyle T\) satisfying this property, and let \(\displaystyle \phi(T)\) denote the number of white lattice points in \(\displaystyle T\). Show that
\(\displaystyle L=\lim_{n\to \infty}\frac{\max_{T\in \mathcal{T}_n} \phi(T)}{abn^2}\)
exists for every choice of positive integers \(\displaystyle a\) and \(\displaystyle b\), and determine the value of \(\displaystyle L\).
Proposed by Márton Lovas and Csongor Beke, Cambridge
(7 pont)
Deadline expired on January 12, 2026.
We show that the value of \(\displaystyle L\) exists for all \(\displaystyle a,b\geq 1\), and that \(\displaystyle L=1\).
First, we examine the case \(\displaystyle a=1\), \(\displaystyle b=1\), that is, when our board is square-shaped. We present a construction for \(\displaystyle n = 4k+7\), where \(\displaystyle k\in \mathbb{N}\).
We show that in the case \(\displaystyle k=2\) this tiling is valid. For an arbitrary board, and for some already drawn path segments, we call used those cells which are either black or white and are already touched by two drawn path segments (running between cells).
Then observe that if a white cell is adjacent to two used cells, then it is uniquely determined from which two neighboring cells Csigusz enters and leaves this cell.
Accordingly, for the empty board on the left, the red path segments shown on the board on the right are uniquely determined (above and below the secondary diagonal the white cells have two used neighbors, which results in new used cells, and so on).
It is easy to see that from here the completion is unique (since the path must form a single closed cycle), and it exists; these are marked in blue in the figure. A similar construction works for any \(\displaystyle k\in \mathbb{N}\).
The number of white cells is
\(\displaystyle \phi(T_{k}) = (7+4k)^2 - (4 + (4k+3) + 2k + 2(k+1)) = n^2 - l(n) \)
where \(\displaystyle l\) is a linear function of \(\displaystyle n=4k+7\). If we place one, two, or three black strips above and to the right of a construction of size \(\displaystyle 4k+7\), then we obtain constructions for \(\displaystyle 4k+8\), \(\displaystyle 4k+9\), and \(\displaystyle 4k+10\), respectively. That is, for all sufficiently large \(\displaystyle n\),
\(\displaystyle \max_{T\in \mathcal{T}_n} \phi(T) \geq n^2-l(n)-6n. \)
Thus the desired limit indeed exists, and
\(\displaystyle \lim_{n\to \infty} \frac{\max_{T\in \mathcal{T}_n} \phi(T)}{n^2} \geq \lim_{n\to \infty} \frac{n^2-l(n)-6n}{n^2} = 1-\lim_{n\to \infty} \frac{l(n)+6n}{n^2} = 1. \)
Since \(\displaystyle \phi(T)\leq n^2\), in the case \(\displaystyle a=1\), \(\displaystyle b=1\) we have \(\displaystyle L=1\).
For the general construction, we first modify the square board we found: turn the bottom-left corner into a black cell, surround the entire board on all sides with a black strip, but let there be two holes (white cells) in the black strip, adjacent to the original bottom-left corner (denote these two cells by \(\displaystyle A\) and \(\displaystyle B\)).
Thus we obtain a board in which there is exactly one way to reach \(\displaystyle B\) from \(\displaystyle A\) while visiting every white cell. Tile an \(\displaystyle a\times b\) rectangular grid with such boards, separating them by black strips of thickness \(\displaystyle m\), as shown in the figure (for the case \(\displaystyle a=3\), \(\displaystyle b=4\)).
Finally, drill tunnels into the black strips, thereby connecting the outermost cells of the boards in series as shown in the figure. It is clear that for example when \(\displaystyle m=10\), this can certainly be done. Csigusz is forced to visit all boards, since each contains a white cell, and he can do so in only one way. The construction works similarly for arbitrary values of \(\displaystyle a\) and \(\displaystyle b\).
Thus, from an \(\displaystyle n\times n\) board we have constructed a suitable board of size
\(\displaystyle [(n+m)\cdot a + m]\times [(n+m)\cdot b+m]. \)
Its aspect ratio is not yet exactly correct, but independently of \(\displaystyle n\), by attaching at most \(\displaystyle a+b\) black strips to the right or top side of the new board, we obtain a construction in which the number of black cells is at most
\(\displaystyle abl(n) + (a+b)g(n), \)
where \(\displaystyle l\) and \(\displaystyle g\) are linear functions of \(\displaystyle n\) (in the sum we included the black strips of thickness at most \(\displaystyle m\leq 10\) originating from the square construction and those inserted between them, as well as those placed on the right and top). Hence in this case as well, \(\displaystyle L\) exists and \(\displaystyle L=1\).
Statistics:
8 students sent a solution. 7 points: Aravin Peter, Forrai Boldizsár, Kis Ágoston, Vödrös Dániel László, Xiaoyi Mo. 1 point: 2 students. Unfair, not evaluated: 1 solutions.
Problems in Mathematics of KöMaL, December 2025