Jeu de Wythoff - Strategie

On dispose de 2 ou plus tas d'allumettes.
A tour de rôle, chaque joueur prend autant d'allumettes qu'il veut dans un ou deux tas.
S'il prend dans deux tas, il en prend autant dans chacun.
Celui qui prend la ou les dernières allumettes a gagné.

Avec deux tas, l'analyse peut se faire facilement sur un quadrillage avec comme coordonnées le nombre d'allumettes dans chaque tas.
Il faut atteindre la position gagnée (0,0).
Pour cela il faut donner à l'adversaire une position telle que quoiqu'il joue, il nous permettra d'arriver à cette position (0,0).
Toutes les cases (0,x), (x,0) et (x,x) nous permettent d'atteindre (0,0).
Il faut que l'adversaire soit contraint de jouer sur une de ces cases.
La plus proche case pas dans cette liste est la case (1,2), ou (2,1).
En donnant cette position à l'adversaire il est forcé de jouer sur (1,1), (0,1) ou (0,2), ou leur symétrique.

De proche en proche on construit ainsi la liste des "positions clé".
De toute autre position, on peut atteindre une position clé, d'une position clé on ne peut pas atteindre une autre position clé.

La liste des positions clés est ainsi :

rang012345678...
x01346891112...
y02571013151820...

Cette table peut se calculer aisément : On commence par le rang 0, position (0,0).
Le rang 1 a pour x le plus petit nombre pas trouvé : 1, et y = x + rang = 1 + 1 = 2
Au rang suivant le plus petit pas deja trouvé est 3 et y = x + rang = 5. etc...

W.A. Wythoff a montré que ces nombres sont xn = [n.φ],
la partie entière des multiples du nombre d'or φ = (1+√5)/2 ≈ 1.6180339887...
et yn = [n.φ²], partie entière des multiples du carré de φ
Tous les nombres entiers apparaissent une fois et une seule dans l'une des suites x ou y.

Les positions clés sont aussi données par des suites de Fibonacci :
1, 2, 3, 5, 8, 13, 21, 34... qui donne en groupant les termes par paires : (1,2), (3,5), (8,13), (21,24)...
la première paire n'apparaissant pas dans cette suite est (4,7).
On peut former une suite "à la Fibonacci" 4, 7, 11, 18, 29, 47... qui donne les paires (4,7), (11,18), (29,47)...

Les suites xn, yn sont ainsi engendrées par un ensemble infini de suites de Fibonacci à partir des positions "primitives" :
(1,2), (4,7), (6,10), (9,15)...
R. Silber à montré qu'une paire est primitive si et seulement si son rang est dans la suite xn.

Représentons un nombre n en "notation de Fibonacci", c'est à dire avec des "Fits" 1 pour chaque plus grand nombre de Fibonacci contenu dans n.
En partant de la suite de Fibonacci 1, 2, 3, 5, 8, 13, 21, 34...
Par exemple le nombre 30 = 21 + 8 + 1 = 1010001F
Il y a plusieurs représentations possibles : 30 = 21+5+3+1 = 13+8+5+3+1
Nous nous intéresserons à la représentation "canonique", avec les plus grands Fits possibles.
Alors il n'y a jamais deux Fits à 1 consécutifs.
La suite de Fibonacci elle même est alors 1, 10, 100, 1000, 10000....
Les termes de la suite xn sont les termes de rang impair, c'est à dire ceux se terminant par un nombre pair de 0.
Le terme yn correspondant est obtenu en ajoutant un zéro.
On obtient de même les paires dérivées de la suite de Fibonacci démarrant à 4 = 101
101, 1010, 10100, 101000 ...
Celles dérivées de la suite commençant à 6 : 1001, 10010, 100100, 1001000...

Ceci donne un critère pour que (x,y) soit une position clé :

 (x,y) clé, x<y <=> x se termine par un nombre pair de zéros, y étant obtenu en ajoutant un zéro à x. 

Par exemple la position (11, 18) = (10100F, 101000F) est une position clé
La position (7, 11) = (1010F, 10100F) ne l'est pas : le plus petit a un nombre impair de zéros
La position (11, 13) = (10100F, 100000F) non plus : le plus grand n'est pas le plus petit avec un zéro.

Reste à déterminer le coup à jouer pour ramener à une position clé.
Trois cas peuvent se présenter :

  1. Le plus petit x se termine par un nombre pair de zéros, le plus grand est supérieur à x plus un zéro.
    Il suffit de retirer au plus grand ce qui est en trop.
    Exemple : (11, 20) = (10100F, 101010F) 101010>101000, retirer 2 de 20 → (11, 18)

  2. Le plus grand y se termine par un nombre impair de zéros, le plus petit est supérieur a y sauf un zéro.
    Retirer ce qui est en trop du plus petit.
    Exemple : (19, 20) = (101001F, 101010F) 101001>10101, retirer 7 de 19 → (12, 20)

  3. Sinon, il faut retirer une même quantité aux deux.
    Soit d = |y - x|, d va rester constant.
    Comme les positions clés ont yn = xn + n, la position clé à atteindre a le rang d.
    On cherche donc xn = a0f0 + a1f1 + a2f2 +...+ aifi et yn = 0.f0 + a0f1 + a1f2 + a2f3 +...+ aifi+1
    avec yn - xn = d = |y - x|
    Comme on veut xn se terminant par un nombre pair de zéros, le plus simple est d'imposer a0 = 1
    d = yn - xn = a0(f1-f0) + a1(f2-f1) + a2(f3-f2) +...+ ai(fi+1-fi) = a0.1 + a1f0 + a2f1 +...+ aifi-1
    ou encore : d - 1 = a1f0 + a2f1 +...+ aifi-1
    D'où la règle : exprimer d - 1 en notation de Fibonacci, ajouter un 1 à droite donne xn, puis un zéro donne yn.
    Exemple : (14, 19) = (100001F, 101001F) ne satisfait pas aux critères précédents.
    d = 5 et d-1 = 101F donne la paire (1011F, 10110F) = (8, 13)
    Noter que ces représentations ne sont pas canoniques.

Qui perd gagne

C'est à dire que celui qui prend la ou les dernières a perdu.
Les positions clés sont les mêmes à l'exception des derniers coups :

rang012345678...
x02346891112...
y12571013151820...

On jouera donc comme au jeu direct tant que les coups donnent au moins 3 allumettes.
Si le coup normal donne moins, on compensera pour les positions clés du qui perd gagne (0, 1) et (2, 2).
Par exemple la position (3, 4) conduirait normalement à (1, 2) qu'il faudra changer en (0, 1).
La position (2, 5) conduirait normalement à (2, 1) qu'il faudra changer en (2, 2).

 

Accueil Arithmétiques Géométrique Divers Thèmes Scripts Jeux Exercices Parent