SOLO-039 · Nim — pair subtraction
EXTREMEThree Linked Fronts
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−3 → (14, 19); 2: A−3 → (11, 18).
The reasoning
- 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.
- 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.
- 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.
- The values of the given pairs are: g(17,19)=5, g(14,18)=1, g(20,15)=2. Their XOR is 6. It is non-zero: the position is winning, provided you join a null XOR.
- 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−3 → (14, 19); 2: A−3 → (11, 18).
- Control of all other hits: 1: A−1 → (16, 19) : XOR 1 ; 1: B−1 → (17, 18) : XOR 3 ; 1: A−1 and B−1 → (16, 18) : XOR 7 ; 1: A−2 → (15, 19) : XOR 11 ; 1: B−2 → (17, 17) : XOR 1 ; 1: A−2 and B−2 → (15, 17) : XOR 4 ; 1: B−3 → (17, 16) : XOR 2 ; 1: A−3 and B−3 → (14, 16) : XOR 1 ; 2: A−1 → (13, 18) : XOR 7 ; 2: B−1 → (14, 17) : XOR 7 ; 2: A−1 and B−1 → (13, 17) : XOR 5 ; 2: A−2 → (12, 18) : XOR 4 ; 2: B−2 → (14, 16) : XOR 5 ; 2: A−2 and B−2 → (12, 16) : XOR 7 ; 2: B−3 → (14, 15) : XOR 1 ; 2: A−3 and B−3 → (11, 15) XOR 2 ; 3: A−1 → (19, 15) : XOR 12 ; 3: B−1 → (20, 14) : XOR 1 ; 3: A−1 and B−1 → (19, 14) : XOR 7 ; 3: A−2 → (18, 15) : XOR 2 ; 3: B−2 → (20, 13) : XOR 5 ; 3: A−2 and B−2 → (18, 13) : XOR 4 ; 3: A−3 → (17, 15) : XOR 3 ; 3: B−3 → (20, 12) : XOR 4 ; 3: A−3 and B−3 → (17, 12) : XOR 5. They each leave a non-zero sum: a winning answer exists for the adversary.
- 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.
- 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.
- For the verification of high values, apply exactly the recurrence, up to a maximum of 20 of this exercise. A symmetry g(a,b)=g(b,a) is allowed. 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.
How we verified this answer
Accurate dynamic programming of Grundy numbers, control of the mex and all the first moves. The sum property is demonstrated in the fix.
{
"pairs": [
[
17,
19
],
[
14,
18
],
[
20,
15
]
],
"grundy_values": [
5,
1,
2
],
"xor": 6,
"winning_moves": [
"1: A−3 → (14, 19)",
"2: A−3 → (11, 18)"
],
"legal_first_moves": 27,
"max_component": 20,
"table": [
[
0,
1,
2,
3,
0,
1,
2,
3,
0,
1,
2,
3,
0,
1,
2,
3,
0,
1,
2,
3,
0
],
[
1,
2,
0,
4,
1,
2,
0,
4,
1,
2,
0,
4,
1,
2,
0,
4,
1,
2,
0,
4,
1
],
[
2,
0,
1,
5,
3,
0,
1,
2,
3,
0,
1,
2,
3,
0,
1,
2,
3,
0,
1,
2,
3
],
[
3,
4,
5,
6,
2,
7,
4,
5,
6,
7,
4,
5,
6,
7,
4,
5,
6,
7,
4,
5,
6
],
[
0,
1,
3,
2,
0,
1,
5,
3,
0,
1,
2,
3,
0,
1,
2,
3,
0,
1,
2,
3,
0
],
[
1,
2,
0,
7,
1,
2,
0,
4,
1,
2,
0,
4,
1,
2,
0,
4,
1,
2,
0,
4,
1
],
[
2,
0,
1,
4,
5,
0,
1,
6,
2,
0,
1,
7,
3,
0,
1,
2,
3,
0,
1,
2,
3
],
[
3,
4,
2,
5,
3,
4,
6,
5,
3,
7,
4,
5,
2,
6,
4,
5,
7,
6,
4,
5,
7
],
[
0,
1,
3,
6,
0,
1,
2,
3,
0,
1,
5,
2,
0,
1,
5,
3,
0,
1,
2,
3,
0
],
[
1,
2,
0,
7,
1,
2,
0,
7,
1,
2,
0,
3,
1,
2,
0,
4,
1,
2,
0,
4,
1
],
[
2,
0,
1,
4,
2,
0,
1,
4,
5,
0,
1,
4,
6,
0,
1,
7,
2,
0,
1,
6,
3
],
[
3,
4,
2,
5,
3,
4,
7,
5,
2,
3,
4,
5,
2,
7,
3,
5,
4,
6,
7,
5,
2
],
[
0,
1,
3,
6,
0,
1,
3,
2,
0,
1,
6,
2,
0,
1,
4,
2,
0,
1,
3,
2,
0
],
[
1,
2,
0,
7,
1,
2,
0,
6,
1,
2,
0,
7,
1,
2,
0,
3,
1,
2,
0,
4,
1
],
[
2,
0,
1,
4,
2,
0,
1,
4,
5,
0,
1,
3,
4,
0,
1,
6,
2,
0,
1,
3,
5
],
[
3,
4,
2,
5,
3,
4,
2,
5,
3,
4,
7,
5,
2,
3,
6,
4,
5,
7,
6,
8,
2
],
[
0,
1,
3,
6,
0,
1,
3,
7,
0,
1,
2,
4,
0,
1,
2,
5,
0,
1,
4,
2,
0
],
[
1,
2,
0,
7,
1,
2,
0,
6,
1,
2,
0,
6,
1,
2,
0,
7,
1,
2,
0,
5,
1
],
[
2,
0,
1,
4,
2,
0,
1,
4,
2,
0,
1,
7,
3,
0,
1,
6,
4,
0,
1,
3,
6
],
[
3,
4,
2,
5,
3,
4,
2,
5,
3,
4,
6,
5,
2,
4,
3,
8,
2,
5,
3,
4,
2
],
[
0,
1,
3,
6,
0,
1,
3,
7,
0,
1,
3,
2,
0,
1,
5,
2,
0,
1,
6,
2,
0
]
]
}Build a Grundy table with two variables, assemble three components by XOR, list all the winning hits and prove the universal answer. The difficulty is on several combined tools, not on a long calculation of isolated chips. Editorial evaluation based on the required techniques; not calibrated by a human panel.