# Nim

Resources

Good explanation by ChatGPT below.

In the game of Nim, there are multiple piles of objects. On each turn, a player can remove any number of objects from one pile. The goal is to force your opponent into a situation where they cannot make a move (all piles are empty). The key to understanding the solution lies in the xor-sum of the pile sizes.

**Xor-Sum**: The xor-sum of the pile sizes is the bitwise exclusive or (xor, denoted by ⊕\oplus⊕) of the sizes of all piles.- For example, if the pile sizes are a1,a2,…,ana_1, a_2, \ldots, a_na1,a2,…,an, the xor-sum is calculated as a1⊕a2⊕…⊕ana_1 \oplus a_2 \oplus \ldots \oplus a_na1⊕a2⊕…⊕an.

Theorem

The theorem states that the current player has a winning strategy if and only if the xor-sum of the pile sizes is non-zero.

- This is not very intuitive, it can be proven by induction

**Winning and Losing Positions**:**Losing Position**: If the xor-sum of the pile sizes is 0, the player whose turn it is will eventually lose, provided both players play optimally.**Winning Position**: If the xor-sum $=0$, the current player has a winning strategy.

### Proof Breakdown:

**Base Case**: When all piles are empty (the multiset is empty), the xor-sum is zero, and the theorem holds (the current player loses).**Induction Hypothesis**: Assume the theorem is true for all states that can be reached from the current position. That is, if you reach a state with xor-sum zero, you’re in a losing position, and if you reach a state with non-zero xor-sum, you’re in a winning position.

Let $s$ be the xor-sum of the current position. We’ll define $t$ as the XOR value of the new position that we end up in. We have 2 different scenarios:
3. **Case 1:** $s=0$ (player is in losing position)
- Consider any move the player makes by reducing a pile from size $x$ to size $y$. After the move, the xor-sum becomes: $t=s⊕x⊕y=0⊕x⊕y=x⊕y$
- Since $y<x$, it follows that $x⊕y=0$. Thus, any move results in a new position where the xor-sum is non-zero, which is a winning position for the opponent. Therefore, the current player is in a losing position.
4. **Case 2:**$s=0$ (player is in winning position)
- Now, assume $s=0$. The current player can make a move that turns the xor-sum to zero, putting the opponent in a losing position.
- Let $d$ be the index of the leading non-zero bit in the binary representation of $s$. The player will reduce the **size of a pile where the bit in position** $d$ **is set.** Let $x$ be the size of that pile.
- The player changes $x$ to $y=x⊕s$. This choice ensures that the bit at position $d$ is cleared in the new pile size $y$, making $y<x$. Therefore, the move is legal.
- Notice that we’re not choosing any arbitrary $x$. It’s true because we’re choosing an $x$ with the leading bit $d$ set
- After the move, the new xor-sum becomes: $t=s⊕x⊕y=0$
- Thus, the current player forces the game into a state with xor-sum zero, putting the opponent in a losing position.

The proof shows that if the xor-sum is zero, the current player is in a losing position, and if the xor-sum is non-zero, the current player can always make a move that forces the opponent into a losing position. Hence, the theorem holds.