IMO 2023 Problem 5

 

Let $n$ be a positive integer. A Japanese triangle consists of $1 + 2 + \dots + n$ circles arranged in an equilateral triangular shape such that for each $i = 1$, $2$, $\dots$, $n$, the $i^{th}$ row contains exactly $i$ circles, exactly one of which is colored 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.

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.

===========================================

Solution:

The answer is $f(n)=\lfloor \log_2 n\rfloor+1$.

Denote the $j^{th}$ circle in the $i^{th}$ row by $(i,j)$.

Upper bound:

We construct an infinite Japanese triangle below:

$(1,1)\\(2,1), (3,3)\\(4,1), (5,3), (6,5), (7,7)\\ \vdots\\ (2^k,1), (2^k+1,3), \ldots, (2^{k+1}-1,2^{k+1}-1)\\ \vdots$

We call each line above a stride. Clearly any finite Japanese triangle truncated from above has exactly $f(n)$ strides and no ninja path contains multiple red circles from the same stride.

Lower bound:

Given the upper bound and the monotonicity of $f(n)$, it suffices to prove the lower bound only for $n$ as a power of two.

Denote by $a(x,y)$ the maximum number of red circles contained in any ninja path ending at $(x,y)$, and let $s(n)=a(n,1)+a(n,2)+\ldots+a(n,n)$. It suffices to show that $s(n)\ge n\log_2n+1$, because that implies that some $a(n,m)$ is at least $\lceil \frac{1+n\log_2 n}{n} \rceil=1+\log_2 n$. We have

$$a(n,m)=\begin{cases}\max\{a(n-1,m-1),a(n-1,m)\}+1 & (n,m)\text{ is red} \\ \max\{a(n-1,m-1),a(n-1,m)\} & \text{otherwise}\\ \end{cases}.$$

Observe that $s(n)\ge s(n-1)+1+\max_m{a(n-1,m)}\ge s(n-1)+1+\lceil 1+\log_2 {\left(n-1\right)} \rceil$, the latter by inductive hypothesis. So inductively if $n$ is a power of two, $s(2n)\ge s(n)+n+n\left(1+\log_2 n\right) \ge n\log_2n+1+2n+n\log_2 n=2n\left(\log_2 (2n)\right)+1$.

$\diamond$