Shortlist 2013, C1¶
Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : Poland
Concepts : Principe des tiroirs · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2013 (avec solutions), p. 21 (page 21 du PDF)
Figures reprises du livret officiel de la Shortlist.
Énoncé¶
Let \(n\) be a positive integer. Find the smallest integer \(k\) with the following property: Given any real numbers \(a_1, \ldots, a_d\) such that \(a_1 + a_2 + \cdots + a_d = n\) and \(0 \leq a_i \leq 1\) for \(i = 1, 2, \ldots, d\), it is possible to partition these numbers into \(k\) groups (some of which may be empty) such that the sum of the numbers in each group is at most \(1\).
Indices : les idées clés
- L'exemple : \(2n - 1\) nombres égaux à \(\frac{n}{2n - 1}\) ; deux d'entre eux ne tiennent pas dans un même groupe, donc \(k \geq 2n - 1\).
- Tiroirs et récurrence (solution 1) : si \(d \geq 2n\), les \(n\) sommes \((a_1 + a_2), \ldots, (a_{2n-1} + a_{2n})\) totalisent au plus \(n\), donc l'une d'elles est au plus \(1\) ; on fusionne ces deux nombres.
- Glouton (solution 3) : chaque groupe dépasse \(\frac{1}{2}\), sauf peut-être le dernier, ce qui borne le nombre de groupes.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2013 (trois solutions et deux remarques).
Réponse : \(k = 2n - 1\).
Solution 1¶
Si \(d = 2n - 1\) et \(a_1 = \cdots = a_{2n-1} = \frac{n}{2n - 1}\), chaque groupe d'une telle partition contient au plus un nombre, car \(\frac{2n}{2n - 1} > 1\). Donc \(k \geq 2n - 1\). Il reste à montrer qu'une partition convenable en \(2n - 1\) groupes existe toujours.
Procédons par récurrence sur \(d\). Pour \(d \leq 2n - 1\), c'est évident. Si \(d \geq 2n\), comme
on peut trouver deux nombres \(a_i\), \(a_{i+1}\) tels que \(a_i + a_{i+1} \leq 1\). On « fusionne » ces deux nombres en un nouveau nombre \(a_i + a_{i+1}\). Par hypothèse de récurrence, une partition convenable existe pour les \(d - 1\) nombres \(a_1, \ldots, a_{i-1}, a_i + a_{i+1}, a_{i+2}, \ldots, a_d\). Elle induit une partition convenable de \(a_1, \ldots, a_d\). \(\blacksquare\)
Solution 2¶
On va montrer qu'on peut même découper la suite \(a_1, \ldots, a_d\) en \(2n - 1\) groupes contigus dont chacun a une somme au plus \(1\). Considérons un segment \(S\) de longueur \(n\), découpé en segments \(S_1, \ldots, S_d\) de longueurs \(a_1, \ldots, a_d\), comme sur la figure. Considérons une seconde partition de \(S\) en \(n\) parties égales par \(n - 1\) « points vides ».
Supposons que les \(n - 1\) points vides soient dans les segments \(S_{i_1}, \ldots, S_{i_{n-1}}\) (si un point est à la frontière de deux segments, on choisit celui de droite). Ces \(n - 1\) segments sont distincts, car ils sont de longueur au plus \(1\). Considérons la partition
Dans l'exemple de la figure, cette partition est \(\{a_1, a_2\}, \{a_3\}, \{a_4, a_5\}, \{a_6\}, \varnothing, \{a_7\}, \{a_8, a_9, a_{10}\}\). Dans cette partition, la somme des nombres de chaque groupe est au plus \(1\).
Pour les ensembles \(\{a_{i_t}\}\), c'est évident puisque \(a_{i_t} \leq 1\). Pour les ensembles \(\{a_{i_t + 1}, \ldots, a_{i_{t+1} - 1}\}\), cela vient de ce que les segments correspondants sont entre deux points vides voisins, ou entre une extrémité de \(S\) et le point vide le plus proche ; la somme de leurs longueurs ne dépasse donc pas \(1\). \(\blacksquare\)
Solution 3¶
Mettons d'abord chaque nombre strictement supérieur à \(\frac{1}{2}\) dans un groupe à lui seul. Formons ensuite les autres groupes ainsi : pour chaque groupe, on ajoute de nouveaux \(a_i\) un par un jusqu'à ce que leur somme dépasse \(\frac{1}{2}\). Comme le dernier terme ajouté est au plus \(\frac{1}{2}\), ce groupe a une somme au plus \(1\). On continue jusqu'à avoir utilisé tous les \(a_i\). Le dernier groupe peut avoir une somme inférieure à \(\frac{1}{2}\). Si la somme des nombres des deux derniers groupes est au plus \(1\), on les fusionne en un seul groupe. On obtient finalement \(m\) groupes. Si \(m = 1\), c'est terminé. Sinon, les \(m - 2\) premiers groupes ont des sommes strictement supérieures à \(\frac{1}{2}\), et les deux derniers ont une somme totale strictement supérieure à \(1\). Donc \(n > \frac{m - 2}{2} + 1\), d'où \(m \leq 2n - 1\), comme voulu. \(\blacksquare\)
Remarques¶
Remarque 1. La proposition d'origine demandait la valeur minimale de \(k\) pour \(n = 2\).
Remarque 2. Plus généralement, on peut poser la même question pour des réels entre \(0\) et \(1\) dont la somme est un réel \(r\). La plus petite valeur de \(k\) est alors \(k = \lceil 2r \rceil - 1\), comme le montre la solution 3. Les solutions 1 et 2 donnent la borne un peu moins bonne \(k \leq 2\lceil r \rceil - 1\). C'est en fait la borne optimale pour les partitions en groupes contigus, qui sont celles des deux premières solutions. Pour le voir, supposons \(r\) non entier et posons \(c = \frac{r + 1 - \lceil r \rceil}{1 + \lceil r \rceil}\). On vérifie que \(0 < c < \frac{1}{2}\) et \(\lceil r \rceil (2c) + (\lceil r \rceil - 1)(1 - c) = r\), de sorte que la suite
de \(2\lceil r \rceil - 1\) nombres vérifie les conditions. Pour cette suite, la seule partition convenable en groupes contigus est la partition triviale, qui demande \(2\lceil r \rceil - 1\) groupes.