SOLO-038 · Nim — soustraction par paires

L’équilibre brisé

Trouver tous les premiers coups qui garantissent la victoire, et démontrer la stratégie contre toute réponse adverse.

Corrigé — cette page contient la réponse.

La réponse exacte

Coups gagnants : 2: A−3 → (4, 13).

Le raisonnement

1. Chaque paire est un jeu impartial fini : le total de jetons diminue strictement à chaque coup. À la position (0, 0), aucun mouvement n’existe ; son nombre de Grundy vaut 0.
2. Pour une paire (a, b), construis l’ensemble des nombres atteignables en retirant 1, 2 ou 3 de A seul, de B seul, ou des deux simultanément. Le nombre de Grundy est le mex : le plus petit entier non négatif absent de cet ensemble. Calcule par sommes a+b croissantes, car tous les successeurs ont une somme plus petite.
3. Début de table, utile pour vérifier la convention : a\b | 0 1 2 3 4 5 6 7 ; 0 | 0 1 2 3 0 1 2 3 ; 1 | 1 2 0 4 1 2 0 4 ; 2 | 2 0 1 5 3 0 1 2 ; 3 | 3 4 5 6 2 7 4 5 ; 4 | 0 1 3 2 0 1 5 3 ; 5 | 1 2 0 7 1 2 0 4 ; 6 | 2 0 1 4 5 0 1 6 ; 7 | 3 4 2 5 3 4 6 5.
4. Les valeurs des paires données sont : g(12,9)=1, g(7,13)=6. Leur XOR vaut 7. Il est non nul : la position est gagnante, à condition de rejoindre un XOR nul.
5. Pour chaque coup dans la paire k, remplace uniquement son ancien nombre g par le nouveau g′ : XOR nouveau = XOR ancien ⊕ g ⊕ g′. On obtient exactement les coups gagnants suivants : 2: A−3 → (4, 13).
6. Contrôle de tous les autres coups : 1: A−1 → (11, 9) : XOR 5 ; 1: B−1 → (12, 8) : XOR 6 ; 1: A−1 et B−1 → (11, 8) : XOR 4 ; 1: A−2 → (10, 9) : XOR 6 ; 1: B−2 → (12, 7) : XOR 4 ; 1: A−2 et B−2 → (10, 7) : XOR 2 ; 1: A−3 → (9, 9) : XOR 4 ; 1: B−3 → (12, 6) : XOR 5 ; 1: A−3 et B−3 → (9, 6) : XOR 6 ; 2: A−1 → (6, 13) : XOR 1 ; 2: B−1 → (7, 12) : XOR 3 ; 2: A−1 et B−1 → (6, 12) : XOR 2 ; 2: A−2 → (5, 13) : XOR 3 ; 2: B−2 → (7, 11) : XOR 4 ; 2: A−2 et B−2 → (5, 11) : XOR 5 ; 2: B−3 → (7, 10) : XOR 5 ; 2: A−3 et B−3 → (4, 10) : XOR 3. Ils laissent chacun une somme non nulle : une réponse gagnante existe pour l’adversaire.
7. Pourquoi le critère suffit : dans une somme de XOR nul, tout coup change le nombre de Grundy d’une seule composante vers une valeur différente, donc rend le XOR non nul. Dans une somme de XOR non nul, prends le bit de poids fort du XOR et une composante qui porte ce bit ; la cible g′ = g ⊕ XOR est alors inférieure à g. Par définition du mex, chaque valeur inférieure à g est atteignable. On peut donc ramener le XOR à zéro après chaque réponse adverse.
8. La partie finit puisque le nombre total de jetons baisse. En maintenant le XOR nul après chacun de tes coups, tu ne peux pas être le joueur bloqué : (0,0) pour toutes les paires a un XOR nul. Tu prends ainsi le dernier jeton. Ce raisonnement couvre toutes les réponses adverses, sans inventer une unique continuation.
9. Pour la vérification des valeurs élevées, appliquer exactement la récurrence, jusqu’au maximum 13 de cet exercice. Une symétrie g(a,b)=g(b,a) est permise. Ne suppose aucune périodicité à partir des huit premières lignes : la preuve ici utilise la table complète.

Fausses pistes et erreurs

• Appliquer le XOR des tailles des tas : ce sont les nombres de Grundy des PAIRES qui se combinent.
• Oublier les retraits simultanés, ou autoriser deux quantités différentes lors d’un retrait simultané.
• Transposer une règle misère à cette règle normale.

{
  "pairs": [
    [
      12,
      9
    ],
    [
      7,
      13
    ]
  ],
  "grundy_values": [
    1,
    6
  ],
  "xor": 7,
  "winning_moves": [
    "2: A−3 → (4, 13)"
  ],
  "legal_first_moves": 18,
  "max_component": 13,
  "table": [
    [
      0,
      1,
      2,
      3,
      0,
      1,
      2,
      3,
      0,
      1,
      2,
      3,
      0,
      1
    ],
    [
      1,
      2,
      0,
      4,
      1,
      2,
      0,
      4,
      1,
      2,
      0,
      4,
      1,
      2
    ],
    [
      2,
      0,
      1,
      5,
      3,
      0,
      1,
      2,
      3,
      0,
      1,
      2,
      3,
      0
    ],
    [
      3,
      4,
      5,
      6,
      2,
      7,
      4,
      5,
      6,
      7,
      4,
      5,
      6,
      7
    ],
    [
      0,
      1,
      3,
      2,
      0,
      1,
      5,
      3,
      0,
      1,
      2,
      3,
      0,
      1
    ],
    [
      1,
      2,
      0,
      7,
      1,
      2,
      0,
      4,
      1,
      2,
      0,
      4,
      1,
      2
    ],
    [
      2,
      0,
      1,
      4,
      5,
      0,
      1,
      6,
      2,
      0,
      1,
      7,
      3,
      0
    ],
    [
      3,
      4,
      2,
      5,
      3,
      4,
      6,
      5,
      3,
      7,
      4,
      5,
      2,
      6
    ],
    [
      0,
      1,
      3,
      6,
      0,
      1,
      2,
      3,
      0,
      1,
      5,
      2,
      0,
      1
    ],
    [
      1,
      2,
      0,
      7,
      1,
      2,
      0,
      7,
      1,
      2,
      0,
      3,
      1,
      2
    ],
    [
      2,
      0,
      1,
      4,
      2,
      0,
      1,
      4,
      5,
      0,
      1,
      4,
      6,
      0
    ],
    [
      3,
      4,
      2,
      5,
      3,
      4,
      7,
      5,
      2,
      3,
      4,
      5,
      2,
      7
    ],
    [
      0,
      1,
      3,
      6,
      0,
      1,
      3,
      2,
      0,
      1,
      6,
      2,
      0,
      1
    ],
    [
      1,
      2,
      0,
      7,
      1,
      2,
      0,
      6,
      1,
      2,
      0,
      7,
      1,
      2
    ]
  ]
}

← Revenir à l’énoncé SOLO-038