다음과 같은 게임을 생각해 봅시다. $n$개의 더미가 주어지며, 각 더미에는 몇 개의 돌이 있습니다. 한 번의 차례에 플레이어는 더미 하나를 골라 그 더미에서 0이 아닌 임의의 개수의 돌을 버릴 수 있습니다. 마지막 돌을 가져간 플레이어가 이깁니다.
조건을 약간 바꾸어 표현해 봅시다. 게임의 상태는 음이 아닌 정수들의 순서 없는 집합으로 유일하게 기술됩니다. 이들에 번호를 매기고 $i$번째 더미의 돌 개수를 $a_i$로 나타냅시다. 이제 한 번의 수에서는 임의의 수 하나를 엄격하게 감소시킬 수 있습니다. 종료 상태는 모든 수가 0이 된 상태입니다.
정리. 게임 상태는 더미 크기들의 xor 합이 0이 아닐 때, 그리고 오직 그때에만 승리 상태입니다:
$$ S = a_1 \oplus a_2 \oplus \ldots \oplus a_n \ne 0 $$증명은 귀납법으로 진행합니다.
종료 상태에서는 더 이상 더미가 없고, xor 합은 0이며, 이 상태는 실제로 지는 상태입니다. 기저 단계는 증명되었습니다. 이제 전이를 증명합시다.
xor 합이 0인 상태에서는 모든 전이가 승리 상태, 즉 합이 0이 아닌 상태로 이어집니다. 실제로 어느 더미에서든 성냥을 원하는 만큼 제거하기만 하면 됩니다. 그러면 xor-합은 0에서 $a_i \oplus b_i $로 바뀝니다. 여기서 $b_i < a_i$는 우리가 수를 둔 후 $i$번째 더미에 남은 돌의 개수입니다.
반대의 경우는 더 어렵습니다. xor 합이 0이 아니라면, xor 합이 0이 되도록 하는 $b_i < a_i$가 항상 존재한다는 것을 보여야 합니다. 즉,
$$ S \oplus a_i \oplus b_i = 0 $$이를 위해 $S$의 최상위 1 비트를 살펴보고, 이 비트 역시 1인 $a_i$를 아무거나 하나 고릅시다. 이러한 $a_i$는 적어도 하나 존재합니다. xor의 성질에 따라 그러한 수는 홀수 개여야 하기 때문입니다. 위의 조건으로부터 구하려는 $b_i$는 $S \oplus a_i$와 같아야 함을 알 수 있습니다.
이것이 올바른 새 더미 크기, 즉 $b_i < a_i$임이 밝혀집니다. 왜 그렇습니까? 식에서 상위 비트는 모두 그대로 남아 있고, $k$번째 비트는 1에서 0으로 바뀌었으며, 그 이후 비트들에 무슨 일이 일어났는지는 중요하지 않습니다. 그 변화는 분명히 $2^k$보다 크지 않기 때문입니다.
결국 최적 전략은 다음과 같습니다. 모든 $a_i$의 xor 합을 계산하고, 그 최상위 비트가 켜져 있는 $a_i$를 찾아 $S \oplus a_i$로 바꿉니다. (만약 xor 합 $S$가 0이라면 포기합니다.)
#변형
#미제르 님 (misère nim)
일반적인 님과 반대로, 마지막 수를 둔 플레이어가 이기는 것이 아니라 지는 «역님(ним в поддавки)»도 있습니다.
이러한 님의 해법은 놀라울 정도로 간단합니다. 위치의 승패는 일반 님과 마찬가지로 더미 크기들의 xor-합으로 결정되지만, 한 가지 예외가 있습니다. 모든 더미의 크기가 1이면 승리 위치와 패배 위치가 서로 뒤바뀝니다.
이 예외를 고려하여, 일반 님에서와 같이 xor 합이 0인 포지션으로 이동하는 수를 두되, 그러한 수가 모든 더미의 크기가 1인 포지션으로 이어진다면 남아 있는 비어 있지 않은 더미의 개수의 홀짝성이 바뀌도록 그 수를 수정해야 합니다.
증명. 게임의 어떤 진행 과정을 생각해 봅시다. 임의의 시작 위치를 선택하고, 게임이 끝날 때까지 플레이어들의 수를 적어 봅시다. 최적으로 플레이하는 두 플레이어의 어떤 게임에서든, 언젠가는 비어 있지 않은 모든 더미의 크기가 1이 되는 순간이 옵니다. 이 순간 비어 있지 않은 더미의 개수를 $k$로 나타냅시다. 그러면 현재 플레이어에게 이 위치는 $k$가 짝수일 때, 그리고 그때에만 이기는 위치입니다.
이제 한 수 뒤로 되돌아가 봅시다. 우리는 정확히 한 무더기의 크기가 $a_i > 1$이고 나머지 모든 무더기(0개일 수도 있습니다)의 크기가 $1$인 상태에 놓여 있었습니다. 이 위치는 이기는 위치입니다. 왜냐하면 우리는 항상 크기가 $1$인 더미가 홀수 개 남도록 하는 수를 둘 수 있기 때문입니다:
- 비어 있지 않은 더미의 총개수가 홀수이면 $a_i$를 $1$로 바꿉니다.
- 그렇지 않으면 $a_i$를 $0$으로 바꿉니다.
이어서 게임을 계속 거꾸로 거슬러 올라가 보면, 모든 상태에 대해 승패 여부 역시 「일반」 님과 일치하게 됩니다. 그 이유는 단순히, 크기가 $>1$인 더미가 둘 이상 있을 때는 모든 전이가 크기가 $>1$인 더미가 하나 이상 있는 상태로 이어지며, 이미 보였듯이 그러한 모든 상태에 대해서는 「일반」 님과 비교하여 아무것도 달라지지 않았기 때문입니다.
따라서 ‘지는 쪽이 이기는’ 님에서의 변화는 모든 더미의 크기가 1인 상태에만 영향을 미치며, 이것으로 증명이 끝납니다.
#무어의 님 (k-님)
조건. 크기가 $a_i$인 돌 더미가 $n$개 있습니다. 또한 자연수 $k$가 주어집니다. 한 번의 수에서 플레이어는 1개부터 $k$개까지의 더미의 크기를 줄일 수 있습니다(즉, 이제는 여러 더미에서 동시에 수를 두는 것이 허용됩니다). 수를 둘 수 없는 사람이 집니다.
자명하게도, $k=1$일 때 무어의 님은 일반적인 님이 됩니다.
해법. 각 더미의 크기를 이진법으로 적습니다. 그런 다음 각 자릿수별로 이 0과 1을 모두 더하고, 그 합을 $(k+1)$로 나눈 나머지를 구합니다. 모든 자릿수에서 0이 나왔다면 현재 상태는 지는 상태이고, 그렇지 않다면 이기는 상태입니다.
증명은 일반 님과 마찬가지로 플레이어들의 전략을 기술하는 방식으로 이루어지며, 다음을 보여야 합니다.
- 값이 0인 게임에서는 값이 0이 아닌 게임으로만 이동할 수 있고,
- 값이 0이 아닌 임의의 게임에서는 값이 0인 게임으로 가는 수가 반드시 존재합니다.
첫 번째 항목은 다음과 같은 논증으로 증명됩니다. 모든 자릿수에 대해 비트의 합을 $(k+1)$로 나눈 나머지가 0이었다면, 1개부터 $k$개까지의 원소를 변경한 뒤 다시 합을 0으로 만드는 것은 모든 변경을 「상쇄」하는 경우에만 가능합니다. 즉, 어떤 비트가 제거되는 모든 원소에 대해 그 비트가 추가되는 다른 원소가 있어야 합니다. 특히 이는 어떤 수에서든 적어도 하나의 비트가 바뀌는 자릿수 중 가장 높은 자릿수에 대해서도 성립해야 합니다. 그러나 그렇다면 이 자릿수에 1이 추가되고 그보다 높은 모든 자릿수에는 아무 변화도 없는 원소가 존재한다는 뜻이 됩니다. 따라서 이 원소는 원래 값보다 커지게 되며, 이는 규칙에 위배됩니다.
이제 남은 것은 합이 0이 아닌 상태에서 합이 0인 상태로 전이하는 방법을 익히는 것입니다. 비트의 합이 0이 아니게 된 위치들을 문제가 있는 위치라고 부릅시다. 모든 비트를 최상위 비트부터 최하위 비트까지 차례로 살펴보면서, 몇 개의 원소를 감소시켜 문제가 있는 각 합을 하나씩 0으로 만들어 나갑시다.
이미 변경하기 시작한 더미의 개수를 $u$라고 합시다. 처음에는 $u = 0$입니다. 이 $u$개의 더미에서는 이전의 더 상위 비트 중 어딘가를 이미 줄였으므로, 그보다 하위의 비트는 모두 원하는 대로 설정할 수 있다는 점에 주목하십시오.
$(k+1)$로 나눈 나머지 합이 0이 아닌 현재 비트를 살펴보고 있다고 합시다. 이상적으로는, 이 자리에서 어차피 이미 변경하기로 한 $u$개의 원소만 변경하여 그 합을 0으로 만들고 싶습니다. 이 $u$개의 원소 모두의 해당 자리에 머릿속으로 1을 놓고 합을 다시 계산하여, 그 값을 $s$라고 합시다. 이제 두 가지 경우를 살펴봅시다:
- $s \le u$이면 이미 선택한 원소들만으로 충분하며, 그중 $s$개에서 해당 비트의 1을 제거하면 됩니다.
- 그렇지 않고 $s > u$이면, 고려 중인 비트가 1인 추가 더미 $(s - u)$개를 찾아 이미 있는 $u$개의 더미와 함께 감소시킵니다.
각 반복이 끝나면 변경되는 더미의 수 $u$는 $u’ = \max(s, u) \le k$가 됩니다.
이와 같이 우리는 변경할 더미들의 집합과 그 더미들에서 변경해야 할 비트를 선택하여 변경하는 더미의 총개수 $u$가 결코 $k$를 넘지 않도록 하는 방법을 보였습니다. 따라서 합이 0이 아닌 상태에서 합이 0인 상태로 가는 원하는 전이가 항상 존재함을 증명하였으며, 이로써 증명이 완료됩니다.
#이것이 도대체 왜 필요합니까?
체스를 비롯한 여러 전략 게임에서 추크츠방(독일어 zug — 수, zwang — 강제에서 유래)이란 플레이어에게 더 이상 좋은 수가 남아 있지 않아서, 규칙이 허용한다면 그냥 제자리에 머문 채 상대에게 차례를 넘기고 싶은 상황을 말합니다.
상대를 추크추방으로 몰아넣는다는 아이디어에 기반한 게임은 매우 많으며, 이들은 모두 님과 동등하다는 사실이 밝혀집니다. 여기서 동등하다는 것은 개별 게임들의 합에서 누가 이기는지를 따질 때 이들 게임의 그래프가 님의 그래프와 정확히 똑같이 작동한다는 의미입니다.
이후의 글에서는 이와 같은 게임을 님으로 환원하는 방법을 살펴보겠습니다.