Jeu d'allumettes   Règle du jeu Un tas d'allumettes comporte un nombre impair d'allumettes. Deux joueurs retirent à tour de rôle, une ou deux allumettes, jusqu'à épuisement du tas. A gagné celui qui, à la fin, dispose dans son tas d'un nombre impair d'allumettes. Ce problème est posé dans Pour la science N° 42, décembre 1997 Jouer contre l'ordinateur Il faut tout d'abord cliquer les paires d'allumettes à garder pour obtenir un nombre initial impair d'allumettes. -entrer ensuite son prénom, puis cliquer Jouer ; -choisir alors celui qui joue le premier. Quand c'est son tour, cliquer -soit une allumette puis OK -soit deux allumettes. Quand c'est le tour de l'ordinateur, cliquer le bouton proposé pour qu'il joue. CLIQUER ANALYSE DU JEU Nous allons représenter les différentes situations par un couple (n,p) où        n représente le nombre d'allumettes restant à jouer et        p la parité du nombre d'allumettes que possède le joueur actuel. Les points rouges signifient que celui qui doit jouer à ce moment-là possède un nombre pair d'allumettes soit p = 0 ; Les points verts signifient qu'il possède un nombre impair d'allumettes soit p = 1. Rappelons que le nombre d'allumettes initial est impair. Cas à analyser : 1°) Soit le joueur A a un nombre PAIR d'allumettes : il est ROUGE, appelons B le joueur suivant, deux cas se présentent : - il reste un nombre IMPAIR d'allumettes et dans ce cas, l'autre joueur B a un nombre pair d'allumettes, il est ROUGE (p = 0).        ou bien A joue une allumette, et B sera dans l'état : n pair, p = 0, ROUGE ;        ou bien A joue deux allumettes, et B sera dans l'état : n impair, p = 0, ROUGE ; - ou bien, il reste un nombre PAIR d'allumettes et dans ce cas, l'autre joueur B a un nombre impair d'allumettes, il est VERT (p = 1).        ou bien A joue une allumette, et B sera dans l'état : n impair, p = 1, VERT ;        ou bien A joue deux allumettes, et B sera dans l'état : n pair, p = 1, VERT. Donc . état ROUGE avec un reste impair donne toujours un état ROUGE, . état ROUGE avec un reste pair donne toujours un état VERT. Le schéma suivant résume cette situation, on parcourt les traits de gauche à droite. 2°) Soit le joueur A a un nombre IMPAIR d'allumettes : il est VERT, - ou il reste un nombre IMPAIR d'allumettes et dans ce cas, l'autre joueur B a un nombre impair d'allumette, il est VERT (p = 1).        ou bien A joue une allumette, et B sera dans l'état : n pair, p = 1, VERT ;        ou bien A joue deux allumettes, et B sera dans l'état : n impair, p = 1, VERT ; - ou bien, il reste un nombre PAIR d'allumettes et dans ce cas, l'autre joueur B a un nombre pair d'allumettes, il est ROUGE (p = 0).        ou bien A joue une allumette, et B sera dans l'état : n impair, p = 0, ROUGE ;        ou bien A joue deux allumettes, et B sera dans l'état : n pair, p = 0, ROUGE. Donc . état VERT avec un reste impair donne toujours un état VERT, . état VERT avec un reste pair donne toujours un état ROUGE. On peut résumer les deux situations en superposant les deux graphes précédents Appelons, -situation GAGNANTE (nous écrirons G) une situation devant laquelle en jouant bien, on est sûr de GAGNER (en la transformant en situation perdante) ; -situation PERDANTE devant laquelle on perd si l'autre joue bien (nous écrirons P) ; ATTENTION, cette appellation n'est pas commune à tous les auteurs, on trouve quelquefois l'appellation contraire. La situation verte en 0 est gagnante puisque le joueur a un nombre impair d'allumettes et il n'y en a plus. Il a gagné. On marque G sur cet état. La situation rouge en 0 est perdante puisque le joueur a un nombre pair d'allumettes et il n'y en a plus. Il a perdu. On marque P sur cet état. Etiquetons alors les états du jeu selon la procédure suivante : -nommer G tous les états qui mènent à une situation P en un seul coup ; -effacer tous les points déjà étiquetés et les traits qui arrivent en G; -nommer P tous les états d'où il ne part plus aucun trait ; -recommencer s'il le faut les étapes précédentes. Voici le graphe obtenu avec cette procédure Finalement l'étiquetage est tel que tout trait qui part d'une situation perdante P aboutit à une situation Gagnante G. Et parmi tous ces traits qui partent d'un point G, l'un au moins aboutit en un point P, c'est à dire à une situation perdante pour l'adversaire. C'est normal, c'est fait exprès ! COMMENT GAGNER ? Pour gagner, il faut démarrer sur une situation Gagnante et laisser à l'adversaire une situation Perdante qui l'amènera forcément à laisser une situation Gagnante pour son adversaire... Au départ, l'état est rouge puisque le joueur possède 0 allumette, donc un nombre pair. Exemples : Lorsque au départ, le nombre d'allumettes vaut 1 modulo 4 (c'est à dire que le nombre d'allumettes a pour reste 1 dans la division par 4 : soit 1, 5, 9...), le joueur qui a la main est sûr de gagner s'il adopte la bonne stratégie. Il lui suffit de prendre deux allumettes et d'imiter scrupuleusement son adversaire jusqu'à la fin et éventuellement de prendre la dernière allumette s'il n'en reste plus qu'une. Par contre, si le nombre d'allumettes au départ, vaut 3 modulo 4, le joueur qui joue le second est sûr de gagner selon la même stratégie d'imitation.