Shortlist 2009, C2¶
Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Romania
Concepts : Double comptage · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2009 (avec solutions), p. 27 (page 29 du PDF)
Énoncé¶
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\).
Indices : les idées clés
- Double comptage de la somme de toutes les coordonnées : les \(a_i\) distincts donnent \(\sum a_i \geq \frac{N(N - 1)}{2}\), et de même pour \(b\) et \(c\), tandis que le total vaut \(nN\).
- Majoration : \(3\frac{N - 1}{2} \leq n\), donc \(N \leq \left\lfloor \frac{2n}{3} \right\rfloor + 1\).
- Constructions explicites selon \(n\) modulo \(3\), en deux blocs où \(a\) et \(b\) croissent de \(1\) et \(c\) décroît de \(2\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2009 (une solution et deux remarques).
Réponse : \(N(n) = \left\lfloor \frac{2n}{3} \right\rfloor + 1\).
Solution¶
Soit \(n \geq 2\) un entier et soit \(\{T_1, \ldots, T_N\}\) un ensemble quelconque de triplets d'entiers positifs ou nuls vérifiant les conditions (1) et (2). Comme les premières coordonnées sont deux à deux distinctes, on a
De même,
En sommant ces trois inégalités et en appliquant (1), on obtient
donc \(3\frac{N - 1}{2} \leq n\) et, par conséquent,
Montrons par des exemples que cette borne est atteinte, de sorte que \(N(n) = \left\lfloor \frac{2n}{3} \right\rfloor + 1\). On distingue les cas \(n = 3k - 1\), \(n = 3k\) et \(n = 3k + 1\) pour \(k \geq 1\), et l'on présente les exemples extrémaux sous forme de tableaux.
Cas \(n = 3k - 1\), avec \(\left\lfloor \frac{2n}{3} \right\rfloor + 1 = 2k\) :
| \(a_i\) | \(b_i\) | \(c_i\) |
|---|---|---|
| \(0\) | \(k + 1\) | \(2k - 2\) |
| \(1\) | \(k + 2\) | \(2k - 4\) |
| \(\vdots\) | \(\vdots\) | \(\vdots\) |
| \(k - 1\) | \(2k\) | \(0\) |
| \(k\) | \(0\) | \(2k - 1\) |
| \(k + 1\) | \(1\) | \(2k - 3\) |
| \(\vdots\) | \(\vdots\) | \(\vdots\) |
| \(2k - 1\) | \(k - 1\) | \(1\) |
Cas \(n = 3k\), avec \(\left\lfloor \frac{2n}{3} \right\rfloor + 1 = 2k + 1\) :
| \(a_i\) | \(b_i\) | \(c_i\) |
|---|---|---|
| \(0\) | \(k\) | \(2k\) |
| \(1\) | \(k + 1\) | \(2k - 2\) |
| \(\vdots\) | \(\vdots\) | \(\vdots\) |
| \(k\) | \(2k\) | \(0\) |
| \(k + 1\) | \(0\) | \(2k - 1\) |
| \(k + 2\) | \(1\) | \(2k - 3\) |
| \(\vdots\) | \(\vdots\) | \(\vdots\) |
| \(2k\) | \(k - 1\) | \(1\) |
Cas \(n = 3k + 1\), avec \(\left\lfloor \frac{2n}{3} \right\rfloor + 1 = 2k + 1\) :
| \(a_i\) | \(b_i\) | \(c_i\) |
|---|---|---|
| \(0\) | \(k\) | \(2k + 1\) |
| \(1\) | \(k + 1\) | \(2k - 1\) |
| \(\vdots\) | \(\vdots\) | \(\vdots\) |
| \(k\) | \(2k\) | \(1\) |
| \(k + 1\) | \(0\) | \(2k\) |
| \(k + 2\) | \(1\) | \(2k - 2\) |
| \(\vdots\) | \(\vdots\) | \(\vdots\) |
| \(2k\) | \(k - 1\) | \(2\) |
On voit facilement que les conditions (1) et (2) sont vérifiées, et qu'on a bien \(\left\lfloor \frac{2n}{3} \right\rfloor + 1\) triplets dans chaque cas. \(\blacksquare\)
Remarques¶
Remarque 1. Le problème original était formulé pour des \(m\)-uplets au lieu de triplets. Les nombres \(N(m, n)\) se définissent alors comme \(N(n)\) dans le cas \(m = 3\). Il fallait déterminer les nombres \(N(3, n)\) et \(N(n, n)\). Le cas \(m = 3\) est le même que dans le présent problème. La borne supérieure de \(N(n, n)\) se prouve par une généralisation simple. La construction d'un ensemble de \(n\)-uplets atteignant la borne se fait facilement par récurrence de \(n\) à \(n + 2\).
Remarque 2. Un joli modèle combinatoire est donné par un triangle équilatéral découpé en \(n^2\) triangles équilatéraux égaux par \(n - 1\) parallèles équidistantes à chacun de ses trois côtés. Deux fous placés en deux sommets quelconques des petits triangles se menacent s'ils sont sur une même parallèle. Le problème revient à déterminer le plus grand nombre de fous qu'on peut placer sans que deux se menacent. On peut associer à un fou trois coordonnées \(a\), \(b\), \(c\) : les nombres de côtés de petits triangles qui le séparent de chacun des côtés du grand triangle. On voit facilement que la somme de ces coordonnées vaut toujours \(n\), ce qui répond aux conditions.