Shortlist 2015, C4¶

Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Finland

Concepts : Jeux et stratégies gagnantes

Solution officielle : Shortlist officielle 2015 (avec solutions), p. 30 (page 31 du PDF)

Énoncé¶

Let \(n\) be a positive integer. Two players \(A\) and \(B\) play a game in which they take turns choosing positive integers \(k \leq n\). The rules of the game are:

(i) A player cannot choose a number that has been chosen by either player on any previous turn.

(ii) A player cannot choose a number consecutive to any of those the player has already chosen on any previous turn.

(iii) The game is a draw if all numbers have been chosen; otherwise the player who cannot choose a number anymore loses the game.

The player \(A\) takes the first turn. Determine the outcome of the game, assuming that both players use optimal strategies.

Indices : les idées clés

Jeux et stratégies gagnantes : \(B\) commence par prendre \(n\) (ou, par symétrie, l'extrémité éloignée du premier choix de \(A\)) ; un argument de comptage de « composantes » montre qu'il peut alors toujours rejouer.
Empêcher la nulle : la partie n'est nulle que si \(A\) prend tous les nombres impairs ; \(B\) en « vole » un au bon moment.
Symétrie et partie imaginaire (remarque 1) : retourner le segment \([1, a]\) ramène tout premier coup de \(A\) au cas où \(A\) joue \(1\).

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2015 (une solution et deux remarques).

Réponse. La partie est nulle pour \(n = 1, 2, 4, 6\) ; dans tous les autres cas, \(B\) gagne.

Solution¶

Notons \([n] = \{1, 2, \ldots, n\}\). Montrons d'abord que \(B\) gagne si \(n \neq 1, 2, 4, 6\) : on donne une stratégie qui garantit que \(B\) peut toujours jouer après un coup de \(A\), et que la partie n'est pas nulle.

Lemme. Supposons que le premier choix de \(B\) soit \(n\) et que \(A\) ait joué son \(k\)-ième coup, avec \(k \geq 2\). Alors \(B\) peut jouer son \(k\)-ième coup.

Preuve. Soit \(S\) l'ensemble des \(k\) nombres choisis par \(A\). Comme \(S\) ne contient pas deux entiers consécutifs (et ne contient pas \(n\)), l'ensemble \([n] \setminus S\) est formé de \(k\) « blocs » d'entiers consécutifs si \(1 \in S\), et de \(k + 1\) blocs sinon. \(B\) n'a choisi que \(k - 1\) nombres, donc l'un de ces blocs ne contient aucun nombre de \(B\). Ses voisins extérieurs sont des nombres de \(A\) (ou les bords de \([n]\)), donc \(B\) peut y choisir n'importe quel nombre. \(\square\)

Décrivons la stratégie gagnante de \(B\) pour \(n \neq 1, 2, 4, 6\). Par symétrie (\(x \mapsto n + 1 - x\)), on peut supposer que le premier choix de \(A\) est au plus \(\frac{n+1}{2}\) ; \(B\) peut alors prendre \(n\) à son premier tour.

Cas 1 : \(n\) impair, \(n \geq 3\). La partie ne peut être nulle que si \(A\) finit par prendre tous les nombres impairs de \([n]\) (il ne peut pas prendre deux consécutifs, et il faudrait que tout soit pris). Comme \(B\) a déjà pris \(n\), c'est impossible. \(B\) applique le lemme jusqu'à ce que \(A\) ne puisse plus jouer.

Cas 2 : \(n\) pair, \(n \geq 8\). Comme \(B\) a pris \(n\), la partie n'est nulle que si \(A\) prend tous les nombres impairs de \([n-1]\). À son deuxième coup, \(B\) prend donc un nombre de \(\{1, 3, 5, \ldots, n-3\}\) non encore choisi par \(A\) : c'est possible car cet ensemble compte \(\frac{n-2}{2} \geq 3\) éléments et \(A\) n'en a choisi que \(2\) (et aucun n'est voisin de \(n\)). Ensuite, \(B\) applique le lemme jusqu'à ce que \(A\) ne puisse plus jouer.

Dans les deux cas, \(A\) perd.

Les cas \(n = 1, 2, 4, 6\). Pour \(n = 1, 2\), la partie est trivialement nulle. Pour \(n = 4\), \(A\) doit commencer par \(1\) (sinon il perd) ; de même \(B\) doit prendre \(4\), et la partie est nulle. Pour \(n = 6\), \(B\) obtient au moins la nulle grâce au lemme ou par une stratégie miroir. D'autre part, \(A\) obtient au moins la nulle ainsi : il commence par \(1\) ; après la réponse \(b\) de \(B\), il choisit un voisin \(c\) de \(b\) différent de \(1\) et \(2\), qu'il se réserve pour son troisième coup ; il peut alors jouer son deuxième coup en prenant un nombre différent de \(1, 2, c-1, c, c+1\). Donc \(A\) ne perd pas. \(\blacksquare\)

Remarques¶

Remarque 1 (stratégies explicites pour \(B\)). \(n\) impair, \(n \geq 3\) : \(B\) prend \(n\), puis à son \(k\)-ième coup (\(k \geq 2\)) le nombre qui vaut exactement \(1\) de moins que le \(k\)-ième choix de \(A\) ; si ce choix est \(1\), le premier choix \(a\) de \(A\) était \(> 1\) et \(B\) joue \(a - 1\) à la place.

\(n\) pair, \(n \geq 8\), si \(A\) commence par \(1\). Si le deuxième choix de \(A\) est \(3\), \(B\) prend \(n - 3\) ; ensuite, il prend \(1\) de moins que le \(k\)-ième choix de \(A\), sauf qu'il prend \(2\) si \(A\) prend \(n - 2\) ou \(n - 1\). Si le deuxième choix de \(A\) est \(a > 3\), \(B\) prend \(a - 2\), puis toujours \(1\) de moins que le choix de \(A\).

Extension à un premier coup quelconque. Si \(B\) a une stratégie gagnante après le coup \(1\) de \(A\), il en a une après tout premier coup \(a > 1\) : il mène en parallèle une partie imaginaire obtenue en retournant le segment \([1, a]\) (tout choix \(x\) devient \(x\) si \(x > a\), et \(a + 1 - x\) si \(x \leq a\)), dans laquelle \(A\) a commencé par \(1\). Un nombre est pris dans la partie réelle si et seulement si son correspondant l'est dans l'imaginaire, et les interdictions de voisinage se correspondent pour chaque joueur. \(B\) répond dans la partie imaginaire selon sa stratégie et joue le coup correspondant dans la partie réelle ; gagnant l'une, il gagne l'autre. Cette remarque simplifie aussi le cas \(n\) impair.

Remarque 2. Pour \(n\) impair, \(B\) peut aussi utiliser une stratégie miroir, mais il faut des idées supplémentaires pour l'adapter lorsque \(A\) prend \(\frac{n+1}{2}\).