IMO 2023 · Problem 5

Let \(n\) be a positive integer. A Japanese triangle consists of \(1+2+\cdots+n\) circles arranged in an equilateral triangular shape such that for each \(i=1,2,\ldots,n\), the \(i^{\mathrm{th}}\) row contains exactly \(i\) circles, exactly one of which is coloured red. A ninja path in a Japanese triangle is a sequence of \(n\) circles obtained by starting in the top row, then repeatedly going from a circle to one of the two circles immediately below it and finishing in the bottom row. Here is an example of a Japanese triangle with \(n=6\), along with a ninja path in that triangle containing two red circles.

\[ \begin{array}{c} {\color{red}\bigcirc}\\[-5pt] \quad\searrow\\[-5pt] {\color{red}\bigcirc}\quad\bigcirc\\[-5pt] \quad\swarrow\\[-5pt] \bigcirc\quad\bigcirc\quad{\color{red}\bigcirc}\\[-5pt] \quad\searrow\\[-5pt] \bigcirc\quad\bigcirc\quad{\color{red}\bigcirc}\quad\bigcirc\\[-5pt] \quad\swarrow\\[-5pt] \bigcirc\quad\bigcirc\quad\bigcirc\quad{\color{red}\bigcirc}\quad\bigcirc\\[-5pt] \swarrow\quad\\[-5pt] {\color{red}\bigcirc}\quad\bigcirc\quad\bigcirc\quad\bigcirc\quad\bigcirc\quad\bigcirc\\ n=6 \end{array} \]

In terms of \(n\), find the greatest \(k\) such that in each Japanese triangle there is a ninja path containing at least \(k\) red circles.

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{k=\lfloor\log_2 n\rfloor+1.} \]

Equivalently, \(k\) is the unique positive integer satisfying \(2^{k-1}\le n<2^k\).

Solution

Number the circles in each row from left to right. Give the circle in row \(i\), column \(j\), the coordinates \[ (x,y)=(j-1,i-j). \] Thus \(x,y\) are nonnegative integers, its row number is \(x+y+1\), and a downward step increases exactly one coordinate by \(1\).

Consequently, a circle \((x,y)\) can reach a circle \((x',y')\) by downward steps if and only if \[ x\le x'\quad\text{and}\quad y\le y'. \] Call a sequence of distinct red circles increasing in both coordinates a chain. Every chain can be joined by downward steps and extended to a complete ninja path. Conversely, the red circles on any ninja path form a chain. Therefore the largest number of red circles on a ninja path equals the largest size of a chain.

We first establish a bound for sets containing no two comparable circles; call such a set an antichain.

Claim. If an antichain contains \(s\) circles, every one of them lies in row \(s\) or below.

Indeed, arrange their coordinates so that \[ x_1<x_2<\cdots<x_s. \] The \(x\)-coordinates are distinct, since two circles with equal \(x\)-coordinates would be comparable. Incomparability also gives \[ y_1>y_2>\cdots>y_s. \] Since these coordinates are nonnegative integers, \[ x_t\ge t-1,\qquad y_t\ge s-t. \] Thus the row number of the \(t\)-th circle is \[ x_t+y_t+1\ge s, \] proving the claim.

Now consider any Japanese triangle, and let \(M\) be the largest size of a red chain. Label each red circle by the largest size of a red chain ending at that circle. These labels lie in \(\{1,\ldots,M\}\). If one red circle precedes another, the latter has a strictly larger label, because we can append it to a longest chain ending at the former. Hence circles with the same label form an antichain.

The nonempty label classes therefore partition the red circles into \(q\le M\) antichains. Order these antichains as \(A_1,\ldots,A_q\) by their smallest row numbers \[ r_1<r_2<\cdots<r_q. \] Write \(s_t=|A_t|\) and \[ S_0=0,\qquad S_t=s_1+\cdots+s_t. \] The claim gives \(s_t\le r_t\). Moreover, every red circle in a row before \(r_t\) belongs to one of \(A_1,\ldots,A_{t-1}\). There is one red circle in each such row, so \[ r_t-1\le S_{t-1}. \] Combining these inequalities yields \[ S_t=S_{t-1}+s_t \le S_{t-1}+r_t \le 2S_{t-1}+1. \] Starting from \(S_0=0\), induction gives \(S_t\le 2^t-1\). In particular, \[ n=S_q\le 2^q-1\le 2^M-1. \] If \(2^{k-1}\le n<2^k\), this forces \(M\ge k\). Thus every Japanese triangle has a ninja path containing at least \(k\) red circles.

To show that this bound is sharp, partition the rows into the \(k\) blocks \[ 2^t,\ 2^t+1,\ \ldots,\ \min(2^{t+1}-1,n), \qquad t=0,1,\ldots,k-1. \] In row \(i\) of block \(t\), colour the circle in column \[ j_i=2^{t+1}-i \] red. This is a valid column: the inequalities \(2^t\le i\le 2^{t+1}-1\) imply \[ 1\le j_i\le i. \]

Within each block, the columns of the red circles strictly decrease as the row number increases. Along a ninja path, however, the column number either stays unchanged or increases by \(1\) at every step. Therefore a ninja path can contain at most one red circle from each block, and hence at most \(k\) red circles altogether.

The universal bound and this construction prove the answer for every positive integer \(n\), including \(n=1\).

The solution was checked against the official IMO shortlist solutions.