SOLO-037 · Nim — pair subtraction

Two Workshops

Find all the first shots that guarantee victory, and demonstrate strategy against any adverse response.

This page contains the solution.

The answer

Winning shots: 1: A−1 and B−1 → (7, 10); 1: A−3 → (5, 11); 2: B−3 → (10, 4).

The reasoning

1. Each pair is a finished impartial game: the total number of chips decreases strictly at each stroke. At the position (0, 0), no movement exists; its number of Grundy is 0.
2. For a pair (a, b), build all the numbers that can be reached by removing 1, 2 or 3 A alone, B alone, or both simultaneously. The number of Grundy is the mex: the smallest non-negative integer absent from this set. Calculates by increasing amounts a+b, as all successors have a smaller sum.
3. Start of the table, useful for checking the 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. The values of the given pairs are: g(8,11)=2, g(10,7)=4. Their XOR is 6. It is not null: the position is winning, provided you join a null XOR.
5. For each move in pair k, replace its old value g with the new value g′: new XOR = old XOR ⊕ g ⊕ g′. The winning moves are exactly: 1: A−1 and B−1 → (7, 10); 1: A−3 → (5, 11); 2: B−3 → (10, 4).
6. Control of all other hits: 1: A−1 → (7, 11) : XOR 1 ; 1: B−1 → (8, 10) : XOR 1 ; 1: A−2 → (6, 11) : XOR 3 ; 1: B−2 → (8, 9) : XOR 5 ; 1: A−2 and B−2 → (6, 9) : XOR 4 ; 1: B−3 → (8, 8) : XOR 4 ; 1: A−3 and B−3 → (5, 8) : XOR 5 ; 2: A−1 → (9, 7) : XOR 5 ; 2: B−1 → (10, 6) : XOR 3 ; 2: A−1 and B−1 → (9, 6) : XOR 2 ; 2: A−2 → (8, 7) : XOR 1 ; 2: B−2 → (10, 5) : XOR 2 ; 2: A−2 and B−2 → (8, 5) : XOR 3 ; 2: A−3 → (7, 7) : XOR 7 ; 2: A−3 and B−3 → (7, 4) : XOR 1. winner exists for the opponent.
7. Why this works: when the XOR of the components is zero, a move changes one Grundy number to a different value, making the XOR nonzero. When the XOR is nonzero, choose a component with the highest set bit of the XOR. Its target g′ = g ⊕ XOR is less than g. By the definition of mex, every value below g is reachable. This lets you restore the XOR to zero after each opposing move.
8. The game ends because the total number of tokens decreases. Keeping the XOR at zero after each of your moves ensures you are never the player unable to move: (0,0) for every pair gives XOR zero. You therefore take the final token. This reasoning covers every opponent response.
9. For the verification of high values, apply exactly the recurrence, up to a maximum of 11 of this exercise. A symmetry g(a,b)=g(b,a) is permitted. Does not assume periodicity from the first eight lines: the evidence here uses the complete table.

Common mistakes and false leads

• Apply the XOR of the heap sizes: it is the Grundy numbers of the PAIRS that combine.
• Forget simultaneous withdrawals, or allow two different quantities when withdrawing simultaneously.
• Transpose a poverty rule to this normal rule.

{
  "pairs": [
    [
      8,
      11
    ],
    [
      10,
      7
    ]
  ],
  "grundy_values": [
    2,
    4
  ],
  "xor": 6,
  "winning_moves": [
    "1: A−1 et B−1 → (7, 10)",
    "1: A−3 → (5, 11)",
    "2: B−3 → (10, 4)"
  ],
  "legal_first_moves": 18,
  "max_component": 11,
  "table": [
    [
      0,
      1,
      2,
      3,
      0,
      1,
      2,
      3,
      0,
      1,
      2,
      3
    ],
    [
      1,
      2,
      0,
      4,
      1,
      2,
      0,
      4,
      1,
      2,
      0,
      4
    ],
    [
      2,
      0,
      1,
      5,
      3,
      0,
      1,
      2,
      3,
      0,
      1,
      2
    ],
    [
      3,
      4,
      5,
      6,
      2,
      7,
      4,
      5,
      6,
      7,
      4,
      5
    ],
    [
      0,
      1,
      3,
      2,
      0,
      1,
      5,
      3,
      0,
      1,
      2,
      3
    ],
    [
      1,
      2,
      0,
      7,
      1,
      2,
      0,
      4,
      1,
      2,
      0,
      4
    ],
    [
      2,
      0,
      1,
      4,
      5,
      0,
      1,
      6,
      2,
      0,
      1,
      7
    ],
    [
      3,
      4,
      2,
      5,
      3,
      4,
      6,
      5,
      3,
      7,
      4,
      5
    ],
    [
      0,
      1,
      3,
      6,
      0,
      1,
      2,
      3,
      0,
      1,
      5,
      2
    ],
    [
      1,
      2,
      0,
      7,
      1,
      2,
      0,
      7,
      1,
      2,
      0,
      3
    ],
    [
      2,
      0,
      1,
      4,
      2,
      0,
      1,
      4,
      5,
      0,
      1,
      4
    ],
    [
      3,
      4,
      2,
      5,
      3,
      4,
      7,
      5,
      2,
      3,
      4,
      5
    ]
  ]
}

← Return to puzzle SOLO-037