6x11=la stratégie gagnante commence par manger un seul carré!
8x10=la stratégie gagnante commence par deux coups possibles (c’est le plus petit exemple)

On peut coder une position via le chemin qui part en haut à droite et finit en bas à gauche en suivant le bord de ce qu’il reste de la tablette. Dans une tablette nxm, ces chemins sont de longueur n+m et il y en a n parmi n+m (regarder les moments où on va à gauche). En identifiant un chemin à un n uplet croissant d’éléments de {1,…,n+m} (les moments où on va à gauche), on peut mettre un ordre lexicographique sur l’ensemble des positions. On peut alors calculer le successeur d’une position, et observer qu’étant donnée une position, les positions obtenues à partir d’elle sont plus petites pour l’ordre lexicographique. Étant donné une position, on peut calculer son rang, et étant donné un rang on peut calculer la position correspondante, ce qui permet d’indexer efficacement les positions par des entiers entre 1 et n parmi n+m.

On peut donc construire la stratégie gagnante de la manière suivante: on commence par dire que toutes les positions sont perdantes sauf la position vide, puis on prend les positions une par une dans l’ordre lexicographique et on fait la chose suivante:
-Si la position est gagnante, on ne fait rien
-Si la position est perdante, on regarde toutes les positions qui y mènent et on les marque comme gagnantes

On n’a pas de « fausses positions perdantes » par induction sur l’ordre lexicograpique: quand on joue un coup, on obtient que des positions plus petites lexicographiquement, donc si on était gagnante on l’aurait su en considérant un des prédécesseurs, qui était perdant. 

Dans la version actuelle du jeu, on utilise le codage des positions par des entiers, mais on n’a pas fait l’algorithme ci-dessus mais quelque chose de plus naïf basé sur la preuve que toute position est gagnante ou perdante. Plus précisément, on prend les positions dans l’ordre lexicographique et, étant donné une nouvelle position, on regarde tous les coups possibles, soit l’un mène à une position perdante et alors la position est gagnante, soit non et la position est perdante. 




Des liens: 
https://www.win.tue.nl/~aeb/games/chomp.html
http://forumgeom.fau.edu/POLYA/ProblemCenter/POLYA020.html