IMO 2009 Shortlist C2
For any integer n ≥ 2, let N(n) be the maximal number of triples (ai,bi,ci), i = 1,...,N(n), consisting of nonnegative i...
Category: Combinatorics
Problem
For any integer n ≥ 2, let N(n) be the maximal number of triples (ai,bi,ci), i = 1,...,N(n), consisting of nonnegative integers ai,bi and ci such that the following two conditions are satis- fied: (1) ai + bi + ci = n for all i = 1,...,N(n), (2) If i 6= j, then ai 6= aj,bi 6= bj and ci 6= cj. Determine N(n) for all n ≥ 2. Comment. The original problem was formulated for m-tuples instead for triples. The numbers N(m,n) are then defined similarly to N(n) in the case m = 3. The numbers N(3,n) and N(n,n) should be determined. The case m = 3 is the same as in the present problem. The upper bound for N(n,n) can be proved by a simple generalization. The construction of a set of triples attaining the bound can be easily done by induction from n to n + 2.