Shortlist 2014, N3¶
Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : Luxembourg
Concepts : Principe des tiroirs
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é¶
Une pièce est appelée pièce du Cap si sa valeur est \(1/n\) pour un certain entier \(n\) strictement positif. Étant donnée une collection de pièces du Cap de valeur totale au plus \(99 + \frac{1}{2}\), montrer qu'on peut répartir cette collection en au plus \(100\) groupes, chacun de valeur totale au plus \(1\).
Énoncé original (anglais)
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.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2020 C3 ★★☆☆☆ · OIM P4 : Deux compagnies de téléphériques desservent \(n^2\) stations : combien de lignes faut-il pour que deux stations soient reliées par les deux ?
- 2020 G4 ★★☆☆☆ : \(n\) disques disjoints et un point \(O\) quelconque : la somme des distances de \(O\) à un point de chaque disque est au moins \(R_6 + \cdots + R_n\).
- 2017 C4 ★★☆☆☆ · OIM P5 : Dans une rangée de \(N(N + 1)\) joueurs, on peut en garder \(2N\) où chaque paire de tailles consécutives est côte à côte.
- 2017 N3 ★★☆☆☆ : Pour quels \(n\) une suite circulaire de somme non divisible par \(n\) a-t-elle un point de départ sans somme partielle multiple de \(n\) ?