Shortlist 2009, C5¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Netherlands
Concepts : Jeux et stratégies gagnantes · Invariants et monovariants
Solution officielle : Shortlist officielle 2009 (avec solutions), p. 33 (page 35 du PDF)
Énoncé¶
Five identical empty buckets of \(2\)-liter capacity stand at the vertices of a regular pentagon. Cinderella and her wicked Stepmother go through a sequence of rounds: At the beginning of every round, the Stepmother takes one liter of water from the nearby river and distributes it arbitrarily over the five buckets. Then Cinderella chooses a pair of neighboring buckets, empties them into the river, and puts them back. Then the next round begins. The Stepmother's goal is to make one of these buckets overflow. Cinderella's goal is to prevent this. Can the wicked Stepmother enforce a bucket overflow?
Indices : les idées clés
- Invariant à maintenir : deux seaux voisins vides, leurs deux voisins de contenu total au plus \(1\), et le dernier seau au plus \(1\).
- Un litre ajouté : \(y_0 + y_1 + y_2 + y_3 \leq 2\) donne \(y_0 + y_2 \leq 1\) ou \(y_1 + y_3 \leq 1\), et Cendrillon vide la paire qui rétablit l'invariant (stratégie).
- Pièges : la stratégie gloutonne (retirer le plus d'eau possible) échoue ; et pour une capacité \(b < 2\), la belle-mère gagne.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2009 (deux solutions, des remarques et une variante).
Réponse : non, la belle-mère ne peut pas forcer un débordement, et Cendrillon peut jouer indéfiniment.
Solution 1¶
Dans toute la suite, on note les cinq seaux \(B_0\), \(B_1\), \(B_2\), \(B_3\) et \(B_4\), où \(B_k\) est voisin des seaux \(B_{k-1}\) et \(B_{k+1}\) (\(k = 0, 1, 2, 3, 4\)), tous les indices étant pris modulo \(5\). Cendrillon fait en sorte que les trois conditions suivantes soient vérifiées au début de chaque tour :
(1) Deux seaux voisins (disons \(B_1\) et \(B_2\)) sont vides.
(2) Les deux seaux voisins de ces seaux (ici \(B_0\) et \(B_3\)) ont un contenu total d'au plus \(1\).
(3) Le seau restant (ici \(B_4\)) a un contenu d'au plus \(1\).
Ces conditions sont évidemment vraies au début du premier tour, quand tous les seaux sont vides.
Supposons que Cendrillon réussisse à les maintenir jusqu'au début du \(r\)-ième tour (\(r \geq 1\)). Notons \(x_k\) (\(k = 0, 1, 2, 3, 4\)) le contenu du seau \(B_k\) au début de ce tour, et \(y_k\) le contenu correspondant après que la belle-mère a réparti son litre d'eau.
D'après les conditions, on peut supposer \(x_1 = x_2 = 0\), \(x_0 + x_3 \leq 1\) et \(x_4 \leq 1\). Comme la belle-mère ajoute un litre, on en conclut que \(y_0 + y_1 + y_2 + y_3 \leq 2\). Cette inégalité implique \(y_0 + y_2 \leq 1\) ou \(y_1 + y_3 \leq 1\). Par symétrie, on ne considère que le second cas.
Cendrillon vide alors les seaux \(B_0\) et \(B_4\).
Au début du tour suivant, \(B_0\) et \(B_4\) sont vides (la condition (1) est remplie) ; grâce à \(y_1 + y_3 \leq 1\), la condition (2) est remplie ; enfin, comme \(x_2 = 0\), on a aussi \(y_2 \leq 1\) (la condition (3) est remplie).
Cendrillon peut donc bien maintenir les trois conditions (1) à (3) au début du \((r + 1)\)-ième tour. Par récurrence, elle les maintient au début de chaque tour. En particulier, elle maintient le contenu de chaque seau à au plus \(1\) litre. Les seaux de \(2\) litres ne débordent donc jamais. \(\blacksquare\)
Solution 2¶
Montrons que Cendrillon peut maintenir les deux conditions suivantes, et donc empêcher les seaux de déborder :
(1') Deux seaux non voisins quelconques contiennent au total au plus \(1\).
(2') Le contenu total des cinq seaux est au plus \(\frac{3}{2}\).
On utilise les mêmes notations que dans la première solution. Les deux conditions sont encore évidemment vraies au début. Supposons que Cendrillon les ait maintenues jusqu'au début du \(r\)-ième tour. Une paire de seaux non voisins \((B_i, B_{i+2})\), \(i = 0, 1, 2, 3, 4\), est dite critique si \(y_i + y_{i+2} > 1\). D'après la condition (2'), après la répartition de l'eau par la belle-mère, on a \(y_0 + y_1 + y_2 + y_3 + y_4 \leq \frac{5}{2}\). Donc
et il existe donc une paire de seaux non voisins qui n'est pas critique, disons \((B_0, B_2)\). Si les deux paires \((B_3, B_0)\) et \((B_2, B_4)\) sont critiques, on doit avoir \(y_1 < \frac{1}{2}\), et Cendrillon peut vider les seaux \(B_3\) et \(B_4\). Il ne reste alors évidemment aucune paire critique, et le contenu total de tous les seaux est \(y_1 + (y_0 + y_2) \leq \frac{3}{2}\). Les conditions (1') et (2') sont donc remplies.
Supposons maintenant, sans perte de généralité, que la paire \((B_3, B_0)\) n'est pas critique. Si dans ce cas \(y_0 \leq \frac{1}{2}\), alors l'une des inégalités \(y_0 + y_1 + y_2 \leq \frac{3}{2}\) et \(y_0 + y_3 + y_4 \leq \frac{3}{2}\) doit être vraie. Mais alors Cendrillon peut vider respectivement \(B_3\) et \(B_4\), ou \(B_1\) et \(B_2\), et remplir évidemment les conditions.
Considérons enfin le cas \(y_0 > \frac{1}{2}\). Par \(y_0 + y_1 + y_2 + y_3 + y_4 \leq \frac{5}{2}\), l'une au moins des paires \((B_1, B_3)\) et \((B_2, B_4)\) n'est pas critique. Sans perte de généralité, soit \((B_1, B_3)\) cette paire. Comme la paire \((B_3, B_0)\) n'est pas critique et que \(y_0 > \frac{1}{2}\), on doit avoir \(y_3 \leq \frac{1}{2}\). Mais alors, comme précédemment, Cendrillon peut maintenir les deux conditions au début du tour suivant en vidant soit \(B_1\) et \(B_2\), soit \(B_4\) et \(B_0\). \(\blacksquare\)
Remarques¶
Sur les approches gloutonnes. Une approche naturelle pour Cendrillon serait une stratégie gloutonne, par exemple : toujours retirer le plus d'eau possible du système. On prouve facilement que cette stratégie empêche des seaux de capacité \(\frac{5}{2}\) de déborder : si, avant le coup de la belle-mère, on a \(x_0 + x_1 + x_2 + x_3 + x_4 \leq \frac{3}{2}\), alors après son coup on a \(Y = y_0 + y_1 + y_2 + y_3 + y_4 \leq \frac{5}{2}\). Si Cendrillon vide les deux seaux voisins de plus grand contenu total, elle retire au moins \(\frac{2Y}{5}\), et les seaux restants contiennent au plus \(\frac{3}{5} \cdot Y \leq \frac{3}{2}\).
Mais la stratégie gloutonne n'est en général pas assez forte pour régler le problème, comme le montre l'exemple suivant.
- Dans une phase initiale, la belle-mère amène tous les seaux (après son coup) à un contenu d'au moins \(\frac{1}{2} - 2\epsilon\), où \(\epsilon\) est un nombre strictement positif arbitrairement petit. Elle y parvient en répartissant toujours son litre de sorte que tous les seaux aient le même contenu. Après son \(r\)-ième coup, le contenu total de chaque seau est alors \(c_r\), avec \(c_1 = 1\) et \(c_{r+1} = 1 + \frac{3}{5} \cdot c_r\), donc \(c_r = \frac{5}{2} - \frac{3}{2} \cdot \left(\frac{3}{5}\right)^{r-1}\). Le contenu de chaque seau tend donc bien vers \(\frac{1}{2}\) (par valeurs inférieures). En particulier, deux seaux voisins quelconques ont un contenu total strictement inférieur à \(1\), ce qui permet à la belle-mère de toujours remplir à nouveau les seaux que Cendrillon vient de vider, puis de répartir le reste de l'eau également sur tous les seaux.
- Après cette phase, la stratégie gloutonne fait face à une situation comme \(\left(\frac{1}{2} - 2\epsilon, \frac{1}{2} - 2\epsilon, \frac{1}{2} - 2\epsilon, \frac{1}{2} - 2\epsilon, \frac{1}{2} - 2\epsilon\right)\) et laisse une situation de la forme \((x_0, x_1, x_2, x_3, x_4) = \left(\frac{1}{2} - 2\epsilon, \frac{1}{2} - 2\epsilon, \frac{1}{2} - 2\epsilon, 0, 0\right)\).
- La belle-mère peut alors ajouter les quantités \(\left(0, \frac{1}{4} + \epsilon, \epsilon, \frac{3}{4} - 2\epsilon, 0\right)\) pour obtenir la situation \((y_0, y_1, y_2, y_3, y_4) = \left(\frac{1}{2} - 2\epsilon, \frac{3}{4} - \epsilon, \frac{1}{2} - \epsilon, \frac{3}{4} - 2\epsilon, 0\right)\).
- Maintenant, \(B_1\) et \(B_2\) sont les seaux voisins de plus grand contenu total, donc la stratégie gloutonne les vide et donne \((x_0, x_1, x_2, x_3, x_4) = \left(\frac{1}{2} - 2\epsilon, 0, 0, \frac{3}{4} - 2\epsilon, 0\right)\).
- La belle-mère ajoute alors \(\left(\frac{5}{8}, 0, 0, \frac{3}{8}, 0\right)\), ce qui donne \(\left(\frac{9}{8} - 2\epsilon, 0, 0, \frac{9}{8} - 2\epsilon, 0\right)\).
- La stratégie gloutonne ne peut plus vider qu'un des deux seaux non vides, et au tour suivant la belle-mère ajoute son litre à l'autre seau et le porte à \(\frac{17}{8} - 2\epsilon\), c'est-à-dire qu'il déborde.
Une variante plus difficile. Cinq seaux vides identiques de capacité \(b\) sont placés aux sommets d'un pentagone régulier, avec les mêmes règles. Déterminer toutes les capacités \(b\) pour lesquelles la belle-mère peut forcer un débordement.
Solution de la variante. La réponse est \(b < 2\).
La preuve précédente montre que, pour tout \(b \geq 2\), la belle-mère ne peut pas forcer de débordement. Si maintenant \(b < 2\), soit \(R\) un entier strictement positif tel que \(b < 2 - 2^{1-R}\). Pendant les \(R\) premiers tours, la belle-mère s'assure que l'un au moins des seaux (non voisins) \(B_1\) et \(B_3\) contient au moins \(1 - 2^{1-r}\) au début du tour \(r\) (\(r = 1, 2, \ldots, R\)). C'est trivial pour \(r = 1\), et si c'est vrai au début du tour \(r\), elle peut remplir le seau qui contient au moins \(1 - 2^{1-r}\) litres avec \(2^{-r}\) litres supplémentaires, et mettre le reste de son eau, \(1 - 2^{-r}\) litres, dans l'autre seau. Comme Cendrillon ne peut retirer l'eau que de l'un au plus de ces deux seaux, l'autre seau garde son contenu au tour suivant.
Au début du \(R\)-ième tour, il y a \(1 - 2^{1-R}\) litres dans \(B_1\) ou \(B_3\). La belle-mère met tout son litre dans ce seau et provoque un débordement, puisque \(b < 2 - 2^{1-R}\).