님 게임·그런디 수 계산기

무더기 크기를 모두 XOR한 값(님 합)이 0이면 지금 차례인 쪽이 지고, 0이 아니면 이깁니다. 양쪽이 최선을 다한다는 전제입니다. 1·3·5·7처럼 님 합이 0인 배치는 후공이 이기고, 3·4·5처럼 0이 아니면 선공이 이깁니다.

XOR이 0이라는 것은 이진수로 세워 놓았을 때 자리마다 1의 개수가 짝수라는 뜻이기 때문입니다. 그 상태에서 어느 무더기를 어떻게 줄이든 적어도 한 자리의 개수가 홀수로 바뀌므로 XOR이 0이 아니게 됩니다. 거꾸로 XOR이 0이 아니면 가장 높은 1이 선 자리에 1을 가진 무더기가 반드시 있고, 그것을 줄여 다시 짝을 맞출 수 있습니다.

무더기 a마다 a ⊕ (님 합)을 셈해, 그 값이 a보다 작으면 그 크기로 줄이면 됩니다. 줄인 뒤의 XOR이 0이 되기 때문입니다. 3·4·5라면 님 합이 2이므로 3 ⊕ 2 = 1이 3보다 작아, 첫 무더기를 3에서 1로 줄이는 것이 유일한 답입니다.

2개 이상인 무더기가 하나라도 남아 있으면 판정이 보통 님과 똑같고, 모든 무더기가 0이나 1뿐일 때만 뒤집혀 「남은 무더기 수가 짝수여야 이긴다」가 됩니다. 큰 무더기가 있는 동안에는 1만 남는 판을 몇 개로 만들지를 이기는 쪽이 마음대로 고를 수 있어, 마지막 순간에만 규칙 차이가 드러나기 때문입니다. 이 예외를 빠뜨리고 XOR만 보면 마지막 몇 수에서 정반대 답을 줍니다.

무더기 크기를 그대로 쓰지 않고 그런디 수 g(n) = n mod (k+1)로 바꿔 XOR합니다. 한 무더기만 놓고 보면 (k+1)의 배수가 지는 자리이고, 그 주기가 그대로 그런디 수가 됩니다. 스프라그–그런디 정리가 「독립된 게임 여럿의 합은 각자의 그런디 수를 XOR한 것과 같다」고 말해 주므로 보통 님과 똑같이 다룰 수 있습니다.

상대의 실수를 노리는 수밖에 없습니다. 판정은 양쪽이 최선을 다한다는 전제이므로, 상대가 한 번이라도 님 합을 0이 아닌 채로 넘기면 바로 뒤집힙니다. 크고 어중간한 무더기를 남겨 판을 복잡하게 만드는 것이 현실적인 대응이고, 무더기가 적고 작을수록 실수가 나올 여지도 줄어듭니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.