Aller au contenu

Shortlist 2012, C4

Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : non indiqué

Concepts : Jeux et stratégies gagnantes · Invariants et monovariants · Principe extrémal

Solution officielle : Shortlist officielle 2012 (avec solutions), p. 22 (page 22 du PDF)

Énoncé

Players \(A\) and \(B\) play a game with \(N \geq 2012\) coins and \(2012\) boxes arranged around a circle. Initially \(A\) distributes the coins among the boxes so that there is at least \(1\) coin in each box. Then the two of them make moves in the order \(B, A, B, A, \ldots\) by the following rules:

  • On every move of his \(B\) passes \(1\) coin from every box to an adjacent box.
  • On every move of hers \(A\) chooses several coins that were not involved in \(B\)'s previous move and are in different boxes. She passes every chosen coin to an adjacent box.

Player \(A\)'s goal is to ensure at least \(1\) coin in each box after every move of hers, regardless of how \(B\) plays and how many moves are made. Find the least \(N\) that enables her to succeed.

Indices : les idées clés
  • Généraliser à \(n \geq 7\) boîtes : la réponse est \(N = 2n - 2\), soit \(4022\) pour \(n = 2012\).
  • Stratégie de \(A\) pour \(N = 2n - 2\) : maintenir une répartition « régulière » (\(n - 2\) boîtes à \(2\) pièces, \(2\) boîtes à \(1\) pièce) en renvoyant chaque fois la seconde pièce d'une boîte rouge dans la direction opposée.
  • Monovariant pour \(N \leq 2n - 3\) : un « arc » de \(\ell\) boîtes contenant au plus \(2\ell - 3\) pièces existe, et \(B\) peut faire diminuer strictement son nombre de pièces à chaque tour, jusqu'à vider une boîte.
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2012 (une solution).

Réponse : \(N_{\min} = 4022\).

Solution

On raisonne pour un nombre \(n \geq 7\) de boîtes au lieu de \(2012\), et l'on montre que le minimum cherché est \(N = 2n - 2\). Pour \(n = 2012\), cela donne \(N_{\min} = 4022\).

a) Si \(N = 2n - 2\), le joueur \(A\) peut atteindre son but. Qu'elle commence avec une répartition régulière : \(n - 2\) boîtes avec \(2\) pièces et \(2\) boîtes avec \(1\) pièce. On appelle les boîtes de ces deux types rouges et blanches respectivement. Montrons qu'à son premier coup, \(A\) peut à nouveau obtenir une répartition régulière, quel que soit le premier coup \(M\) de \(B\). Elle agit selon que la situation \(\mathcal{S}\) suivante se produit après \(M\) ou non : la répartition initiale contient une boîte rouge \(R\) ayant deux voisines blanches, et \(R\) ne reçoit aucune pièce de ses voisines lors du coup \(M\).

Supposons que \(\mathcal{S}\) ne se produise pas. Exactement l'une des pièces \(c_1\) et \(c_2\) d'une boîte rouge \(X\) donnée est impliquée dans \(M\), disons \(c_1\). Si \(M\) passe \(c_1\) à la voisine de droite de \(X\), \(A\) passe \(c_2\) à sa voisine de gauche, et inversement. En faisant cela pour toutes les boîtes rouges, \(A\) effectue un coup légal \(M'\). Les coups \(M\) et \(M'\) combinés déplacent les deux pièces de chaque boîte rouge dans des directions opposées. Donc, une fois \(M\) et \(M'\) effectués, chaque voisine d'une boîte rouge \(X\) contient exactement \(1\) pièce venant de \(X\). Toute boîte ayant une voisine rouge est donc non vide après \(M'\). S'il existe initialement une boîte \(X\) ayant deux voisines blanches (\(X\) est alors rouge et unique), \(X\) reçoit une pièce d'au moins l'une d'elles lors du coup \(M\), puisque \(\mathcal{S}\) ne se produit pas. Cette pièce n'est pas impliquée dans \(M'\), donc \(X\) est aussi non vide après \(M'\). De plus, chaque boîte \(Y\) a cédé son contenu initial après \(M\) et \(M'\). Une voisine rouge de \(Y\) lui ajoute \(1\) pièce ; une voisine blanche lui ajoute au plus \(1\) pièce, car elle n'est pas impliquée dans \(M'\). Chaque boîte contient donc \(1\) ou \(2\) pièces après \(M'\). Comme \(N = 2n - 2\), une telle répartition est régulière.

Supposons maintenant que \(\mathcal{S}\) se produise après \(M\). Alors \(A\) ne touche pas à la boîte rouge exceptionnelle \(R\). Pour toutes les autres boîtes rouges, elle procède comme dans le cas précédent, et effectue ainsi un coup légal \(M''\). La boîte \(R\) ne reçoit aucune pièce de ses voisines lors des deux coups, donc elle contient \(1\) pièce après \(M''\). Comme ci-dessus, \(M\) et \(M''\) combinés font passer exactement \(1\) pièce de chaque boîte rouge autre que \(R\) à chacune de ses voisines. Toute boîte autre que \(R\) a une voisine rouge différente de \(R\), donc toutes les boîtes sont non vides après \(M''\). Ensuite, chaque boîte \(Y\) autre que \(R\) perd son contenu initial après \(M\) et \(M''\). Une voisine rouge de \(Y\) lui ajoute au plus \(1\) pièce ; une voisine blanche aussi, car elle ne participe pas à \(M''\). Chaque boîte a donc \(1\) ou \(2\) pièces après \(M''\), et la répartition obtenue est régulière.

Le joueur \(A\) peut appliquer cette stratégie indéfiniment ; donc \(N = 2n - 2\) lui permet de réussir.

b) Si \(N \leq 2n - 3\), le joueur \(B\) peut obtenir une boîte vide après un coup de \(A\). Soit \(\alpha\) un ensemble de \(\ell\) boîtes consécutives contenant au total \(N(\alpha)\) pièces. On dit que \(\alpha\) est un arc si \(\ell \leq n - 2\) et \(N(\alpha) \leq 2\ell - 3\). Cette dernière condition impose \(\ell \geq 2\). De plus, si les deux extrémités de \(\alpha\) sont des boîtes non vides, alors \(N(\alpha) \geq 2\), donc \(N(\alpha) \leq 2\ell - 3\) impose \(\ell \geq 3\). Remarquons aussi que si une extrémité \(X\) de \(\alpha\) contient plus de \(1\) pièce, en ignorant \(X\) on obtient un arc plus court. Il s'ensuit que tout arc contient un arc dont les extrémités ont chacune au plus \(1\) pièce.

Numérotons les boîtes \(1, 2, \ldots, n\) dans le sens des aiguilles d'une montre, et supposons que les boîtes \(1, 2, \ldots, \ell\) forment un arc \(\alpha\), avec \(\ell \leq n - 2\) et \(N(\alpha) \leq 2\ell - 3\). Supposons aussi que les \(n \geq 7\) boîtes soient toutes non vides. Alors \(B\) peut jouer de sorte qu'un arc \(\alpha'\) avec \(N(\alpha') < N(\alpha)\) apparaisse après toute réponse de \(A\).

On peut supposer qu'il y a exactement \(1\) pièce dans les boîtes \(1\) et \(\ell\), d'après la remarque précédente. Que \(B\) passe \(1\) pièce dans le sens inverse des aiguilles d'une montre depuis la boîte \(1\) et depuis la boîte \(n\), et dans le sens des aiguilles d'une montre depuis chacune des autres boîtes. Il reste alors \(N(\alpha) - 2\) pièces dans les boîtes de \(\alpha\). De plus, comme \(3 \leq \ell \leq n - 2\), la boîte \(\ell\) contient exactement \(1\) pièce \(c\), celle reçue de la boîte \(\ell - 1\).

Supposons que le coup suivant \(M\) de \(A\) fasse entrer \(k \leq 2\) pièces dans les boîtes \(1, 2, \ldots, \ell\) depuis les autres boîtes. Seules les boîtes \(1\) et \(\ell\) peuvent recevoir de telles pièces, au plus \(1\) chacune. Si \(k < 2\), après le coup \(M\) les boîtes \(1, 2, \ldots, \ell\) forment un arc \(\alpha'\) avec \(N(\alpha') < N(\alpha)\). Si \(k = 2\), alors \(M\) ajoute une pièce à la boîte \(\ell\). De plus, \(M\) ne déplace pas la pièce \(c\) hors de \(\ell\), car \(c\) est impliquée dans le coup précédent de \(B\). En résumé, les boîtes \(1, 2, \ldots, \ell\) contiennent \(N(\alpha)\) pièces comme avant, donc elles forment un arc ; mais il y a maintenant \(2\) pièces à l'extrémité \(\ell\) de l'arc. En ignorant \(\ell\), on obtient un arc plus court \(\alpha'\) avec \(N(\alpha') < N(\alpha)\).

Considérons une répartition initiale quelconque sans boîte vide. Comme \(N \leq 2n - 3\), au moins \(3\) boîtes y contiennent exactement \(1\) pièce. Comme \(n \geq 7\), deux d'entre elles sont les extrémités d'un arc \(\alpha\). Le joueur \(B\) peut donc faire le coup décrit ci-dessus, qui mène à un arc \(\alpha'\) avec \(N(\alpha') < N(\alpha)\) après la réponse de \(A\). Si toutes les boîtes de la nouvelle répartition sont non vides, il peut recommencer, et ainsi de suite. Comme \(N(\alpha)\) ne peut pas décroître indéfiniment, une boîte vide apparaît après un coup de \(A\). \(\blacksquare\)