Aller au contenu

Shortlist 2023, A1

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

Concepts : Partie entière et majorations · AM-GM et moyennes

Solution officielle : Shortlist officielle 2023 (avec solutions), p. 11 (page 13 du PDF)

Énoncé

Professor Oak is feeding his \(100\) Pokémon. Each Pokémon has a bowl whose capacity is a positive real number of kilograms. These capacities are known to Professor Oak. The total capacity of all the bowls is \(100\) kilograms. Professor Oak distributes \(100\) kilograms of food in such a way that each Pokémon receives a non-negative integer number of kilograms of food (which may be larger than the capacity of their bowl). The dissatisfaction level of a Pokémon who received \(N\) kilograms of food and whose bowl has a capacity of \(C\) kilograms is equal to \(|N - C|\).

Find the smallest real number \(D\) such that, regardless of the capacities of the bowls, Professor Oak can distribute the food in a way that the sum of the dissatisfaction levels over all the \(100\) Pokémon is at most \(D\).

Indices : les idées clés
  • Un exemple extrême pour la minoration : \(99\) gamelles de \(0{,}5\) kg et une de \(50{,}5\) kg forcent une insatisfaction d'au moins \(0{,}5\) par Pokémon.
  • Partie entière et majorations : on donne d'abord \(\lfloor C_i \rfloor\) à chacun ; il reste \(R = F_1 + \cdots + F_{100}\) kg, un entier, où \(F_i\) est la partie fractionnaire de \(C_i\).
  • Arrondir vers le haut ceux qui ont les plus grandes parties fractionnaires (solution 1) : la moyenne des petites \(F_i\) est au plus la moyenne de toutes.
  • AM-GM et moyennes : \(R(100 - R) \leq 50^2\) donne la borne \(50\).
  • Méthode probabiliste (solution 2) : l'espérance de l'insatisfaction totale d'une distribution aléatoire vaut \(2R(100 - R)/100 \leq 50\).
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2023 (deux solutions).

Réponse : \(D = 50\).

Solution 1

Minoration. Considérons la situation où \(99\) gamelles ont une capacité de \(0{,}5\) kg et la dernière une capacité de \(50{,}5\) kg. Quelle que soit la distribution, chaque Pokémon reçoit un nombre entier de kilogrammes, donc son insatisfaction est au moins \(0{,}5\). L'insatisfaction totale est donc au moins \(50\), ce qui prouve \(D \geq 50\).

Majoration. Montrons que, quelles que soient les capacités, le professeur peut toujours distribuer la nourriture avec une insatisfaction totale d'au plus \(50\). Numérotons les Pokémon de \(1\) à \(100\) et notons \(C_i > 0\) la capacité de la gamelle du \(i\)-ième. Par hypothèse, \(C_1 + C_2 + \cdots + C_{100} = 100\). Notons \(F_i = C_i - \lfloor C_i \rfloor\) la partie fractionnaire de \(C_i\). Quitte à renuméroter, on peut supposer \(F_1 \leq F_2 \leq \cdots \leq F_{100}\).

Voici une stratégie : le professeur commence par donner \(\lfloor C_i \rfloor\) kg au \(i\)-ième Pokémon. Soit

\[R = 100 - \lfloor C_1 \rfloor - \lfloor C_2 \rfloor - \cdots - \lfloor C_{100} \rfloor = F_1 + F_2 + \cdots + F_{100} \geq 0\]

la quantité restante (c'est un entier). Il donne ensuite un kilogramme supplémentaire aux \(R\) Pokémon numérotés \(100 - R + 1, \ldots, 100\), c'est-à-dire ceux qui ont les \(R\) plus grandes valeurs de \(F_i\). Il a ainsi distribué \(100\) kg. L'insatisfaction totale vaut

\[d = F_1 + \cdots + F_{100-R} + (1 - F_{100-R+1}) + \cdots + (1 - F_{100}),\]

que l'on réécrit

\[d = 2(F_1 + \cdots + F_{100-R}) + R - (F_1 + \cdots + F_{100}) = 2(F_1 + \cdots + F_{100-R}).\]

Comme \(F_1 \leq \cdots \leq F_{100}\), la moyenne de \(F_1, \ldots, F_{100-R}\) n'est pas plus grande que celle de \(F_1, \ldots, F_{100}\). Donc

\[d \leq 2(100 - R) \cdot \frac{F_1 + \cdots + F_{100}}{100} = 2 \cdot \frac{R(100 - R)}{100}.\]

Enfin, par AM-GM, \(R(100 - R) \leq \frac{100^2}{2^2}\), ce qui donne \(d \leq 50\).

Il existe donc toujours une distribution d'insatisfaction totale au plus \(50\), d'où \(D \leq 50\), et finalement \(D = 50\). \(\blacksquare\)

Solution 2

On garde les notations de la solution 1 (sans supposer les \(F_i\) ordonnés) : \(C_i > 0\), \(F_i = C_i - \lfloor C_i \rfloor\) et \(R = F_1 + \cdots + F_{100} = 100 - \lfloor C_1 \rfloor - \cdots - \lfloor C_{100} \rfloor\), qui est un entier. La minoration \(D \geq 50\) est la même.

On utilise la méthode probabiliste. Considérons toutes les distributions où le \(i\)-ième Pokémon reçoit \(\lfloor C_i \rfloor + \varepsilon_i\) kg, avec \(\varepsilon_i \in \{0, 1\}\) et \(\varepsilon_1 + \cdots + \varepsilon_{100} = R\). Il y en a \(\binom{100}{R}\). Choisissons-en une uniformément au hasard ; autrement dit, pour chaque \(i\),

\[\varepsilon_i = \begin{cases} 0 & \text{avec probabilité } \frac{100 - R}{100}, \\ 1 & \text{avec probabilité } \frac{R}{100}. \end{cases}\]

L'espérance de l'insatisfaction du \(i\)-ième Pokémon est

\[\frac{100 - R}{100}\big(C_i - \lfloor C_i \rfloor\big) + \frac{R}{100}\big(\lfloor C_i \rfloor + 1 - C_i\big) = \frac{100 - R}{100} F_i + \frac{R}{100}(1 - F_i).\]

Par linéarité, l'espérance de l'insatisfaction totale est

\[\sum_{i=1}^{100} \left(\frac{100 - R}{100} F_i + \frac{R}{100}(1 - F_i)\right) = \frac{100 - R}{100} \cdot R + \frac{R}{100} \cdot (100 - R) = 2 \cdot \frac{R(100 - R)}{100}.\]

Comme dans la solution 1, c'est au plus \(50\) (AM-GM). Il existe donc au moins une distribution dont l'insatisfaction totale est au plus \(50\), d'où \(D = 50\). \(\blacksquare\)