Exercice 1 — Le jeu de la petite moitié

Sujet

Étant donné un nombre entier \(n \geqslant 2\), on notera \(T_{n}\) un tas contenant exactement \(n\) jetons.

1. Deux joueurs A et B jouent au jeu suivant.

Chacun à son tour retire du tas un ou deux jetons. Le perdant est celui qui retire le dernier jeton. Les deux joueurs A et B sont très futés ce qui leur permet, à chaque étape du jeu, d'adopter la stratégie la meilleure dans le but de gagner.
Le joueur A commence le premier.
On dira que le tas \(T_{n}\) est gagnant si A peut adopter une stratégie lui assurant la victoire en adaptant à chaque étape du jeu son choix en fonction de ce que joue B et en le poussant ainsi à perdre.
On dira que le tas \(T_{n}\) est perdant s'il n'est pas gagnant, autrement dit si A ne peut pas adopter de stratégie lui assurant la victoire.
Exemple :

• \(T_{2}\) est bien sûr un tas gagnant car A peut adopter la stratégie gagnante suivante :

A commence par retirer un jeton et B n'aura d'autre choix que de tirer le dernier jeton.

• \(T_{3}\) est également un tas gagnant car A peut adopter la stratégie gagnante suivante :

A commence par retirer deux jetons en laissant à B le dernier jeton.

• \(T_{4}\) est par contre un tas perdant car aucune stratégie n'assure la victoire à A . En effet :

Si A commence par retirer un jeton, il laisse à B le tas \(T_{3}\) qui permet à B de gagner s'il joue intelligemment.
Si A commence par retirer deux jetons, il laisse à B le tas \(T_{2}\) qui permet à B de gagner s'il joue intelligemment.
a) Montrer que le tas \(T_{5}\) est gagnant.
b) Pour chacune des valeurs de l'entier \(n\) avec \(6 \leqslant n \leqslant 10\), préciser si le tas \(T_{n}\) est gagnant ou bien perdant.
c) Montrer que le tas \(T_{20}\) est gagnant. Justifier clairement votre réponse.
d) Le tas \(T_{2014}\) est-il gagnant ?
2. «Ce jeu est trop simple, dit B, et bien long. Modifions la règle. À chaque étape du jeu, au lieu de retirer un ou deux jetons, on pourrait en retirer un ou la moitié des jetons restant dans le tas. » « Bonne idée mais, par exemple, s'il en reste 13, la moitié de 13 c'est combien? » dit A.
« Alors on prendra la petite moitié des jetons restant dans le tas» répond B « c'est-à-dire le plus grand nombre entier inférieur ou égal à la moitié. Par exemple s'il reste 10 jetons dans le tas, on pourrait en retirer un ou 5. S'il en reste 13 on pourrait en retirer un ou \(6 . \gg\)
« OK c'est parti avec cette nouvelle règle» dit A .
«Vas-y, c'est toi qui commence» dit B.
a) a. Pour chacune des valeurs de l'entier \(n\) avec \(2 \leqslant n \leqslant 13\), préciser si le tas \(T_{13}\) est gagnant ou bien perdant.
b) Le tas \(T_{40}\) est-il gagnant ou perdant? Justifier clairement votre réponse.