413_Nim.md

Nim & others

Game: Two players take turns to choose from 1 to 10. Add each number to a total sum. The first one who reaches 100 wins.

Strategy: The first player has the winning strategy:

• Choose 1 first
• Second player chooses $x$, then the first player choose $11-x$
• In this patter, the first player reaches $89$ first, which leads to a triumph.

Game: Matchstick.

There are $n$ matchstickes on the table. Two players take turns to take $1, 2, 3$ sticks. The player who takes the last match stick loses.

Strategy:

Consider tha patterns:

# Stickes	Winner
1	2
2	1
3	1
4	1
5	2
6	1
7	1
8	1
9	2

Observation The first player of the $n$ game can be seen as the second player of games $n-1, n-2, n-3$.

The second player wins if $n \equiv 1 \mod 4$.

Game: Nim.

• There are many piles of stones.
• Two players take turns to choose one pile, and then remove any number (at least one) of stones from that pile.
• The last one to empty all the piles wins.

Strategy:

For the cases of two piles:

• If two piles don't have same number, then the first player wins.

• If two piles have same number, then the second player wins