H118. Des carrés à la queue leu leu Imprimer
H. Graphes et circuits
calculator_edit.png  
 

Le résultat k (1,2,3,4,5 ou 6) du lancer d'un dé supposé parfait est écrit au tableau. Zig et Puce chacun à son tour écrivent sur une même ligne un nombre choisi parmi l'ensemble des 24 premiers nombres naturels 1 à 24, distinct de tous ceux qui ont déjà été écrits, y compris k, tel que la somme des deux derniers nombres inscrits est un carré parfait. La partie s'arrête quand l'un des deux joueurs est bloqué faute d'obtenir un carré ou parce que les 24 entiers ont tous été écrits. Le gagnant est donc celui qui écrit le dernier nombre. Zig commence. Quelle est la probabilité de gain de Puce ?

 

 solution


Ce problème a donné lieu à un large éventail de réponses qui s'accordent toutes pour ne laisser aucune chance à Puce quel que soit le résultat du lancer du dé. La stratégie gagnante de Zig peut se résumer simplement : "à tout x, répondre 25 - x". Voir les solutions de Pierre Henri Palmade,Jean Moreau de Saint Martin,Catherine Nadault,Philippe Laugerat,Fabien Gigante,Daniel Collignon. La contribution de Claudio Baïocchi mérite quelques commentaires. Avec le logiciel Javascript, Claudio Baïocchi a conçu un programme susceptible de trouver la bonne stratégie. Partant d'un programme peu performant mais simple à décrire qu'il appelle "stupide", il écrit un programme plus "intelligent" qu'il appelle "recursif" et qui fournit à Zig sa stratégie gagnante. L'avantage de ce programme est de traiter également la version dite "Misère" (bien connue des amateurs des jeux de type NIM ou Marienbad) selon laquelle le gagnant de la version de base devient le perdant. En d'autres termes, le dernier joueur à pouvoir écrire un entier qui donne un carré est perdant. Cette fois-ci, la stratégie de Zig ne s'exprime plus aussi simplement que précédemment. Le programme "misere" donne toujours Zig gagnant sauf quand le lancer du dé donne un 5 qui permet à Puce de sauver l'honneur!