IMO Shortlist

Combinatorics Difficulty 8.8 Shortlist Prove it IMO

For any integer $n \geq 2$ , let $N(n)$ be the maximal number of triples $(a_{i}, b_{i}, c_{i})$ , $i=1, \ldots, N(n)$ , consisting of nonnegative integers $a_{i}, b_{i}$ and $c_{i}$ such that the following two conditions are satisfied:
(1) $a_{i}+b_{i}+c_{i}=n$ for all $i=1, \ldots, N(n)$ ,
(2) If $i \neq j$ , then $a_{i} \neq a_{j}, b_{i} \neq b_{j}$ and $c_{i} \neq c_{j}$ .
Determine $N(n)$ for all $n \geq 2$ .

Solution

Let $n \geq 2$ be an integer and let $\{T_{1}, \ldots, T_{N}\}$ be any set of triples of nonnegative integers satisfying the conditions (1) and (2). Since the $a$ -coordinates are pairwise distinct we have
$\sum_{i=1}^{N} a_{i} \geq \sum_{i=1}^{N}(i-1)=\frac{N(N-1)}{2}$
Analogously,
$\sum_{i=1}^{N} b_{i} \geq \frac{N(N-1)}{2} \quad \text{ and } \quad \sum_{i=1}^{N} c_{i} \geq \frac{N(N-1)}{2} .$
Summing these three inequalities and applying (1) yields
$3 \frac{N(N-1)}{2} \leq \sum_{i=1}^{N} a_{i}+\sum_{i=1}^{N} b_{i}+\sum_{i=1}^{N} c_{i}=\sum_{i=1}^{N}\left(a_{i}+b_{i}+c_{i}\right)=n N,$
hence $3 \frac{N-1}{2} \leq n$ and, consequently,
$N \leq\left\lfloor\frac{2 n}{3}\right\rfloor+1$
By constructing examples, we show that this upper bound can be attained, so $N(n)=\left\lfloor\frac{2 n}{3}\right\rfloor+1$ .
We distinguish the cases $n=3 k-1, n=3 k$ and $n=3 k+1$ for $k \geq 1$ and present the extremal examples in form of a table.

$n=3 k-1$
$\left\lfloor\frac{2 n}{3}\right\rfloor+1=2 k$
$a_{i}$	$b_{i}$	$c_{i}$
0	$k+1$	$2 k-2$
1	$k+2$	$2 k-4$
$\vdots$	$\vdots$	$\vdots$
$k-1$	$2 k$	0
$k$	0	$2 k-1$
$k+1$	1	$2 k-3$
$\vdots$	$\vdots$	$\vdots$
$2 k-1$	$k-1$	1

$n=3 k$
$\left\lfloor\frac{2 n}{3}\right\rfloor+1=2 k+1$
$a_{i}$	$b_{i}$	$c_{i}$
0	$k$	$2 k$
1	$k+1$	$2 k-2$
$\vdots$	$\vdots$	$\vdots$
$k$	$2 k$	0
$k+1$	0	$2 k-1$
$k+2$	1	$2 k-3$
$\vdots$	$\vdots$	$\vdots$
$2 k$	$k-1$	1

$n=3 k+1$
$\left\lfloor\frac{2 n}{3}\right\rfloor+1=2 k+1$
$a_{i}$	$b_{i}$	$c_{i}$
0	$k$	$2 k+1$
1	$k+1$	$2 k-1$
$\vdots$	$\vdots$	$\vdots$
$k$	$2 k$	1
$k+1$	0	$2 k$
$k+2$	1	$2 k-2$
$\vdots$	$\vdots$	$\vdots$
$2 k$	$k-1$	2

It can be easily seen that the conditions (1) and (2) are satisfied and that we indeed have

\left\lfloor\frac{2 n}{3}\right\rfloor+1

triples in each case.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.