JEU DE NIM Des cailloux sont répartis sur plusieurs rangées; chacun des deux joueurs supprime tour à tour au moins un caillou d'une rangée de son choix . Celui qui supprime le dernier a perdu. Première méthode pour gagner L'opération xor est la somme sans retenue d'entiers positifs exprimés en binaire. Elle a les propriétés de l'addition plus une: a xor b = 0 si a = b (et rcpt). Exemple: 4 xor 5 xor 7 = en binaire 100 xor 101 xor 111 = 110 = 6 en décimal. 4 xor 5 xor 7 xor 6 = 6 xor 6 = 0 = 4 xor (5 xor 6) xor 7 = 4 xor 3 xor 7 On nomme a,b,...n les rangées d'un jeu ou leur valeur en nombre de cailloux. Pour gagner, jouer dés que possible de façon que l'opération xor de toutes les rangées = 0 .Ceci étant réalisé, par exemple, dans un jeu de trois lignes a,b,c , l'adversaire laisse d cailloux en ligne c : a xor b xor d = c xor d et d < c . Laisser b xor (c xor d) cailloux en ligne b si b xor (c xor d) < b :on a bien a xor b xor c xor d xor d = 0 et le jeu est encore favorable. Continuer de la sorte jusqu'à ce qu'une seule ligne contienne plusieurs cailloux et laisser l'adversaire jouir d'un nombre impair de lignes de 1 Deuxième méthode pour gagner Apprendre les jeux gagnants à trois lignes suivants : 123, 145, 167, 189, 1 10 11 ... (1, nombre pair, nombre suivant) 246, 257, 2 8 10, 2 9 11, 347, 356, 3 8 11, 3 9 10 Cela suffit pour toute partie ayant moins de 12 cailloux par ligne; 356 et 39 10 sont les seuls jeux dont la dernière ligne diffère de la somme des deux autres. Règle N°1: tout double est un jeu gagnant; 5 5 par exemple. Règle N°2: un jeu gagnant le reste si on lui adjoint ou si on lui retire un jeu gagnant. Ex: 4444, 2233, 1155, 22246, 189257, 347356 sont gagnants. Exception si le dernier à jouer perd: quand une seule ligne diffère de 1 ,laisser un nombre impair de lignes de 1: 11 est perdant. Application: 124689 est gagnant car il équivaut à 189246 123257 est gagnant donc 1357 aussi donc 1357189 aussi donc 35789 L'adversaire joue 6598 20 : 653981132 est gagnant donc 65982 aussi: jouer 2 en ligne 5 (même conclusion avec 6 5 3 3 9 10 10 8 2) Cela revient à jouer de la façon suivante: On appelle valeur d'un jeu la valeur de la ligne à lui ajouter pour le rendre gagnant. 18 v 9 (vaut 9) ; 37 v 4 v 26 v 15 v 1555 v 567 257 v 0 v 44 v 356 v tout jeu gagnant. 11 vaut 0 tant que deux lignes au moins différent de 1 On peut remplacer plusieurs lignes par leur valeur sans changer la valeur d'un jeu, et inversement. 6 5 9 8 20 vaut 3 1 20 : jouer 2 en ligne 5 Pour gagner des parties plus difficiles apprendre ce qui suit. Un jeu gagnant ne contient pas de puissance de 2 en maximum unique (ou triple...): 358 est perdant. Il y a deux sortes de jeux gagnants à trois lignes faciles à trouver : 1)Si y ,puissance de 2 -1 ,est > x , y x (y - x) est gagnant: Ex 15 9 6 2)Si y ,puissance de 2 ,est > x , y x (y + x) est gagnant: Ex 8 5 13 Si y ,puissance de 2 ,est < x , il faut décomposer : 4 13 9 v 4 8 5 8 1 v 0 et 4 13 17 est perdant (v 4 13 16 1 où une puissance de 2 est maximum unique). Pour jouer avec des nombres supérieurs à onze retenir aussi ces jeux gagnants: 3 13 14 (v 38586), 5 9 12, 5 11 14, 6 10 12, 6 11 13, 7 9 14, 7 10 13, 7 11 12 Exemples: 13 11 14 17 v 6 14 17 : jouer 8 en ligne 4 33 30 29 7 11 v 33 16 14 16 13 7 11 v 33 3 12 : jouer 15 en ligne 1 38 37 18 10 17 v 32 6 32 5 16 2 10 16 1 v 6 5 3 10 : jouer 0 en ligne 4 26 11 4 33 34 v 26 11 4 3 : jouer 12 en ligne 1 26 11 20 33 34 v 10 11 4 3 : jouer 2 + 16 = 18 en ligne 3 26 11 4 33 50 v 26 11 4 33 32 18 v 10 11 4 1 2 : jouer 2 en ligne 3 Remarques : Si le nombre total de cailloux est impair et supérieur au nombre de lignes,le jeu est perdant. Quand l'adversaire perdant supprime 1 d'un nombre impair, jouer de même. Il peut y avoir plusieurs façons de jouer : 2 6 6 : jouer 2 6 4 ou 2 4 6 ou 6 6 3 5 7 2 : jouer 5 7 2 ou 3 5 4 2 ou 3 5 7 1 Quand l'ordinateur a plusieurs solutions gagnantes, par ordre de priorité: 1: il joue sur une ligne doublée. 2: il n'ajoute pas de ligne doublée. 3: il supprime le plus de cailloux possible. 4: il supprime une ligne. 5: il joue le plus bas possible. Exemple: 6 6 2 2 2 1 : il joue 6 5 2 2 2 1 plutôt que 6 6 2 2 1 1