Une table débarrassée laisse place à un jeu de papier. Nora prépare trois tas de jetons et Camille souhaite savoir lequel toucher au premier tour. Compter tous les jetons donne la taille du départ, mais ne décide pas toujours de la personne qui pourra prendre le dernier. Nous allons remplir leurs coups, puis reprendre le choix lorsque gagner signifie au contraire laisser le dernier à l'autre. Aucun comportement de joueur réel ni matériel commercial n'est observé.
Le modèle est le jeu classique de Nim, avec des tas entièrement visibles et deux personnes qui alternent. Un coup retire un nombre entier strictement positif de jetons d'un seul tas, sans en ajouter ni toucher un deuxième tas. Tout tas peut être vidé. Dans la première règle, prendre le dernier jeton gagne. Nous étudierons ensuite une règle où ce geste perd, puis une permission où chaque coup retire au maximum deux jetons. Les nombres représentent des états fictifs ; ce ne sont ni aliments ni mises d'argent.
Oink Games présente des jeux de société.
Leder Games se présente comme éditeur de jeux de société.
Allplay présente des jeux de société.
Ces pages sont consultées pour ces catégories seules. Elles ne fournissent pas les règles ni les coups calculés ici.
Un calcul de colonnes choisit le premier retrait
Nora pose trois tas de trois, quatre et cinq jetons. Elle écrit leurs nombres en base deux, sur trois colonnes : trois devient 011, quatre 100, cinq 101. Dans chaque colonne, elle note zéro si le nombre de chiffres un est pair, un s'il est impair. La colonne de droite contient deux un, celle du milieu un seul, celle de gauche deux. Le résultat est 010, soit deux. Cette opération est le XOR, que Nora utilisera sur les tailles des tas plutôt que sur leur somme.
Camille commence en retirant deux jetons du tas de trois. Les tailles deviennent un, quatre, cinq, écrites 001, 100, 101. Il y a maintenant deux un à droite, zéro au milieu et deux à gauche : le résultat vaut zéro. Elle transmet cet état à Nora. Elle n'a pas cherché à égaliser les trois tailles, qui restent différentes, ni à partager le nombre total en deux moitiés. Sa décision a annulé précisément le résultat des colonnes. Le premier coup est légal : deux jetons sont sortis d'un seul tas contenant trois.
Une proposition concurrente voudrait vider le tas de cinq, en laissant trois et quatre. Le XOR vaut alors sept, puisque 011 et 100 donnent 111. Camille écarte cette proposition pour sa conduite qui veut remettre zéro. Elle ne prétend pas que retirer davantage accélère nécessairement une victoire. Vider le plus grand tas raccourcit ce départ de cinq jetons, mais ne conserve pas le calcul qu'elle souhaite laisser à Nora. La remise retenue retire deux du plus petit tas ; la quantité retirée et l'état résultant accompagnent ce choix.
Nora demande pourquoi zéro servirait de repère. Partons du tableau un, quatre, cinq choisi. Un retrait remplace exactement une taille a par une taille b plus petite. Avant ce coup, le XOR de toutes les tailles vaut zéro. Après lui, son résultat est celui de a combiné avec b, car les tailles inchangées se compensent avec leur ancienne participation. Si a et b étaient égaux, ce résultat serait zéro ; ils sont différents, donc au moins une colonne change. Aucun coup légal ne peut ainsi remettre zéro depuis ce tableau, même s'il ne retire qu'un jeton.
Cette propriété n'a pas seulement été testée sur les trois retraits les plus faciles à dessiner. Elle traite tout tas choisi et toute taille restante plus petite. Le coup ne peut changer deux tas pour compenser ses deux interventions : notre menu l'interdit. Nora enlève donc de sa fiche une réparation qui retirait un jeton dans le tas de quatre et un dans celui de cinq en une seule fois. Le résultat des colonnes aurait pu se conserver autrement, mais cette réparation ne serait pas une réponse permise au jeu qu'elles ont posé.
Revenir à zéro après un coup adverse
Nora joue effectivement depuis un, quatre, cinq : elle retire un jeton du tas de cinq. Il reste un, quatre, quatre. Les deux quatre se compensent et le XOR vaut un. Camille peut vider le tas de un, laissant zéro, quatre, quatre. Les deux tas égaux se compensent encore, cette fois sans taille supplémentaire : le résultat revient à zéro. Camille transmet ce nouvel état. Elle n'a pas recommencé son premier retrait de deux par habitude ; elle a choisi un autre tas et une autre quantité en fonction du tableau reçu.
Dans une branche différente depuis un, quatre, cinq, Nora retire deux du tas de quatre. Il reste un, deux, cinq, soit 001, 010, 101. Leur XOR vaut six, écrit 110. Camille change cinq en trois en retirant deux jetons. Les tailles un, deux, trois donnent 001, 010, 011, dont les colonnes se compensent. Elle choisit ce retrait de deux et conserve le tas de deux tel qu'il lui a été remis. Retirer deux du tas de un serait impossible ; la quantité ne désigne donc pas seule le coup. Le choix contient bien la taille initiale et la taille finale du tas visé.
Pour chercher une réponse depuis n'importe quel résultat non nul, Camille regarde sa colonne un la plus à gauche. Un nombre impair de tas porte un dans cette colonne ; elle en choisit un. Elle remplace sa taille a par le XOR de a avec le résultat total. Dans cette colonne, le un de a devient zéro ; toutes les colonnes situées plus à gauche restent inchangées, puisque le résultat total y valait zéro. La nouvelle taille b est donc strictement inférieure à a, quelles que soient les colonnes de droite. Ce remplacement demande un retrait positif, pas un ajout interdit.
Sur le tableau un, deux, cinq, la colonne la plus à gauche du résultat six est celle de quatre. Seul le tas de cinq la porte. Combiner 101 avec 110 donne 011, donc trois. Les deux jetons retirés réalisent exactement le choix précédent. Sur un, quatre, quatre, le résultat un ne touche que la dernière colonne ; seul le tas de un la porte, et sa nouvelle taille est zéro. Ces deux calculs vérifient la même construction dans des états où elle désigne des tas différents et où l'un se vide tandis que l'autre reste présent.
Le résultat après cette construction vaut zéro : dans le total, l'ancienne taille a est retirée et la nouvelle taille, a combinée avec le total, est introduite. Deux participations identiques du total se compensent, comme deux participations de a. Camille sait donc à la fois que sa cible est atteinte et que son coup est disponible. Elle ne choisit pas un tableau zéro qui demanderait de faire grandir un tas. La colonne la plus à gauche avait précisément établi que la nouvelle taille est inférieure, et la compensation établit maintenant la propriété de la remise.
Le repère décide du gagnant, sans choisir les erreurs de l'autre
À chaque coup, le nombre total de jetons diminue d'au moins un. La partie ne peut donc tourner indéfiniment dans les mêmes tailles. L'état sans jeton possède un XOR nul et appartient, selon notre première règle, à la personne qui vient de perdre la possibilité de jouer : l'autre a pris le dernier. Depuis un état nul non vide, toute réponse transmet un résultat non nul. Depuis ce résultat non nul, Camille dispose du retrait qui rend zéro. Elle peut répéter cette réponse tant que Nora lui remet un tableau non vide.
Camille part de trois, quatre, cinq et rend un, quatre, cinq. Si elle continue à rendre zéro après chaque coup de Nora, c'est Nora qui reçoit finalement l'état vide. Camille aura alors pris le dernier jeton. Nora ne peut pas forcer un coup différent en choisissant un retrait inattendu : la construction précédente traite tout résultat non nul permis. Cela ne signifie pas que Camille gagne si elle cesse de suivre la conduite. Nous avons une réponse garantissant la victoire contre les coups légaux, plutôt qu'une annonce portant sur toute suite improvisée depuis les mêmes nombres.
Nora compare deux départs contenant chacun six jetons. Trois et trois ont un XOR nul ; un et cinq ont un XOR de quatre. Avec trois et trois, toute première intervention lui retire le repère nul et permet à Camille de le retrouver. Avec un et cinq, Nora peut transformer cinq en un, laissant un et un à Camille. La même parité du total, pair dans les deux cas, a donc rencontré des situations opposées pour la personne qui commence. Nora retire la note qui donnait une victoire à chaque départ de taille paire dans ce jeu à plusieurs tas.
Elle remplit aussi le cas du seul tas de trois. Sous notre permission de retrait libre, elle prend les trois en une fois et gagne. Faire jouer seulement un jeton par tour aurait produit une autre partie, mais ce n'est pas la permission actuelle. Le tableau de colonnes ne demande pas ici une longue suite : toute taille positive seule a un résultat non nul et peut devenir zéro par vidage. Ce cas servira de comparaison lorsque Nora réduira réellement le menu des retraits ; elle ne lui attribue pas d'avance la règle de cette autre branche.
Prendre le dernier peut devenir le geste perdant
Une nouvelle fiche conserve les tas visibles et les retraits libres, mais fait perdre la personne qui prend le dernier. Nous n'appelons pas cette fiche une correction de l'addition précédente : c'est une autre condition terminale. Avec un jeton seul, Nora doit le prendre et perd. Avec deux jetons séparés en deux tas de un, elle vide un tas, laisse le dernier à Camille et gagne. Trois tas de un font au contraire perdre la personne qui commence, car chaque coup obligatoire retire exactement un de ces trois tas.
Pour des tas tous réduits à un jeton, le nombre de tas non vides décide donc cette fin. Après un nombre impair de coups restants, la personne qui commence prend le dernier et perd ; après un nombre pair, l'autre le prend. Nora garde les nombres de tas, pas leur disposition sur la table. Quatre tas de un lui permettent de laisser trois à Camille, qui lui laissera deux ; Nora lui en laissera alors un. Le calcul concerne l'obligation de retirer une seule unité de ces tas, même si la règle générale autorise davantage dans un tas plus grand.
Camille arrive maintenant devant quatre, un, un. Sous la première règle, elle aurait vidé quatre, laissant deux tas de un et un résultat nul. Sous la nouvelle règle, cette réponse donne justement à Nora un nombre pair de tas unitaires, donc une victoire pour Nora. Camille retire seulement trois du grand tas. Elle laisse un, un, un, soit trois tas de un, et gagne contre toute réponse : Nora laisse deux, Camille en laisse un, Nora prend le dernier et perd. La cible de zéro a été abandonnée à cette frontière précise.
Dans un autre état, quatre, un, un, un, Camille dispose d'un grand tas et de trois tas unitaires. Elle vide cette fois le grand tas, laissant trois unitaires à Nora. Le choix précédent, réduire quatre à un, en aurait laissé quatre et serait perdant pour Camille. Quand il ne reste qu'un tas supérieur à un, elle complète donc les tas unitaires jusqu'à un nombre impair : s'ils sont déjà impairs, elle vide le grand ; s'ils sont pairs, elle le réduit à un. Les deux retraits sont disponibles parce que ce tas contient au moins deux jetons.
Conserver le calcul initial jusqu'à la bonne frontière
Tant qu'au moins deux tas sont supérieurs à un, Camille conserve une recherche de résultat nul. Un tableau nul ne peut avoir exactement un grand tas : dans la colonne un la plus à gauche de ce grand nombre, les tas unitaires n'apporteraient aucun autre un pour le compenser. Si son retrait depuis plusieurs grands tas atteint zéro, il laisse donc soit encore plusieurs grands tas, soit seulement des tas unitaires. Elle vérifie ainsi que son choix ne transmet pas à Nora un seul grand tas dont celle-ci pourrait régler librement la parité finale.
Il faut regarder le second cas. Pour qu'un seul retrait fasse passer plusieurs grands tas à aucun, il faudrait vider ou réduire simultanément au moins deux tas ; notre coup touche un seul tas. Ce passage direct est donc impossible depuis au moins deux grands. Le tableau nul remis par Camille possède encore au moins deux grands tas. Nora peut ensuite, en réduisant un seul de ces tas, créer la frontière avec un grand restant. C'est alors Camille qui reçoit cette frontière et choisit la réponse de parité, au lieu de conserver automatiquement sa cible précédente.
Camille remplit une telle traversée avec deux et deux. Le résultat est nul et les deux tas sont grands. Nora transforme le premier deux en un, laissant un et deux. Il n'y a plus qu'un grand tas et un tas unitaire, nombre impair. Camille vide le tas de deux et laisse un à Nora, qui perd en le prenant. Si Nora avait vidé le premier deux, il serait resté un seul grand tas et aucun unitaire ; Camille aurait réduit deux à un. Les deux réponses adverses franchissent la même frontière, mais appellent des quantités différentes pour transmettre le dernier jeton.
Cette conduite peut aussi commencer dans trois, quatre, cinq, qui possède plusieurs grands tas et un résultat non nul. Camille rend un, quatre, cinq comme auparavant. Elle ne donne toutefois plus la même justification à la fin de la partie : elle conserve zéro seulement avant la frontière d'un grand tas, puis règle le nombre impair de tas unitaires. Le premier coup identique entre les deux fiches ne prouve pas que leurs décisions finales seraient interchangeables. La nouvelle fiche porte une condition de passage qui sera réellement consultée après chaque réponse de Nora.
Limiter le retrait retire aussi des réponses disponibles
Nora crée une troisième fiche, où prendre le dernier gagne à nouveau, mais où chaque tour retire un ou deux jetons d'un seul tas. Elle reprend son tas isolé de trois. Le vidage en une fois est maintenant interdit. Si elle retire un, Camille reçoit deux et prend les deux ; si elle retire deux, Camille reçoit un et le prend. Nora perd contre ces deux réponses. La même taille trois, gagnante avec retrait libre, est donc perdante sous ce menu réduit. Elle conserve le résultat ancien dans son histoire, sans lui laisser le droit de désigner un coup désormais impossible.
Nora établit les positions de son tas unique en remontant depuis zéro. À un ou deux, elle peut prendre tout le tas et gagne. À trois, les deux retraits donnent deux ou un, tous deux gagnants pour l'autre. À quatre, elle peut retirer un et laisser trois ; à cinq, elle peut retirer deux et laisser trois. À six, retirer un laisse cinq et retirer deux laisse quatre, deux positions gagnantes pour l'autre. Les tailles zéro, trois et six sont ainsi les premières positions perdantes pour la personne qui doit jouer.
Elle prolonge ce choix sans dresser un nouveau tableau pour chaque taille. Depuis un multiple positif de trois, retirer un ou deux laisse un nombre qui n'est pas multiple de trois. Depuis une taille ayant un reste de un, retirer un laisse un multiple ; depuis un reste de deux, retirer deux le fait. Ces retraits sont légaux pour les tailles concernées. La fin zéro et la diminution à chaque tour ferment le raisonnement : Nora choisit le retrait donné par le reste quand il existe, et reconnaît qu'un départ multiple de trois ne possède pas cette réponse gagnante.
Sur sept jetons, elle retire un pour laisser six. Si Camille retire ensuite deux, Nora reçoit quatre et retire un pour laisser trois. Si Camille retire plutôt un depuis six, Nora reçoit cinq et retire deux pour laisser trois. Dans les deux cas, Camille doit donner un ou deux à Nora, qui prend alors tout ce reste et gagne. Nora transmet sept avec ce choix initial de un. Elle refuse une fiche indiquant « retirer trois pour laisser quatre » : outre son mauvais repère, ce retrait n'appartient pas au menu de un ou deux qu'elle vient de vérifier.
Les trois fiches restent donc séparées. Le retrait libre avec dernier gagnant utilise le résultat des colonnes ; le dernier perdant demande une autre décision près des tas unitaires ; le retrait borné change les réponses disponibles et la règle du tas isolé. Camille remet ses coups avec leurs tailles résultantes et leurs conditions terminales. Les nombres communs entre certaines branches n'effacent pas ces permissions : une réponse calculée doit pouvoir être jouée sur la fiche qu'elles ont effectivement choisie.