Maths Olympiad Prep

Library / /13 of 16

Combinatorics Difficulty 8.8 Shortlist Prove it IMO

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

Solution

Let n2n \geq 2 be an integer and let {T1,,TN}\{T_{1}, \ldots, T_{N}\} be any set of triples of nonnegative integers satisfying the conditions (1) and (2). Since the aa-coordinates are pairwise distinct we have
i=1Naii=1N(i1)=N(N1)2 \sum_{i=1}^{N} a_{i} \geq \sum_{i=1}^{N}(i-1)=\frac{N(N-1)}{2}
Analogously,
i=1NbiN(N1)2 and i=1NciN(N1)2. \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
3N(N1)2i=1Nai+i=1Nbi+i=1Nci=i=1N(ai+bi+ci)=nN, 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 3N12n3 \frac{N-1}{2} \leq n and, consequently,
N2n3+1 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)=2n3+1N(n)=\left\lfloor\frac{2 n}{3}\right\rfloor+1.
We distinguish the cases n=3k1,n=3kn=3 k-1, n=3 k and n=3k+1n=3 k+1 for k1k \geq 1 and present the extremal examples in form of a table.

n=3k1n=3 k-1
2n3+1=2k\left\lfloor\frac{2 n}{3}\right\rfloor+1=2 k
aia_{i}bib_{i}cic_{i}
0k+1k+12k22 k-2
1k+2k+22k42 k-4
\vdots\vdots\vdots
k1k-12k2 k0
kk02k12 k-1
k+1k+112k32 k-3
\vdots\vdots\vdots
2k12 k-1k1k-11
n=3kn=3 k
2n3+1=2k+1\left\lfloor\frac{2 n}{3}\right\rfloor+1=2 k+1
aia_{i}bib_{i}cic_{i}
0kk2k2 k
1k+1k+12k22 k-2
\vdots\vdots\vdots
kk2k2 k0
k+1k+102k12 k-1
k+2k+212k32 k-3
\vdots\vdots\vdots
2k2 kk1k-11
n=3k+1n=3 k+1
2n3+1=2k+1\left\lfloor\frac{2 n}{3}\right\rfloor+1=2 k+1
aia_{i}bib_{i}cic_{i}
0kk2k+12 k+1
1k+1k+12k12 k-1
\vdots\vdots\vdots
kk2k2 k1
k+1k+102k2 k
k+2k+212k22 k-2
\vdots\vdots\vdots
2k2 kk1k-12

It can be easily seen that the conditions (1) and (2) are satisfied and that we indeed have 2n3+1\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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.