E442. A deux ou en solitaire Imprimer
E4. Jeux de NIM et variantes

calculator_edit.png  

Zig et Puce disposent d’une grille carrée 12x12 dont les cases sont remplies avec les entiers naturels de 1 à 144. Le premier joueur barre un nombre pair puis chaque joueur barre un nombre non encore rayé parmi les multiples ou les diviseurs du nombre choisi par le joueur précédent. Un joueur est déclaré vainqueur si son adversaire ne peut plus jouer.Zig joue le premier. Lequel des deux joueurs a une stratégie gagnante ?
Le vainqueur de la partie joue ensuite en solitaire avec la même grille et selon les mêmes règles. Son objectif est de barrer le plus grand nombre possible n de cases.Déterminer n.


 Solution


Il s'agit du jeu de Juniper Green vulgarisé par Ian Stewart en 1996 dans la revue Scientific American et qui a été repris ultérieurement dans les bulletins verts de l'APMEP.
José Pacios et Claudio Baiocchi ont résolu la première partie du problème. En ce qui concerne la variante jouée en solitaire, Claudio Baiocchi a obtenu le score de 97 cases.La question de l'amélioration de ce score reste ouverte.

Juillet 2022: Paul Revenant nous écrit:

Je complète la solution du problème E442, dans lequel il est question de barrer un maximum d'entiers entre 1 et 144 dans la variante "solitaire". Une solution a été trouvée avec 97 entiers, je propose ici une solution avec 107 entiers :

123, 41, 82, 1, 87, 29, 58, 116, 2, 74, 37, 111, 3, 93, 31, 62, 124, 4, 76, 38, 114, 57, 19, 95, 5, 115, 23, 92, 46, 138, 6, 144, 48, 16, 128, 64, 32, 96, 24, 120, 40, 80, 20, 100, 50, 10, 130, 65, 13, 143, 11, 55, 110, 22, 88, 44, 132, 66, 33, 99, 9, 117, 39, 78, 26, 52, 104, 8, 136, 68, 34, 102, 51, 17, 119, 7, 49, 98, 14, 112, 56, 28, 140, 70, 35, 105, 21, 63, 126, 42, 84, 12, 72, 18, 36, 108, 54, 27, 135, 45, 90, 30, 60, 15, 75, 25, 125

Il mentionne par la même occasion le lien de l'encylopédie en ligne des nombres enteirs (O.E.IS.): https://oeis.org/A337125. Le chercheur Rob Pratt explique son algorithme pour déterminer les solutions jusqu'à n=200.