님게임은 여러개의 막대기 더미들이 있고, 두 플레이어가 번갈아가며 한 무더기에서 하나 이상의 막대기를 제거하는 게임이다.
님게임의 더 잘 이해하고 필승법을 찾으려면 다음의 nim sum과 Lemma1, 2를 아는것이 중요하다.
nim sum: 모든 줄의 막대기의 수를 XOR 연산한 값이다.
기존의 nim sum을 x, 한 턴 이후의 nim sum을 y라고 하자.
Lemma 1. 이면 항상 이다.
Lemma 2. 이면 을 만들 수 있는 방법이 반드시 하나 이상 존재한다.
Lemma 1, 2를 이용하여 만약 내가 선공이고 초기 상태의 nim sum이 0이 아니라면, 상대방이 앞으로 어떤 무더기에서 어떤 막대기를 몇개씩 빼내든 상관없이, 항상 상대방에게 nim sum이 0이 되게 만들어줄 수 있음을 알수있다.
참고자료
https://en.wikipedia.org/wiki/Nim#Proof_of_the_winning_formula
- Proof of the winning formula 부분을 보면 Lemma 1, 2 에 대한 수학적 증명을 볼 수 있다.
- Lemma 1, 2에 대한 증명을 한국어로 쉽게 풀이해놓은 글이다.