Aller au contenu

Shortlist 2011, A5

Domaine : Algèbre · Difficulté : ★★★☆☆ · Proposé par : non indiqué

Concepts : Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2011 (avec solutions), p. 20 (page 21 du PDF)

Énoncé

Prove that for every positive integer \(n\), the set \(\{2, 3, 4, \ldots, 3n + 1\}\) can be partitioned into \(n\) triples in such a way that the numbers from each triple are the lengths of the sides of some obtuse triangle.

Indices : les idées clés
  • Un lemme de décalage : si \(a < b < c\) forment un triplet obtus, alors \(\{a, b + x, c + x\}\) aussi pour tout \(x > 0\).
  • Récurrence forte avec \(t = \lfloor n/2 \rfloor\) : on décale de \(n - t\) une partition de \([2, 3t + 1]\), et l'on complète avec les triplets \(\{i, n + t + i, 2n + i\}\) pour \(i \in [t + 2, n + 1]\).
  • Vérification : \((2n + i)^2 - (n + t + i)^2 = (n - t)(3n + t + 2i) > (n + 1)^2 \geq i^2\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2011 (une solution).

Solution

Dans toute la solution, \([a, b]\) désigne l'ensemble \(\{a, a + 1, \ldots, b\}\). On dit que \(\{a, b, c\}\) est un triplet obtus si \(a\), \(b\), \(c\) sont les côtés d'un triangle obtusangle.

Montrons par récurrence sur \(n\) qu'il existe une partition de \([2, 3n + 1]\) en \(n\) triplets obtus \(A_i\) (\(2 \leq i \leq n + 1\)) de la forme \(A_i = \{i, a_i, b_i\}\). Pour \(n = 1\), il suffit de prendre \(A_2 = \{2, 3, 4\}\). Pour l'hérédité, on a besoin du lemme simple suivant.

Lemme. Supposons que les nombres \(a < b < c\) forment un triplet obtus, et soit \(x\) un nombre positif quelconque. Alors le triplet \(\{a, b + x, c + x\}\) est aussi obtus.

Preuve. Les nombres \(a < b + x < c + x\) sont les côtés d'un triangle, car \((c + x) - (b + x) = c - b < a\). Ce triangle est obtusangle, car \((c + x)^2 - (b + x)^2 = (c - b)(c + b + 2x) > (c - b)(c + b) > a^2\). \(\square\)

Passons à l'hérédité. Soit \(n > 1\), et posons \(t = \lfloor n/2 \rfloor < n\). Par hypothèse de récurrence, il existe une partition de \([2, 3t + 1]\) en \(t\) triplets obtus \(A'_i = \{i, a'_i, b'_i\}\) (\(i \in [2, t + 1]\)). Pour les mêmes valeurs de \(i\), posons \(A_i = \{i, a'_i + (n - t), b'_i + (n - t)\}\). Ces triplets sont évidemment disjoints, et obtus par le lemme. De plus,

\[\bigcup_{i=2}^{t+1} A_i = [2, t + 1] \cup [n + 2, n + 2t + 1].\]

Ensuite, pour tout \(i \in [t + 2, n + 1]\), posons \(A_i = \{i, n + t + i, 2n + i\}\). Tous ces ensembles sont disjoints, et

\[\bigcup_{i=t+2}^{n+1} A_i = [t + 2, n + 1] \cup [n + 2t + 2, 2n + t + 1] \cup [2n + t + 2, 3n + 1], \quad \text{donc} \quad \bigcup_{i=2}^{n+1} A_i = [2, 3n + 1].\]

Il reste à prouver que le triplet \(A_i\) est obtus pour tout \(i \in [t + 2, n + 1]\). Comme \((2n + i) - (n + t + i) = n - t < t + 2 \leq i\), les éléments de \(A_i\) sont les côtés d'un triangle. Ensuite,

\[(2n + i)^2 - (n + t + i)^2 = (n - t)(3n + t + 2i) \geq \frac{n}{2} \cdot \big(3n + 3(t + 1) + 1\big) > \frac{n}{2} \cdot \frac{9n}{2} \geq (n + 1)^2 \geq i^2,\]

donc ce triangle est obtusangle. La preuve est complète. \(\blacksquare\)