Competition problem — Combinatorics

Combinatorics Difficulty 8.0 Shortlist Prove it Singapore

Let $n$ be an integer $\ge 2$ . Let $S$ be a set of triples of nonnegative integers $(a, b, c)$ such that $a + b + c = n$ and if $(a, b, c)$ and $(a', b', c')$ are distinct triples in $S$ , then $a \ne a'$ , $b \ne b'$ and $c \ne c'$ . Find the maximum value of $|S|$ .

Solution

Suppose $|S| = s$ . Then $\sum_{(a, b, c) \in S} a \ge \sum_{i=0}^{s-1} i = \frac{s(s-1)}{2}$ . Likewise $\sum_S b \ge \frac{s(s-1)}{2}$ and $\sum_S c \ge \frac{s(s-1)}{2}$ . Therefore
$\frac{3s(s-1)}{2} \le \sum_{S} a + b + c = ns \Rightarrow s \le \left\lfloor \frac{2n}{3} \right\rfloor + 1.$
The following shows the bound can be attained.


n = 3k - 1			n = 3k			n = 3k + 1
$a$	$b$	$c$	$a$	$b$	$c$	$a$	$b$	$c$
0	$k + 1$	$2k - 2$	0	$k$	$2k$	0	$k$	$2k + 1$
1	$k + 2$	$2k - 4$	1	$k + 1$	$2k - 2$	1	$k + 1$	$2k - 1$
...	...	...	...	...	...	...	...	...
$k - 1$	$2k$	0	$k$	$2k$	0	$k$	$2k$	1
$k$	0	$2k - 1$	$k + 1$	0	$2k - 1$	$k + 1$	0	$2k$
$k + 1$	1	$2k - 3$	$k + 2$	1	$2k - 3$	$k + 2$	1	$2k - 2$
...	...	...	...	...	...	...	...	...
$2k - 1$	$k - 1$	1	$2k$	$k - 1$	1	$2k$	$k - 1$	2

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 reproduced verbatim; metadata (topic, difficulty) added by this project.