Exercice 3 — Jeu de Marienbad

Sujet

On dispose de quatre colonnes de \(3,5,7\) et 9 jetons comme ci-contre. Deux joueurs A et B jouent à tour de rôle en commençant par le joueur A . Chacun peut prendre autant de jetons qu'il veut, mais sur une seule colonne. Par exemple, pour le joueur A qui joue le premier :

Ceci est autorisé

Ceci n'est pas autorisé
Le joueur qui prend le dernier jeton a gagné. On se demande si l'un des deux joueurs peut forcer la victoire avec une stratégie gagnante. Autrement dit, est-ce que, avant de commencer à jouer, l'un des joueurs peut être sûr de gagner ?

Somme digitale

Pour répondre à cette question, on introduit les notions d'écriture binaire et de somme digitale.

1. Pour obtenir l'écriture binaire d'un nombre, on commence par le décomposer en somme de puissances de 2 successives. Par exemple :

\[ \begin{aligned} 155 & =128+16+8+2+1 \\ & =1 \times 2^{7}+0 \times 2^{6}+0 \times 2^{5}+1 \times 2^{4}+1 \times 2^{3}+0 \times 2^{2}+1 \times 2^{1}+1 \times 2^{0} \end{aligned} \]

L'écriture binaire de 155 est donc 10011011 où les 1 et les 0 correspondent au coefficient des puissances de 2 successives décroissantes.
a. Donner l'écriture binaire de 346 .
b. L'écriture binaire d'un nombre est 111001. Déterminer ce nombre.
2. On note ⊕ la somme digitale de deux nombres binaires. Par exemple, on cherche à effectuer :

\[ \underline{1001010} \oplus \underline{101110} \]

On commence par écrire que \(\underline{101110}=\underline{0101110}\) de telle sorte que les deux nombres possèdent le même nombre de chiffres dans leur écriture. Puis pour chaque position, si la valeur est identique, on note 0 ; si la valeur est différente, on note 1. Ainsi, \(\underline{1001010} \oplus \underline{0101110}=\underline{1100100}\).
Calculer les sommes digitales suivantes :
a. \(\underline{10101} \oplus \underline{1001}\)
b. \(\underline{10011} \oplus \underline{101101}\)
c. \(\underline{100001} \oplus \underline{101100}\)

Stratégie gagnante

Pour le jeu de Marienbad, on dira que le jeu est en position favorable si, lorsqu'on écrit en binaire le nombre de jetons dans chacune des colonnes, leur somme digitale est non-nulle. On parlera de position défavorable dans le cas contraire.
3. La position de départ \(3-5-7-9\) est-elle favorable ou défavorable ?
4. C'est au joueur A de jouer, comment peut-il mettre le jeu en position défavorable ?
5. C'est au joueur B de jouer et on suppose que le joueur A a laissé le jeu en position défavorable. En quelle position est le jeu après que le joueur B a joué ?