필승 전략 게임: 스프라그-그런디 정리(Sprague-Grundy Theorem)와 그런디 수(Grundy Number), 님 게임(Nim Game)

게임의 룰을 아십니까?

수학에서 말하는 게임이란

  • 여러 명의 참가자가 있고,
  • 게임판이 가질 수 있는 상태 집합이 있고,
  • 각 게임판 상태에서 각 참가자마다 취할 수 있는 행동 집합이 존재하여 어떤 행동을 하면 게임판의 상태가 바뀌는 것

으로 정의합니다. 저 행동 집합이 바로 “게임의 규칙”을 이루죠. 가장 예로 많이 드는 게임이 바로 체스로, 두 명이 참가하고 체스판의 상태 집합(어떤 말이 어디 놓여있나)이 있으며 각 상태에서 해당 순서의 참가자가 취할 수 있는 행동 집합(어떤 말을 어디로 옮긴다)이 존재하여 이 행동을 하면 체스판의 상태가 바뀝니다. 우리가 흔히 생각하는 보드 게임, 비디오 게임 뿐만 아니라 기업이나 생물 사이의 생존 경쟁 또한 상태 집합과 행동 집합을 적절히 정의하여 게임으로 다룰 수 있습니다.

게임의 분류

순차적 게임(sequential game): 여러 사람이 차례를 가지고 순서대로 돌아가면서 하는 게임. 게임 이론에서 유명한 죄수의 딜레마는 두 죄수가 동시에 선택을 하고 각 죄수는 상대방이 어떤 선택을 했는지 자신이 선택하기 전에는 모르기 때문에 순차적 게임이 아닙니다.

완전 정보 게임(perfect information game): 모든 참가자가 게임에 대한 모든 정보를 공유하는 게임. 포커는 남의 카드를 내가 알 수 없기 때문에 완전 정보 게임이 아닙니다.

공정 게임(impartial game): 행동 집합이 참가자와 상관 없고 게임판의 상태에 따라서만 결정되는 게임. 바둑은 두 사람의 행동 집합이 다르기 때문에(두 사람이 놓을 수 있는 돌이 나뉘어 있습니다) 공정한 게임이 아닙니다.

노멀 게임(normal game): 자기 차례에 할 수 있는 행동이 하나도 없으면 패배하는 게임. 체스에서 체크메이트를 당하면 이를 의무적으로 피해야 하는데 그럴 수 없으면 패배하죠. 따라서 체스는 노멀 게임입니다.

예제: 돌 가져가기 게임

흔히 술자리에서 배스킨라빈스 31이란 이름으로 많이 하는 게임입니다. 돌이 $n$개 있는 돌무더기가 있고, 두 사람이 차례로 돌을 1개, 2개, 또는 3개 가져갈 수 있습니다(아예 가져가지 않을 수는 없습니다). 마지막 돌을 가져가는 사람이 이긴다고 할 때(즉, 남이 돌을 못 가져가게 하면 승리) 선공과 후공 중 누가 이길까요?

이 게임은 위 네 가지 게임 분류를 모두 만족합니다. 여기에 추가로 유한한 단계 안에 끝나는 것이 보장이 되는 게임이죠(체스는 안 그렇습니다. 양쪽 다 킹만 가지고 있다면?). 이 게임이 어떻게 진행되는지 보기 위해 예시로 돌이 5개인 경우를 살펴봅시다.

돌 개수 행동
5 선공이 돌 1개를 가져감
4 후공이 돌 1개를 가져감
3 선공이 돌 1개를 가져감
2 후공이 돌 1개를 가져감
1 선공이 돌 1개를 가져감
0 후공이 가져갈 수 있는 돌이 없음. 후공 패배.

어째 둘 다 1개씩만 가져가다 게임이 끝나버렸습니다. 재미없는 판이긴 하지만 각 차례에서 행동 집합을 분석해보면 그리 간단하지 않습니다.

6번째 차례에서 후공의 행동 집합은 공집합 $\{\}$이므로 후공이 패배했습니다. 이 행동 집합을 $*0$이라 합시다.

5번째 차례에서 선공이 할 수 있는 행동은 돌 하나를 가져가는 것 밖에 없습니다. 여기서 행동을 어떻게 기호로 표현할까요? 돌이 하나 남았는데 이걸 가져가버리면 다음 차례에 행동 집합이 $*0$이 되니까, 돌을 하나 가져가는 행동은 달리 말해 “행동 집합을 $*0$으로 만드는 행동”이라 할 수 있습니다. 이 행동을 그냥 행동 집합과 같은 기호 $*0$로 씁시다. 기호는 공유하지만 행동 집합 $*0$과 행동 $*0$을 구분하는 데 유의하세요! 최종적으로 이 차례에서 선공의 행동 집합은 $\{*0\}$이고, 간단히 $*1$이라 합시다.

4번째 차례에서 후공은 돌을 1개 또는 2개 가져갈 수 있습니다. 돌을 2개 가져가면 돌이 하나도 남지 않으므로 이 행동은 $*0$으로 표현할 수 있고, 돌을 1개 가져가면 돌이 1개 남으므로 이 행동은 $*1$입니다. 따라서 이때 후공의 행동 집합은 $\{*0, *1\}$이고, 간단히 $*2$라 합시다.

3번째 차례에서 선공은 돌을 1개, 2개, 또는 3개 가져갈 수 있습니다. 1개를 가져가면 돌이 두 개 남는데, 이는 4번째 차례와 동일한 상황이 되므로 이 행동은 $*2$입니다. 마찬가지로 돌을 2개 가져가는 행동은 $*1$, 3개 가져가는 행동은 $*0$이므로 선공의 행동 집합은 $\{*0, *1, *2\}$이고, 역시 간단히 $*3$이라 하겠습니다. 일반적으로 음이 아닌 정수 $n$에 대해 $*n$을 다음과 같이 정의합시다.

\[ *0=\{\}, \qquad *(n+1) = \{*0, *1, *2, \cdots, *n\} = *n \cup \{*n\} \]

2번째 차례에서 후공이 돌을 1개 가져가면 $*3$, 2개를 가져가면 $*2$, 3개를 가져가면 $*1$이 되므로 행동 집합은 $\{*1,*2,*3\}$입니다.

1번째 차례에서 선공의 행동 집합은 $\{*2, *3, \{*1, *2, *3\}\}$입니다.

생각해보면 공정 게임의 특성상 행동 집합은 게임판의 상태, 즉 남은 돌의 개수에만 상관 있으므로 돌의 개수에 따른 행동 집합을 정리해보면 다음과 같습니다.

돌의 개수 행동 집합
0 $*0$
1 $*1$
2 $*2$
3 $*3$
4 $\{*1, *2, *3\}$
5 $\{*2, *3, \{*1, *2, *3\}\}$
6 $\{*3, \{*1, *2, *3\}, \{*2, *3, \{*1, *2, *3\}\}\}$
7 $\{\{*1, *2, *3\}, \{*2, *3, \{*1, *2, *3\}\}, \{*3, \{*1, *2, *3\}, \{*2, *3, \{*1, *2, *3\}\}\}\}$

그런디 수

위에서 행동 집합을 나타낼 때 쓴 $*n$을 그런디 수(Grundy number) 또는 님버(nimber)라고 합니다(사실 말이 “수”지 실제론 집합입니다). 돌의 개수가 3개 이하일 땐 행동 집합이 그런디 수 하나로 그냥 나타내어지지만 4개부턴 그런디 수의 집합이나 집합족이 되어 아주 복잡해집니다. 다행히 이런 경우도 대응되는 그런디 수 하나로 바꿀 수 있습니다. 이는 밑에서 다루겠습니다.

동시에 두 게임을 같이 한다면?

두 게임 $\mathbf A$와 $\mathbf B$의 합 $(\mathbf A, \mathbf B)$를 다음과 같이 정의합시다. 각 차례마다 참가자는 두 게임 중 하나를 골라 고른 게임의 행동 집합에서 한 행동을 취합니다. 이때 다른 게임은 절대 건드리지 않습니다. 동시에 두 게임을 같이 하는 셈이죠.

예를 들어 위의 돌 가져가기 게임을 돌 5개짜리 돌무더기와 돌 2개짜리 돌무더기에서 동시에 게임을 한다고 해보죠. 먼저 돌이 5개인 돌 가져가기 게임에서 선공의 행동 집합은

\[ \color{blue} G = \color{blue}{\{*2, *3, \{*1, *2, *3\}\}} \]

돌이 2개일 때 선공의 행동 집합은

\[ \color{red} {G’} = \color{red}{*2} = \color{red}{\{*0,*1\}} \]

게임 $\mathbf A$의 행동 집합이 $A$이고 게임 $\mathbf B$의 행동 집합이 $B$일 대 합쳐진 게임 $(\mathbf A, \mathbf B)$의 행동 집합을 $A+B$라 씁시다. $(\mathbf A, \mathbf B)$에서 할 수 있는 행동은 $A$에서 행동 하나($a$라고 합시다)를 하거나 $B$에서 행동 하나($b$라고 합시다)를 하거나 둘 중 하나인데, 전자는 행동 집합이 $a+B$가 되고 후자는 행동 집합이 $A+b$가 되므로 $A+B$를 아래와 같이 재귀적으로 표현할 수 있습니다.

\[ A+B = \{A + b \ | \ b \in B\} \cup \{a + B \ | \ a \in A\} \]

위 예시에서는

\[ \color{blue} G + \color{red} {G’} = \{
\color{blue}{*2} + \color{red}{G’},
\color{blue}{*3} + \color{red}{G’},
\color{blue}{\{*1,*2,*3\}} + \color{red}{G’} \} \cup \{
\color{blue}G + \color{red}{*0},
\color{blue}G + \color{red}{*1}
\} \]

행동 집합의 “덧셈”은 교환법칙과 결합법칙을 만족합니다. 교환법칙은 정의에 의해 자명하고, 결합법칙은 $(\mathbf A, \mathbf B)$와 $\mathbf C$를 더하든 $\mathbf A$와 $(\mathbf B, \mathbf C)$를 더하든 결국 각 차례마다 $\mathbf A$, $\mathbf B$, $\mathbf C$ 셋 중 한 게임을 골라서 행동을 취하는 것이 된다는 것으로 증명할 수 있습니다. 결합법칙이 성립하므로 세 게임의 합을 간단하게 $(\mathbf A, \mathbf B, \mathbf C)$로 씁시다.

$\mathcal P$-행동 집합과 $\mathcal N$-행동 집합

항상 유한한 차례 안에 끝나는 2인용 순차적, 완전 정보, 공정, 노멀 게임의 모든 행동 집합은 두 가지로 나눌 수 있습니다. 첫째는 이번 차례의 참가자가 무조건 이기는 차례의 행동 집합들로, $\mathcal N$-행동 집합($\mathcal N$-position)이라고 합니다. 다른 하나는 이전 차례의 참가자가 무조건 이기는 차례의 행동 집합들로, $\mathcal P$-행동 집합($\mathcal P$-position)이라고 합니다. 노멀 게임의 경우 내 차례에 행동 집합이 $*0$이 되면 패배하기 때문에 $*0$은 $\mathcal P$-행동 집합에 속하고, 내 차례에 $*1$이 되면 다음 상대방 차례엔 $*0$이 되어 내가 이길 수 밖에 없기 때문에 $*1$은 $\mathcal N$-행동 집합에 속합니다.

만약 현재 행동 집합에 $\mathcal P$-행동 집합에 속하는 행동이 존재한다면 현재 행동 집합은 $\mathcal N$-행동 집합에 속하고, 모든 행동이 $\mathcal N$-행동 집합에 속한다면 현재 행동 집합은 $\mathcal P$-행동 집합에 속하게 됩니다.

행동 집합의 동등

두 행동 집합 $A$와 $B$가 다음을 만족하면 동등하다고 하고, $A\approx B$로 나타냅니다.

임의의 행동 집합 $G$에 대해 $A+G$와 $B+G$가 둘 다 $\mathcal N$-행동 집합에 속하거나 둘 다 $\mathcal P$-행동 집합에 속한다.

한 마디로 게임 $\mathbf A$와 $\mathbf B$가 있는데 어떤 게임 $\mathbf G$를 들고 오더라도 $(\mathbf A, \mathbf G)$의 전략과 $(\mathbf B, \mathbf G)$의 전략이 완전히 똑같으면 두 게임을 같은 것으로 보자는 이야기죠. 또 정의에 따라 $A\approx B$이고 $B\approx C$이면 $A\approx C$임이 증명됩니다. $A\approx B$이면 $B\approx A$인 건 말할 것도 없고요.

이제부턴 이 글의 제목인 스프라그-그런디 정리의 보조 정리 두 개를 증명하고 가겠습니다.

보조정리 1

행동 집합 $A$가 $\mathcal P$-행동 집합에 속하면 임의의 행동 집합 $G$에 대해 $G \approx A+G$이다.

증명) 정의에 의해 임의의 행동 집합 $H$에 대해 $G+H$와 $A+G+H$가 둘 다 $\mathcal N$-행동 집합이거나 $\mathcal P$-행동 집합임을 증명하면 됩니다.

$G+H$가 $\mathcal P$-행동 집합이라고 가정해봅시다. 즉, 내 차례에 행동 집합이 $G+H$인데 상대방이 필승 전략을 가지고 있어서 내가 어떻게 행동을 취하든 절대 이길 수 없습니다. 그런데 $A$도 $\mathcal P$-행동 집합이므로 상대방은 이쪽 게임에서도 필승 전략을 가지고 있습니다. 그럼 상대방 입장에서는 다음과 같이 게임 $\mathbf A$와 $(\mathbf G, \mathbf H)$의 합에서 필승 전략을 세울 수 있습니다.

  • 내가 $\mathbf A$를 골라서 행동을 취할 경우: $\mathbf A$에서 필승 전략을 구사해서 막아버립니다.
  • 내가 $(\mathbf G, \mathbf H)$를 골라서 행동을 취할 경우: 역시 필승 전략을 구사해서 막아버립니다.

어떻게 하든 질 수 밖에 없죠. 따라서 $A+G+H$도 $\mathcal P$-행동 집합에 속합니다.

$G+H$가 $\mathcal N$-행동 집합이라고 가정해봅시다. 즉, 내가 필승 전략을 가지고 있어서 내가 $G+H$ 차례에서 어떻게 행동을 취하든 항상 이길 수 있습니다. 그럼 내가 $(\mathbf G, \mathbf H)$에서 한 행동을 하고 나면 그 다음 상대방의 행동 집합은 $\mathcal P$-행동 집합이죠. 무조건 질 수 밖에 없으니까! 그럼 $\mathbf A$와 $(\mathbf G, \mathbf H)$를 같이 하는 경우엔 필승 전략을 이렇게 세울 수 있습니다.

  • 먼저 $(\mathbf G, \mathbf H)$를 골라서 행동을 취합니다. 그 다음부턴 상대방의 행동에 따라 달라집니다.
  • 상대방이 $(\mathbf G, \mathbf H)$를 골라서 행동을 취할 경우: 어차피 내가 필승 전략을 가지고 있으니 구사해서 막아버립니다.
  • 상대방이 $\mathbf A$를 골라서 행동을 취할 경우: 위와는 반대로 상대방이 $\mathbf A$를 골랐기 때문에 이번엔 내 쪽이 $\mathbf A$에 대한 필승 전략을 가지고 있습니다. 역시 막아버립니다.

어떻게 하든 내가 이깁니다. 따라서 $A+G+H$도 $\mathcal N$-행동 집합에 속합니다. ■

보조 정리 2

$A\approx B$와 $A+B$가 $\mathcal P$-행동 집합에 속하는 것은 동치이다.

증명) 만약 $A\approx B$이면 정의에 의해 $A+A$와 $A+B$은 둘 다 $\mathcal N$-행동 집합이거나 $\mathcal P$-행동 집합입니다. 그런데 $A+A$는 똑같은 게임 $\mathbf A$를 두 개 갖다놓고 한다는 것이고, 여기서 내가 어떻게 두든 상대방은 반대쪽 게임판을 고르고 나랑 똑같은 행동을 해버리면 먼저 행동 집합이 소진되는 쪽은 내 쪽입니다. 결국 $A+A$는 $\mathcal P$-행동 집합이고, $A+B$ 또한 $\mathcal P$-행동 집합입니다.

만약 $A+B$가 $\mathcal P$-행동 집합이면 보조 정리 1에 의해 $A\approx A+A+B$입니다. 그리고 $A+A$도 $\mathcal P$-행동 집합이기 때문에 역시 보조 정리 1에 의해 $B\approx A+A+B$입니다. 따라서 $A\approx B$입니다. ■

스프라그-그런디 정리

스프라그-그런디 정리(Sprague-Grundy theorem)는 모든 행동 집합은 대응되는 어떤 그런디 수와 동등하다는 정리입니다. 주요 증명 아이디어는 구조적 귀납법으로, 행동 집합 $G$의 원소 각각이 자신과 동등한 그런디 수를 가진다면 $G$ 또한 어떤 그런디 수와 동등함을 증명하는 방식입니다.

먼저 행동 집합 $G=\{G_1, G_2, \cdots, G_k\}$의 각 원소 $G_i$와 동등한 그런디 수를 $*n_i$라 합시다. 이때 행동 집합 $G’=\{*n_1, *n_2, \cdots, *n_k\}$는 $G$와 동등합니다.

증명) $k=0$이면 $G$와 $G’$ 둘 다 공집합이니 자명합니다. 아니라면 행동 집합 $G+G’$을 생각해봅시다. 내가 $\mathbf G$를 골라서 행동 $G_i$를 취하면 상대방은 $\mathbf G’$을 골라서 $*n_i$를 취합니다. 내가 $\mathbf G’$을 골라서 그 중에 행동 $*n_i$를 취하면 상대방은 $\mathbf G$를 골라서 $G_i$를 취합니다. 어느 경우건 두 차례 이후 행동 집합은 $G_i+*n_i$가 되는데, $G_i\approx *n_i$라고 했으니 보조 정리 2에 의해 $G_i+*n_i$는 $\mathcal P$-행동 집합에 속합니다. 따라서 내가 $(\mathbf G, \mathbf G’)$에서 어떻게 두든 상대방이 저렇게 둬버리면 나는 $\mathcal P$-행동 집합에 빠져버려 패배하므로 $G+G’$도 $\mathcal P$-행동 집합이고, 보조 정리 2에 의해 $G\approx G’$입니다. ■

그 다음 집합 $\{n_1, n_2, \cdots, n_k\}$에 속하지 않는 가장 작은 음이 아닌 정수 $m$을 찾습니다. 그러면 $G’+*m$은 $\mathcal P$-행동 집합에 속합니다.

증명) 만약 $G’$과 $*m$이 공집합이면 $G’+*m$도 공집합이므로 자명하게 $\mathcal P$-행동 집합입니다. 아니라면 나한테 두 가지 경우의 수가 있습니다. 내가 $*m=\{*0, *1, *\cdots, *(m-1)\}$에서 $*m’$을 취하면($m'<m$) $m’$과 같은 $n_i$가 하나 존재하므로($m$의 정의에 의해) 상대방은 $G’$에서 $*n_i$를 골라 그 다음 내 차례에 행동 집합을 $*m’+*n_i=*m’+*m’$으로 만들어서 날 패배시킬 수 있습니다($G+G$는 무조건 $\mathcal P$-행동 집합이라고 증명했습니다). 한편 내가 $G’$에서 $*n_i$를 취했다고 해봅시다. $n_i < m$이면 상대방은 $*m$에서 $*n_i$를 골라 내 차례에 행동 집합을 $*n_i+*n_i$로 만들어버릴 거고, $n_i > m$이면 상대방은 $*n_i$에서 $*m$을 골라서 내 차례에 행동 집합을 $*m+*m$으로 만들어버릴 겁니다. 결국 나는 무조건 지고, $G’+*m$은 $\mathcal P$-행동 집합입니다. ■

고로 보조 정리 2에 의해 $G’\approx*m$이고 $G\approx G’$이므로 $G\approx*m$입니다. $G$와 동등한 그런디 수 $*m$을 찾았습니다!

이제 $m$이 0인 경우를 생각해봅시다. $G\approx *0$이면 동등의 정의에 의해 $G+\{\}$와 $*0+\{\}=\{\}+\{\}$는 둘 다 $\mathcal N$-행동 집합이거나 $\mathcal P$-행동 집합인데 $\{\}+\{\}$는 당연히 $\mathcal P$-행동 집합이기 때문에 $G+\{\}$도 $\mathcal P$-행동 집합입니다. 그런데 $\{\}$는 이미 끝난 게임이고, 이걸 다른 게임에 더한다고 게임 양상이 달라지진 않죠. 결국 원래 게임만 고를 수 밖에 없으니까요. 따라서 $G$도 $\mathcal P$-행동 집합입니다.

반면에 $G$가 $*0$이 아닌 다른 그런디 수와 동등하면 다음 차례에 $*0$으로 만들 수 있으므로 $\mathcal N$-행동 집합입니다. 즉, 초기 상태에서 그런디 수를 계산해서 $*0$이면 후공이 승리, 아니면 선공이 승리합니다.

노멀 게임이 아니라면?

노멀 게임이 아니란 건 더 이상 행동할 수 없는 사람이 이긴다는 뜻이죠. 즉, 공집합이 $\mathcal N$-행동 집합에 속합니다. 이 때 만약 내 차례에 할 수 있는 행동들이 다 행동 집합을 공집합으로 만드는 행동들이면 난 무조건 질 거고, 그럼 그런디 수는 $*0$이죠. 따라서 공집합의 그런디 수를 $*1$로 정하고 똑같이 그런디 수를 계산하면 됩니다.

여러 게임의 합의 그런디 수

위에서 언급했듯이 행동 집합에 공집합을 더해도 그런디 수는 그대로입니다. 다시 말해 행동 집합 $G$가 그런디 수 $*n$과 동등하다면 $G+\{\}=G+*0$도 $*n$과 동등합니다. 따라서

\[ *n + *0 \approx *n \]

0 말고 1이면 어떨까요?

\[ \begin{align}
*n+*1 &= \{*0 + *1, *1+*1, \cdots, *(n-1)+*1\}\cup\{*n+*0\} \\
&\approx \{*0 + *1, *1+*1, \cdots, *(n-1)+*1\}\cup\{*n\}
\end{align} \]

규칙을 잘 모르겠군요. 직접 $n$에 0부터 열심히 넣어봅시다.

\[ \begin{align}
*0+*1 &\approx *1 \\
*1+*1 &= \{*0+*1\}\cup\{*1+*0\} \approx \{*1\} \approx *0 \\
*2+*1 &= \{*0+*1,*1+*1\}\cup\{*2+*0\} \approx \{*1, *0, *2\} \approx *3 \\
*3+*1 &= \{*0+*1,*1+*1,*2+*1\}\cup\{*3+*0\} \approx \{*1,*0,*3\} \approx *2
\end{align} \]

왠지 $n$이 짝수이면 $*n+*1\approx*(n+1)$, 홀수이면 $*n+*1\approx*(n-1)$일 것 같습니다.

증명) $n$이 0과 1일 때 성립합니다. $n<2k$일 때 성립한다고 가정하면($k$는 양의 정수) $n=2k$일 때

\[ \begin{align}
*(2k)+*1 &= \{*0+*1, *1+*1, \cdots, *(2k-1)+*1\}\cup\{*(2k)+*0\} \\
&\approx \{*1,*0,*3,*2, \cdots, *(2k-1), *(2k-2)\}\cup\{*(2k)\} \\
&= \{*0,*1,*2,\cdots,*(2k)\} \\
&\approx *(2k+1)
\end{align} \]

$n=2k+1$도 똑같이 증명합니다. ■

한편 $*n+*2$의 결과는 아래와 같습니다(더럽긴 한데 계산해봅시다).

\[ \begin{align}
*0+*2 &\approx *2 \\
*1+*2 &\approx *3 \\
*2+*2 &\approx *0 \\
*3+*2 &\approx *1 \\
*4+*2 &\approx *6
\end{align} \]

규칙이 잘 안 보이지만 자세히 보면 $n$을 이진법으로 나타냈을 때 2의 자리가 0이면 1로 만들고 1이면 0으로 만든 게 답이 됩니다. $*n+*1$의 결과와 합쳐보면 $*n+*m\approx*(n \oplus m)$ 아닐까 추정할 수 있습니다($\oplus$는 배타적 논리합, 그러니까 xor 연산입니다).

증명) 또 귀납법을 씁니다. $*n+*0\approx *n=*(n\oplus0)$임은 위에서 보였습니다. 귀납 가정으로 $m\le l$일 때 모든 $n$에 대해 $*n+*m\approx*(n\oplus m)$이라고 가정하고 $m=l+1$일 때에도 모든 $n$에 대해 $*n+*m\approx*(n\oplus m)$임을 보여주면 됩니다. 근데 이건 어떻게 보이냐고요? 한 단계 더 귀납법 써야죠….

$*0+*(l+1)\approx*(l+1)=*[0\oplus(l+1)]$입니다. 그 다음 $n\le k$일 때 $*n+*(l+1)\approx*[n\oplus(l+1)]$이라고 가정합시다. 이때 $n=k+1$일 때 $S=*n+*(l+1)=*(k+1)+*(l+1)$이 $*[(k+1)\oplus(l+1)]$와 동등함을 보이면 되고, 이건 $S$가 $*0,*1,*2,\cdots,*[[(k+1)\oplus(l+1)]-1]$은 포함하지만 $*[(k+1)\oplus(l+1)]$는 포함하지 않음을 증명하면 됩니다. 귀찮은 관계로(?) $(k+1)\oplus(l+1)=t$라 쓰겠습니다.

  • $0\le s<t$인 정수 $s$에 대해 $*s\in S$ 증명) $u=s\oplus t$가 이진법으로 나타냈을 때 $d$자리 수라고 합시다. 즉 $2^{d-1}\le u$ $<2^d$이고 $u$의 $2^{d-1}$의 자리수는 1입니다. 가정에서 $s<t$라고 했으므로 $s$의 $2^{d-1}$의 자리수는 0이어야 하고 $t$의 해당 자리수는 1이어야 합니다. 다시 $t=(k+1)\oplus(l+1)$이므로 $k+1$과 $l+1$ 둘 중 하나는 $2^{d-1}$의 자리수가 1이고 나머지 하나는 0입니다. 일반성을 잃지 않고 $k+1$의 해당 자리수가 1이라고 해보죠. 그러면 $u\oplus(k+1)$은 $k+1$보다 작습니다. $k+1$은 이진법으로 $d$자리 이상의 수인데 $u$와 배타적 논리합을 계산하면 $k+1$의 $d$번째 자리에 있는 1을 $u$의 $d$번째 자리 1로 지워버리니까 더 작아기 때문이죠. 따라서 그런디 수의 정의에 따라 $*[u\oplus(k+1)]\in$ $*(k+1)$이고, \[*[u\oplus(k+1)]+*(l+1)\approx*[u\oplus(k+1)\oplus(l+1)]\in*(k+1)+*(l+1)=S\]입니다. 그런데 $u\oplus(k+1)\oplus(l+1) = s\oplus t\oplus t=s$이므로 증명 완료입니다.
  • $*t\notin S$ 증명) $*t\in S$라 가정합시다. 즉 $*(k+1)+*(l+1)$에서 행동 하나를 골라서 했더니 행동 집합이 $*t$가 되었습니다. 일반성을 잃지 않고 이 행동이 $*(k+1)$ 쪽에서 고른 거라고 해보죠. 그러면 $*t$는 \[\{*0+*(l+1),*1+(l+1),\cdots,*k+*(l+1)\}\approx\{*[0\oplus(l+1)],\cdots,*[k\oplus(l+1)]\}\]의 원소 중 하나입니다. 하지만 $*t=*[(k+1)\oplus(l+1)]$이므로 모순입니다.

위 재미없고 긴 증명 과정에 의해 $*n+*m\approx*(n\oplus m)$입니다. ■

이를 확장하면 $*n_1+*n_2+\cdots+*n_k\approx*(n_1\oplus n_2\oplus\cdots\oplus n_k)$가 됩니다. 즉, 여러 게임의 합은 각 게임의 그런디 수를 모두 xor한 값이 0이면 후공이 승리, 0이 아니면 선공이 승리합니다.

더 많은 예제들

예제 다시 보기: 돌 가져가기 게임의 그런디 수

돌이 4개일 때 행동 집합은 $\{*1, *2, *3\}\approx*0$입니다. 5개일 때 행동 집합은

\[ \{*2, *3, \{*1, *2, *3\}\}\approx\{*0, *2, *3\}\approx*1 \]

이고, 돌이 6개일 땐 돌이 5개($*1$), 4개($*0$), 3개($*3$)인 경우로 행동할 수 있으므로 행동 집합이 아래와 같습니다.

\[ \{*1, *0, *3\}\approx*2 \]

이렇게 재귀적으로 계산해나가면 아래와 같은 결과를 얻습니다.

돌 개수 그런디 수
0 $*0$
1 $*1$
2 $*2$
3 $*3$
4 $*0$
5 $*1$
6 $*2$
7 $*3$
8 $*0$

따라서 돌이 $n$개일 때 그런디 수는 $n$을 4로 나눈 나머지입니다. 좀 더 일반적으로 돌이 $n$개이고 한 번에 1개부터 $k$개까지 가져갈 수 있다면 $n$이 $k+1$의 배수가 아니면 선공, 배수이면 후공이 이깁니다.

돌을 1개, 3개, 또는 4개 가져갈 수 있는 돌 가져가기 게임

icpc.me/9660

직접 그런디 수를 돌 개수가 0일 때부터 계산해보면 주기 7로 0, 1, 0, 1, 2, 3, 2가 반복됩니다(귀찮으니 앞으로 $*$은 생략합니다). 따라서 돌 개수를 7로 나눈 나머지가 0이나 2면 후공이 승리, 아니면 선공이 승리합니다.

돌을 1개, 3개, 또는 4개 가져갈 수 있지만 마지막 돌을 가져가면 지는 게임

icpc.me/9658

돌 개수가 0개일 때 그런디 수가 1임에 주의합시다. 계산해보면 7을 주기로 1, 0, 1, 0, 2, 3, 2가 반복됩니다.

돌을 4의 거듭제곱(1, 4, 16, 64, …)개 가져갈 수 있는 돌 가져가기 게임

icpc.me/9661

16개까지 계산해보면 0, 1, 0, 1, 2가 반복된다는 사실을 눈치챌 수 있습니다.

증명) 돌의 개수 $n$이 0, 1, 2, 3, 4일 때 그런디 수는 각각 0, 1, 0, 1, 2입니다. $n<5k$일 때($k$는 양의 정수) $n$을 5로 나눈 나머지가 0일 때 그런디 수가 0, 1일 때 1, 2일 때 0, 3일 때 1, 4일 때 2라고 가정합시다(귀납법).

$n=5k$이면 할 수 있는 행동은 돌 1개, 4개, …, $4^x$개를 가져가는 것입니다. 여기서 $x$는 $4^x\le5k$를 만족하는 가장 큰 정수입니다. 돌을 1개 가져가면 돌이 $5k-1$개가 되므로 귀납 가정에 따라 그런디 수는 2입니다. 돌을 4개 가져가면 돌이 $5k-4$개가 되므로 그런디 수는 1이고요. 일반적으로 돌을 $4^{2t}$개 가져가면($t$는 음이 아닌 정수) 돌이 $5k-4^{2t}$개가 되고

\[ 4^{2t}\equiv(5-1)^{2t}\equiv1\pmod5 \]

이므로 이때 그런디 수는 2입니다. 돌을 $4^{2t+1}$개 가져가면 마찬가지 방법으로 그런디 수는 1입니다. 따라서 $n=5k$일 때 어떤 행동을 하든 그런디 수는 1 또는 2가 되므로 $n=5k$의 그런디 수는 0입니다.

나머지 경우도 동일하게 증명하면 됩니다. ■

따라서 돌 개수를 5로 나눈 나머지가 0이나 2이면 후공, 아니면 선공이 승리합니다.

님 게임

님 게임(Nim game)은 여러 돌 무더기를 두고 두 사람이 차례로 하는 게임입니다. 각 차례에서 참가자는 돌 무더기 하나를 골라 돌을 하나 이상 가져갑니다. 마지막 돌을 가져가는 사람이 이깁니다.

사실 님 게임은 돌 무더기 하나에서 하는 게임을 동시에 여러 개 하는 것이기 때문에, 여러 게임을 동시에 할 때의 그런디 수로 풀 수 있습니다. 돌 무더기가 하나일 때 그런디 수는 계산해보면 그냥 돌의 개수이고, 돌 무더기가 여러 개일 때 총 그런디 수는 각 돌 무더기의 그런디 수를 모두 xor한 값, 즉 돌의 개수의 xor 총합이 됩니다.

마지막 돌을 가져가면 지는 님 게임

예이걸 마지막 돌을 가져가면 지는 돌 가져가기 게임 여러 개로 생각하면 틀립니다! 이렇게 생각하면 필승 전략이 각 돌 무더기의 마지막 돌 각각을 피하는 게 되지만 그게 아니라 최종 마지막 돌 하나만 피하면 되기 때문이죠.

이 게임에서 무조건 패배하는 상황은 딱 한 무더기만 돌이 한 개 남았고 나머지는 모두 돌이 없는 상황입니다. 여기서 약간 확장해, 각 무더기에 남은 돌 개수가 1개 이하일 때 한 개짜리 무더기가 짝수 개이면 항상 승리, 홀수 개이면 항상 패배한다는 것도 알 수 있습니다.

돌이 2개 이상인 무더기가 존재한다면 얘기가 복잡해집니다. 그런 무더기가 딱 하나면 돌 한 개짜리 무더기의 개수를 보고 그 무더기의 돌 개수를 0개 아니면 1개로 적절히 만들어서 무조건 이길 수 있습니다. 두 개면? 한쪽을 0개나 1개로 만들었다간 패배하니까 무조건 2개 이상으로 만들어야 합니다. 그러므로 상대가 어쩔 수 없이 한쪽을 1개 이하로 만들 수 밖에 없도록 해야 하고, 그러기 위해선 내가 양쪽 다 돌 2개로 만들어버리면 됩니다. 결국 돌이 2개 이상인 무더기 2개에서 돌 두 개씩 빼고 노멀 님 게임을 하는 거랑 똑같습니다!

돌 2개 이상인 무더기가 3개라면