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é¶
Montrer que, pour tout entier \(n\) strictement positif, l'ensemble \(\{2, 3, 4, \ldots, 3n + 1\}\) peut être partagé en \(n\) triplets de sorte que les nombres de chaque triplet soient les longueurs des côtés d'un triangle obtusangle.
Énoncé original (anglais)
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,
Ensuite, pour tout \(i \in [t + 2, n + 1]\), posons \(A_i = \{i, n + t + i, 2n + i\}\). Tous ces ensembles sont disjoints, et
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,
donc ce triangle est obtusangle. La preuve est complète. \(\blacksquare\)
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2025 C3 ★★☆☆☆ : Retirer des segments équilibrés d'une rangée de boules noires et blanches : combien de retraits pour garder exactement \(2k\) boules ?
- 2022 C6 ★★★☆☆ : On fusionne des cailloux pris en quantités égales dans deux tas : combien de tas au minimum ?
- 2010 C4 ★★★☆☆ · OIM P5 : Six piles de pièces et deux types de coups : peut-on obtenir \(2010^{2010^{2010}}\) pièces sur la dernière pile ?
- 2009 C3 ★★★☆☆ : Deux récurrences pilotées par la même suite de \(0\) et de \(1\), lue dans des sens opposés, aboutissent au même terme.