Shortlist 2022, C4¶
Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Israel
Concepts : Invariants et monovariants · Congruences, théorèmes de Fermat et d'Euler · Récurrence et constructions récursives · Polynômes à coefficients entiers
Solution officielle : Shortlist officielle 2022 (avec solutions), p. 28 (page 30 du PDF)
Énoncé¶
Let \(n > 3\) be a positive integer. Suppose that \(n\) children are arranged in a circle, and \(n\) coins are distributed between them (some children may have no coins). At every step, a child with at least \(2\) coins may give \(1\) coin to each of their immediate neighbours on the right and left. Determine all initial distributions of coins from which it is possible that, after a finite number of steps, each child has exactly one coin.
Indices : les idées clés
- Réponse : les répartitions telles que \(\sum_{i=1}^{n} i c_i \equiv \frac{n(n+1)}{2} \pmod{n}\), où \(c_i\) est le nombre de pièces initial de l'enfant \(i\).
- Invariants et monovariants : \(\sum i c_i \bmod n\) est invariant (condition nécessaire) ; une quantité strictement monotone garantit qu'un processus s'arrête.
- Congruences : l'invariant est une somme pondérée modulo \(n\), indépendante de la numérotation choisie.
- Récurrence et constructions récursives : le lemme du « passage à longue distance » se prouve par récurrence sur la distance, puis on réduit pas à pas l'« irrégularité » \(M\).
- Polynômes à coefficients entiers (solution 2) : coder la répartition par un polynôme modulo \(x^n - 1\) ; chaque étape ajoute un multiple de \((x-1)^2\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2022 (deux solutions).
Réponse : ce sont exactement les répartitions telles que
où \(c_i\) désigne le nombre de pièces de l'enfant \(i\) au départ.
Solution 1¶
Condition nécessaire. Numérotons les enfants \(1, \ldots, n\) (indices modulo \(n\)). Une étape consiste à diminuer un \(c_i\) de \(2\) et à augmenter \(c_{i-1}\) et \(c_{i+1}\) de \(1\). Comme \((i-1) - 2i + (i+1) = 0\), la quantité \(\sum_{i=1}^{n} i c_i \pmod{n}\) est un invariant du processus. Pour que les enfants finissent avec une pièce chacun, il faut donc
Précision ajoutée : comme \(\sum c_i = n\), remplacer \(i\) par \(i + t\) ne change pas cette somme modulo \(n\) ; la condition ne dépend donc pas de l'enfant choisi comme numéro \(1\).
Condition suffisante. Partons d'une répartition quelconque vérifiant la condition. D'abord, tant qu'un enfant \(i \neq n\) a plus d'une pièce, on le fait donner (l'enfant \(n\) ne fait rien). Au bout d'un certain nombre d'étapes, cela devient impossible, car aucun enfant sauf peut-être l'enfant \(n\) n'a plus d'une pièce. Pour le voir, on utilise un monovariant : la quantité \(\sum_{i=1}^{n-1} i(n-i) c_i\), entière et positive, diminue de \(2\) à chaque étape (car, avec \(w_i = i(n-i)\) et \(w_0 = w_n = 0\), on a \(w_{i-1} + w_{i+1} - 2w_i = -2\)). (Le livret propose \(\sum_{i=1}^{n-1} i^2 c_i\), en invoquant \((i-1)^2 + (i+1)^2 > 2i^2\) ; mais cette quantité diminue quand l'enfant \(n-1\) donne, car son voisin \(n\) n'est pas compté. Nous la remplaçons par un monovariant correct.)
On atteint donc un état de la forme \((z_1, \ldots, z_{n-1}, M)\) avec \(z_i \in \{0, 1\}\). On l'appelle état semi-uniforme d'irrégularité \(M\). Dans la suite, on note \(1^k\) un bloc de \(k\) enfants consécutifs ayant chacun une pièce.
Lemme (passage à longue distance). Si une suite d'enfants consécutifs possède les pièces \(a, 1^k, b, 1^k, c\) avec \(b \geq 2\), on peut, par une suite d'étapes, atteindre l'état \(a+1, 1^k, b-2, 1^k, c+1\). On dit que l'enfant \(b\) fait un passage à longue distance.
Preuve. Par récurrence sur \(k\). Pour \(k = 0\), c'est l'opération de l'énoncé. Pour \(k = 1\) : l'enfant à \(b\) pièces donne, puis ses deux voisins donnent, puis l'enfant à \(b\) pièces donne de nouveau. Pour \(k \geq 2\) : l'enfant à \(b\) pièces donne, puis ses deux voisins donnent, ce qui produit
Laissant de côté les enfants à \(a\), \(b\) et \(c\) pièces, on fait donner chaque enfant ayant \(2\) pièces jusqu'à ce qu'il n'y en ait plus. On obtient
(Le livret écrit \(1^{k-2}\) ; le décompte des pièces donne \(1^{k-1}\).) Par hypothèse de récurrence (avec \(k - 1\)), l'enfant à \(b\) pièces peut faire passer une pièce à chacun des deux enfants à \(0\) pièce, ce qui donne l'état voulu. \(\square\)
Affirmation. On peut atteindre un état semi-uniforme d'irrégularité \(M \leq 2\).
Preuve. Supposons \(M \geq 3\) (le livret écrit « \(M > 3\) »). Comme il n'y a que \(n\) pièces, au moins deux enfants ont \(0\) pièce. Considérons l'arc du cercle délimité par les deux tels enfants les plus proches de l'enfant à \(M\) pièces ; il est de la forme
Si \(a = b\), par le lemme, l'enfant à \(M\) pièces fait passer une pièce à chacun des deux enfants à \(0\) pièce, ce qui donne un état semi-uniforme de plus petite irrégularité \(M - 2\).
Sinon, supposons par exemple \(a > b\). L'enfant à \(M\) pièces fait un passage à longue distance vers les deux enfants situés à distance \(b + 1\) de lui, et l'on obtient un état de la forme (avec \(\alpha = a - b - 1\), \(\beta = b\))
Les enfants du bloc \(1^c\) de droite n'ont plus à jouer ; on ne considère que la partie gauche.
- Si \(\alpha < \beta\), l'enfant à \(2\) pièces fait un passage à longue distance vers l'enfant à \(0\) pièce à sa gauche et vers un enfant à \(1\) pièce à sa droite ; on obtient un nouvel état de la forme \(0, 1^{\alpha}, 2, 1^{\beta'}, M - 2\) avec \(\beta' < \beta\). Comme \(\beta\) ne peut pas décroître indéfiniment, on finit par avoir \(\alpha \geq \beta\).
- Si \(\alpha = \beta\), l'enfant à \(2\) pièces fait un passage vers l'enfant à \(M - 2\) pièces et vers l'enfant à \(0\) pièce : on obtient un état semi-uniforme d'irrégularité \(M - 1\).
-
Si \(\alpha > \beta\) (le livret écrit par erreur « \(\alpha < \beta\) » à cet endroit), l'enfant à \(2\) pièces fait un passage vers l'enfant à \(M-2\) pièces et vers un enfant à \(1\) pièce, ce qui donne un état de la forme
\[0,\ 1^x,\ 2,\ 1^y,\ 0,\ 1^z,\ M-1.\]On regarde alors seulement la portion \(0, 1^x, 2, 1^y, 0\) entre les deux enfants à \(0\) pièce. On fait faire à l'enfant à \(2\) pièces un passage à longue distance vers l'enfant à \(0\) pièce le plus proche et un autre enfant. Si cet autre enfant avait \(1\) pièce, on obtient une nouvelle portion de la même forme, strictement plus courte. Donc, à un moment, l'autre enfant a lui aussi \(0\) pièce, et l'on atteint un état semi-uniforme d'irrégularité \(M - 1\).
Dans tous les cas, l'irrégularité diminue, ce qui prouve l'affirmation. \(\square\)
Conclusion. On peut atteindre un état semi-uniforme d'irrégularité \(M \leq 2\). Si \(M = 1\), chaque enfant a une pièce, comme voulu. Sinon \(M = 2\) : un enfant a \(0\) pièce, un enfant a \(2\) pièces et tous les autres ont \(1\) pièce. L'état de départ vérifiait l'invariant \(\sum i c_i \equiv \frac{n(n+1)}{2} \pmod{n}\), donc l'état actuel aussi. Numérotons les enfants de sorte que l'enfant à \(M\) pièces soit l'enfant \(n\), et soit \(k\) l'enfant à \(0\) pièce. Alors
donc \(k \equiv 0 \pmod{n}\). C'est impossible, car seul l'enfant à \(M\) pièces a un numéro divisible par \(n\). On ne peut donc pas aboutir à un état d'irrégularité \(2\), et la condition est suffisante. \(\blacksquare\)
Solution 2¶
On code la suite \((c_i)\) par le polynôme \(p(x) = \sum_i c_i x^i\). La nature cyclique du problème invite à travailler modulo \(x^n - 1\). Une étape effectuée par l'enfant \(i\) revient à ajouter \(x^{i-1}(x-1)^2 = x^{i-1} - 2x^i + x^{i+1}\) au polynôme (le livret écrit \(x^i(x-1)^2\), ce qui revient à décaler les indices), et l'on veut atteindre le polynôme \(q(x) = 1 + x + \cdots + x^{n-1}\) (modulo \(x^n - 1\)). Comme on n'ajoute que des multiples de \((x-1)^2\), ce n'est possible que si \(p(x) \equiv q(x)\) modulo l'idéal engendré par \(x^n - 1\) et \((x-1)^2\), c'est-à-dire
car \(\frac{x^n-1}{x-1} = 1 + x + \cdots + x^{n-1} \equiv n \pmod{x-1}\). Cela équivaut à \(p(1) = q(1)\) (ce qui traduit simplement qu'il y a \(n\) pièces) et \(p'(1) \equiv q'(1) \pmod{n}\), ce qui est exactement l'invariant de la solution 1. (Précision ajoutée : cette approche par les polynômes à coefficients entiers établit la condition nécessaire ; la suffisance se montre comme dans la solution 1.) \(\blacksquare\)