님 게임 (Nim game)은 $0$개 이상의 돌이 있는 돌 더미 $N$개를 가지고 $2$명이서 하는 게임이다. $i$번째 돌 더미에 남아있는 돌의 개수를 $x_i$라고 하자. 플레이어는 번갈아 가면서 다음과 같은 행동을 할 수 있다.
전체 돌 더미의 마지막 돌을 가져가는 사람이 이긴다.
직관적으로 보기에는 이 게임을 이길 수 있는 최선의 전략이 있을 것 같지 않다. 한번 생각해보자.
$N = 1$일때의 님 게임을 생각해보자. 돌 더미가 하나 이므로, 선공이 해당 돌더미의 모든 돌을 가져가면 이긴다. 이같은 전략이 $N \neq 1$인 님 게임에서도 존재할까?
놀랍게도 존재한다. $x_1 \oplus x_2 \oplus \dots \oplus x_{N-1} \oplus x_{N}$을 한 값이 $0$이면 후공이 이기고, $0$이 아니면 선공이 이긴다.
왜 이런 결과가 나올까? $x_1 \oplus x_2 \oplus \dots \oplus x_{N-1} \oplus x_{N} = G$라고 해보자. 우리는 게임이 끝날때의 $G$값을 알 수 있다. 게임이 끝나면 모든 돌 더미의 돌 개수가 $0$이므로 $G$의 값 또한 $0$이 될 것이다. $G = 0$인 상태를 패배상태, $G \neq 0$인 상태를 승리상태라고 하겠다.
$Lemma \ 1.$ 패배상태의 다음 차례는 반드시 승리상태이다.
돌을 최소한 한개는 가져가야 하므로, 어떤 비트의 홀짝성은 반드시 변하게 된다. 따라서 패배상태의 다음상태는 반드시 승리상태이다.
$Lemma \ 2.$ 승리상태에서 항상 패배상태로 만들 수 있다.
각 돌 무더기의 비트들을 살펴보면 최상위 비트를 가진 돌 무더기가 존재할 것이다. 그러면 우리는 그 최상위 비트를 끄고, 나머지 비트를 자유롭게 조작해서 반드시 $G$를 $0$으로 만들 수 있다. 따라서 승리상태에서는 항상 패배상태를 만들 수 있다.
따라서 내가 선공일 때, 만약 현재 돌 무더기의 상태가 승리상태라면, 패배상태로 바꾸는 연산을 계속 함으로써 반드시 승리할 수 있다. 반대로 만약 선공일때 돌 무더기의 상태가 패배상태라면 상대가 최선의 전략을 사용한다면 선공이 이길 수 없다.