님 게임 필승법 — XOR 계산으로 100% 이기는 법

님 게임은 여러 줄의 성냥 중 마지막 성냥을 가져가는 쪽이 지는 게임입니다. 운으로 하는 것처럼 보이지만, 사실 완전히 수학적으로 분석된 게임이라 계산만 하면 항상 이길 수 있는 자리가 정해져 있습니다.

이진법으로 바꿔서 XOR

각 줄의 개수를 이진수로 바꾼 뒤, 자릿수별로 XOR(같으면 0, 다르면 1) 연산을 합니다. 예를 들어 3·5·7이면:

각 자리를 XOR 하면 011 → 결과가 0이 아니면 지금 두는 사람이 유리한 자리입니다.

내가 둔 뒤 남은 줄들의 XOR 값이 0이 되게 만들면, 그 뒤로 상대가 뭘 하든 내가 항상 다시 XOR 0으로 되돌릴 수 있어서 결국 내가 이깁니다. 계산이 복잡하게 느껴진다면, 일단 "가장 큰 줄을 크게 줄여보는" 시도부터 해보면서 감을 잡아도 좋습니다.

직접 계산하며 대국해보고 싶다면 님 게임에서 바로 해볼 수 있습니다.