Library

DFA · Regular

Nim with five sticks

Two players take 1 or 2 sticks in turn, and whoever takes the last one wins. The accepted words are the games the first player wins. Every losing position for the player to move has a multiple of 3 sticks — the first player wins by taking 2, then always making the total taken in a round 3.

5·P14·P23·P23·P12·P11·P12·P2P1_wins1212121211
The machine as drawn — 8 states, 10 transitions.Every word up to length 8, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

122 → accept11111 → accept212 → accept221 → accept222 → reject21111 → reject112 → reject121 → reject