IMO 2007 Problem 6

Let $ n$ be a positive integer. Consider

$S=\left\{ (x,y,z) \mid x,y,z \in \{ 0, 1, \ldots, n\}, x+y+z > 0 \right\}$

as a set of $(n+1)^3-1$ points in the three-dimensional space. Determine the smallest possible number of planes, the union of which contains $S$ but does not include $ (0,0,0)$.

Author: Gerhard Wöginger, Netherlands

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

Solution:

The key point is to prove that you can't do it without $3n$ planes. We follow Alon and Furedi's usage of Combinatorial NullStellensatz in 1993 for almost the same problem with $m$ rather than $3$ dimensions and $n=1$.

Let $f(x,y,z)$ be the product of the planes that contains $S$ but not $(0,0,0)$. Then

$g(x,y,z):=(n!)^3f(x,y,z)-f(0,0,0)\prod_{i\in[n]}(i-x)\prod_{j\in[n]}(j-y)\prod_{k\in[n]}(k-z)$

is zero for any $(x,y,z)\in\{0,1,\dots,n\}^3$.

Suppose $\deg(f)<3n$, then the highest-degree term of $g(x,y,z)$ is $x^ny^nz^n$. Thus by Combinatorial NullStellensatz, for $X=Y=Z=\{0,1,\dots,n\}$ there must be some $(x,y,z)\in X\times Y\times Z$ such that $g(x,y,z)\ne 0$. This contradicts with the assumption.

$\diamond$

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$