돌무더기 여러 개를 놓고 두 사람이 번갈아 돌을 가져가요. 규칙은 딱 두 가지예요. 한 번에 한 무더기에서만 가져갈 수 있고, 가져가는 개수는 1개든 전부든 자유예요. 마지막 돌을 가져가는 사람이 이겨요. 이렇게 간단한 규칙인데, 놀랍게도 누가 이길지 게임을 시작하기 전에 완벽하게 예측할 수 있는 방법이 있어요.
비밀은 각 무더기의 돌 개수를 XOR(배타적 논리합)이라는 연산으로 계산하는 거예요. XOR은 두 수를 2진수로 놓고 자릿수마다 비교해서, 같으면 0, 다르면 1로 만드는 연산이에요. 예를 들어 무더기가 [3, 4, 5]라면, 2진수로 3=011, 4=100, 5=101이에요. 자릿수마다 XOR하면: 첫째 자리 0⊕1⊕1=0, 둘째 자리 1⊕0⊕0=1, 셋째 자리 1⊕0⊕1=0. 그래서 XOR 값은 010, 즉 2가 나와요.
이 XOR 값(님-합이라고 불러요)이 0이 아니면, 지금 차례인 사람에게 반드시 이길 수 있는 수가 있어요. 각 무더기 개수를 XOR값과 다시 XOR해봐서, 그 결과가 원래 개수보다 작아지는 무더기를 찾으면 돼요. [3,4,5]에서 XOR은 2였는데, 5 XOR 2=7과 4 XOR 2=6은 오히려 커지니 불가능하고, 3 XOR 2=1은 작아지니 가능해요. 그래서 첫 번째 무더기(3개)에서 2개를 가져가 1개만 남기면 무더기가 [1,4,5]가 되고, 이때 XOR은 1⊕4⊕5=0이 됩니다.
반대로 XOR이 이미 0이라면, 지금 차례인 사람은 불리한 위치예요. 상대가 완벽하게 두는 한, 어떤 수를 두어도 XOR이 다시 0이 아닌 상태가 되고, 그러면 상대가 또 XOR을 0으로 되돌리는 걸 반복하다가 결국 상대가 마지막 돌을 가져가게 돼요. 그래서 님 게임의 필승 전략은 아주 단순해요 — "항상 내 차례가 끝날 때 XOR이 0이 되도록 만들어라."
왜 하필 XOR일까요? XOR은 "짝을 맞춰 없애는" 성질이 있어요. 게임이 끝났을 때(모든 무더기가 0일 때) XOR도 당연히 0이에요. 그리고 XOR이 0인 상태에서는 어떤 무더기 하나만 줄이면 반드시 XOR이 0이 아니게 바뀌어요(한 무더기만 바뀌면 균형이 깨지니까요). 반대로 XOR이 0이 아닐 때는, 그 불균형을 정확히 상쇄하는 무더기가 항상 존재해서 XOR을 다시 0으로 만들 수 있어요. 이 두 성질이 맞물려서, "XOR=0을 유지하며 상대에게 넘기면 언젠가 상대가 궁지에 몰린다"는 필승 전략이 성립하는 거예요.
저희 체험 페이지에서는 컴퓨터가 정확히 이 XOR 전략으로 두기 때문에, 컴퓨터가 유리한 위치에서 시작하면 이기기 정말 어려워요. 하지만 힌트 버튼으로 매 순간 XOR 값과 추천 수를 확인하면서 두면, 여러분도 컴퓨터를 상대로 이길 수 있어요. 여러 무더기 구성을 시도해보면서, 시작하자마자 XOR이 0인지(내가 불리한지) 아닌지 먼저 확인하는 습관을 들여보세요.