site2wouf.fr : Les allumettes du jour

Je suis né dans les prairies, là où les vents soufflent librement et où rien n'arrête la lumière du soleil. Je suis né là où il n'y a pas de barrières...

Geronimo (sur mon Tshirt!)

Partager :

Facebook X (Twitter) LinkedIn Email WhatsApp

🔑 Code de cette fiche :

imprimer LaTeX
ℹ️

Besoin d'aide sur les positions gagnantes et perdantes ?

Consultez la page du catalogue pour retrouver la distinction entre positions gagnantes et perdantes, et l'analyse à rebours.

📚 Voir les ressources pédagogiques

Fiche n°
mardi 4 août 2026

Le tas d'allumettes, la règle du jeu et les trois questions :

Le jeu des allumettes

Deux joueurs, Alice et Bruno, disposent d'un tas d'allumettes. Ils jouent chacun leur tour, Alice commence. À son tour, un joueur doit retirer 1, 2 ou 3 allumette(s) — pas le choix de passer.
Celui qui prend la dernière allumette gagne.
Voici le tas de départ, 45 allumettes :
Les questions montent en difficulté : la première se traite à la main, la dernière demande une règle générale et sa justification.
  1. Pour commencer, on joue avec un petit tas de 7 allumettes. Alice a-t-elle une façon de gagner à coup sûr ? On pourra examiner les situations une par une, en partant de 0 allumette.
  2. Revenons au tas de 45 allumettes. Qui gagne, si les deux joueurs jouent parfaitement ? Si c'est Alice, quel est son premier coup ?
  3. Décrire toutes les positions perdantes — celles où le joueur qui doit jouer est condamné, quoi qu'il fasse. Justifier la règle trouvée.

Un cahier d'exercices de 128 pages ...

Le cahier : 5,40 €

Plus de Produits

Publicité

Corrigé :

Le jeu des allumettes — Correction

Le bon point de vue. Ne cherchons pas « quel coup jouer », mais classons chaque position (le nombre d'allumettes restantes) en deux catégories, du point de vue du joueur qui doit jouer :
  • une position est perdante si tous les coups possibles offrent à l'adversaire une position gagnante ;
  • une position est gagnante s'il existe au moins un coup donnant à l'adversaire une position perdante.
On construit ce classement à partir de la fin, en partant de 0 allumette. Se retrouver devant 0 allumette signifie que l'adversaire vient de prendre la dernière : il a gagné, donc 0 est une position perdante.
1. Construisons le tableau jusqu'à 7 :
Allumettes restantes01234567
Le joueur qui doit jouerperdgagnegagnegagneperdgagnegagnegagne
Avec 7 allumettes, la position de départ est gagnante : Alice a une façon de l'emporter à coup sûr.
Son coup : retirer 3 allumette(s), ce qui laisse 4 — une position perdante pour Bruno.
2. Poursuivons le même tableau jusqu'à 45. Les positions perdantes rencontrées sont :
4, 8, 12, 16, 20, 24, 28, …
45 est une position gagnante : Alice gagne.
Son premier coup : retirer 1 allumette(s), ce qui laisse 44 — position perdante pour Bruno.
Ensuite, sa stratégie est mécanique : à chaque tour, elle ramène le tas sur la position perdante suivante. Bruno ne peut jamais y échapper.
3.
Les positions perdantes sont exactement les multiples de 4 : 0, 4, 8, 12, …
Pourquoi ? Depuis un multiple de 4, tout coup retire entre 1 et 3 allumettes : on tombe donc forcément sur un nombre qui n'est pas un multiple de 4. Inversement, depuis un nombre qui n'est pas multiple de 4, on peut toujours retirer juste ce qu'il faut (entre 1 et 3) pour retomber sur le multiple de 4 juste en dessous.
La stratégie. Celui qui laisse toujours à l'autre un multiple de 4 gagne. Et il y parvient toujours : si le tas vaut 4q + r avec r entre 1 et 3, il retire r. C'est l'astuce des « allumettes complémentaires » — si l'adversaire prend a, on prend 4 − a.
Ici 45 = 4 × 11 + 1 : ce n'est pas un multiple, position gagnante, et le coup est de retirer 1.
À retenir, bien au-delà des allumettes. Analyser un jeu à deux, c'est classer les positions en gagnantes et perdantes en remontant depuis la fin. La même méthode s'applique à quantité de jeux — et c'est exactement ce que fait un programme d'échecs, en beaucoup plus gros.

Des centaines de PDF disponibles gratuitement !

Pour accéder à nos ressources gratuites, il vous suffit de sélectionner l'activité que vous désirez dans le formulaire au dessus de l'activité du jour. Ensuite, utilisez l'icône appropriée sous les liens de partage pour télécharger vos PDF.

N'oubliez pas, partager fait vivre les sites ! 😊 Merci de votre soutien !

🔗 Liens utiles

// Remarques, codes, note de version etc...

J'ai réalisé cette activité en Python, en utilisant xhtml2pdf pour la version PDF des activités. Mon travail est sous licence Creative commons.

La version actuelle est la version 3.2.0 (28/11/2023)

N'hésitez pas à me contacter si vous detectez la moindre imperfection, ou si vous imaginez une amélioration potentielle !

Open source et gratuité n'empêchent ni les dons ni les remerciements 😉
Un euro ou deux pour m'aider à payer le serveur ? ☕ Payez-moi un café via PayPal