Shortlist 2014, N3¶
Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : Luxembourg
Concepts : Principe des tiroirs · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2014 (avec solutions), p. 72 (page 73 du PDF)
Problème 5 de l'OIM 2014
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2014, où il était le problème 5 (jour 2).
Énoncé¶
A coin is called a Cape Town coin if its value is \(1/n\) for some positive integer \(n\). Given a collection of Cape Town coins of total value at most \(99 + \frac{1}{2}\), prove that it is possible to split this collection into at most \(100\) groups each of total value at most \(1\).
Indices : les idées clés
- Généraliser : toute collection de valeur totale au plus \(N - \frac{1}{2}\) se répartit en \(N\) groupes de valeur au plus \(1\).
- Fusionner des pièces dont la somme est de la forme \(\frac{1}{k}\) ; à la fin, il y a au plus une pièce \(\frac{1}{k}\) pour \(k\) pair et au plus \(k - 1\) pour \(k\) impair.
- Tiroirs et algorithme glouton : le groupe \(G_k\) reçoit les pièces \(\frac{1}{2k - 1}\) et \(\frac{1}{2k}\) ; puis chaque petite pièce va dans un groupe de valeur au plus \(1 - \frac{1}{2N}\), qui existe par la moyenne.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2014 (une solution et deux remarques).
Solution¶
On va montrer que, pour tout entier \(N \geq 1\), toute collection de pièces de Cape Town de valeur totale au plus \(N - \frac{1}{2}\) peut être répartie en \(N\) groupes de valeur totale au plus \(1\) chacun. L'énoncé est le cas particulier \(N = 100\).
Commençons par quelques préparatifs. Si plusieurs pièces ont ensemble une valeur totale de la forme \(\frac{1}{k}\) pour un entier \(k \geq 1\), on peut les fusionner en une seule nouvelle pièce. Si la nouvelle collection peut être répartie comme voulu, la collection de départ le peut aussi.
Chaque fusion diminue le nombre total de pièces ; on arrive donc à un moment où aucune fusion n'est possible. À ce moment, pour tout \(k\) pair, il y a au plus une pièce de valeur \(\frac{1}{k}\) (sinon on pourrait en fusionner deux), et pour tout \(k > 1\) impair, il y a au plus \(k - 1\) pièces de valeur \(\frac{1}{k}\) (sinon on pourrait en fusionner \(k\)).
Ensuite, chaque pièce de valeur \(1\) doit former un groupe à elle seule ; s'il y a \(d\) telles pièces, on peut les retirer de la collection et remplacer \(N\) par \(N - d\). On peut donc supposer désormais qu'il n'y a pas de pièce de valeur \(1\).
On répartit enfin les pièces ainsi. Pour chaque \(k = 1, 2, \ldots, N\), on met toutes les pièces de valeurs \(\frac{1}{2k - 1}\) et \(\frac{1}{2k}\) dans un groupe \(G_k\) ; la valeur totale de \(G_k\) ne dépasse pas
Il reste à placer les « petites » pièces, de valeur inférieure à \(\frac{1}{2N}\) ; on les ajoute une par une. À chaque étape, prenons une petite pièce restante. La valeur totale des pièces déjà dans les groupes est au plus \(N - \frac{1}{2}\), donc il existe un groupe de valeur totale au plus \(\frac{1}{N}\left(N - \frac{1}{2}\right) = 1 - \frac{1}{2N}\) ; on peut donc y mettre notre petite pièce. En procédant ainsi, on finit par placer toutes les pièces. \(\blacksquare\)
Remarques¶
Remarque 1. On peut modifier l'algorithme, du moins l'étape qui répartit les pièces de valeur au moins \(\frac{1}{2N}\). Par exemple, on peut mettre dans \(G_k\) toutes les pièces de valeurs \(\frac{1}{(2k - 1)2^s}\) pour tous les entiers \(s \geq 0\). On vérifie facilement que leur valeur totale ne dépasse pas non plus \(1\).
Remarque 2. La proposition d'origine contenait une autre partie, qui demandait de montrer que la répartition peut être impossible si la valeur totale des pièces est au plus \(100\). Il existe de nombreux exemples, par exemple \(98\) pièces de valeur \(1\), une pièce de valeur \(\frac{1}{2}\), deux pièces de valeur \(\frac{1}{3}\) et quatre pièces de valeur \(\frac{1}{5}\). Le comité a jugé cette partie moins adaptée à la compétition.