Consider a game with a pile of sticks. Alice and Bob take turns, with Alice moving first. On each turn, a player must remove , , or sticks from the pile. The player who removes the last stick wins.
We represent the state of the game as , where is the number of sticks remaining.
According to the problem statement:
Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:
A winning state is a state from which the current player can force a win if both players play optimally.
A losing state is a state from which the current player will lose if the opponent also plays optimally.
So every state of the game can be classified as either winning or losing.
Let us look at the game above:
This gives the main rule:
Using this idea, we can classify all states one by one, starting from the states where no moves are possible.
For the game above, the states from to are classified as follows:
| States | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Result | L | W | W | W | L | W | W | W | L | W | W | W | L |
Here, W means a winning state and L means a losing state.
Now consider another game with sticks.
At a state , a player may remove any number of sticks such that:
For example:
We can represent the game as a graph:
In this game, the process always ends at state , because no move is possible there. So state is a losing state.
After classifying all states, we get the following picture, where losing states are marked in red and winning states in green:
N = 7 -> Initial state (n = 7)
Alice removes 3 sticks -> New state (n = 4)
Bob removes 2 sticks -> New state (n = 2)
Alice removes 2 sticks -> New state (n = 0)