게임의 룰을 아십니까?
수학에서 말하는 게임이란,
- 여러 명의 참가자가 있고,
- 게임판이 가질 수 있는 상태들의 집합이 있고,
- 각 상태에서 각 참가자마다 취할 수 있는 행동들의 집합이 존재하여 어떤 행동을 하면 상태가 바뀌는 것
으로 정의합니다. 저 행동 집합이 바로 게임의 규칙을 이루죠. 가장 예로 많이 드는 게임이 바로 체스로, 두 명이 참가하고 체스판의 상태 집합(어떤 말이 어디 놓여있나)이 있으며 각 상태에서 해당 순서의 참가자가 취할 수 있는 행동 집합(어떤 말을 어디로 옮긴다)이 존재하여 이 행동을 하면 체스판의 상태가 바뀝니다. 우리가 흔히 생각하는 보드 게임, 비디오 게임 뿐만 아니라 기업이나 생물 사이의 생존 경쟁 또한 상태 집합과 행동 집합을 적절히 정의하여 게임으로 다룰 수 있습니다.
게임의 분류
- 순차적 게임(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$을 다음과 같이 정의합시다.
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개부턴 그런디 수의 집합이나 집합족이 되어 아주 복잡해집니다. 다행히 이런 경우도 대응되는 그런디 수 하나로 바꿀 수 있습니다. 이는 밑에서 다루겠습니다.
동시에 두 게임을 같이 한다면?
두 게임 $\A$와 $\B$의 합 $(\A,\B)$를 다음과 같이 정의합시다. 각 차례마다 참가자는 두 게임 중 하나를 골라 고른 게임의 행동 집합에서 한 행동을 취합니다. 이때 다른 게임은 절대 건드리지 않습니다. 동시에 두 게임을 같이 하는 셈이죠.
예를 들어 위의 돌 가져가기 게임을 돌 5개짜리 돌무더기와 돌 2개짜리 돌무더기에서 동시에 게임을 한다고 합시다. 먼저 돌이 5개인 돌 가져가기 게임에서 선공의 행동 집합은
돌이 2개일 때 선공의 행동 집합은
게임 $\A$의 행동 집합이 $A$이고 게임 $\B$의 행동 집합이 $B$일 때 합쳐진 게임 $(\A,\B)$의 행동 집합을 $A+B$라 씁시다. $(\A,\B)$에서 할 수 있는 행동은 $\A$에서 행동 하나($a$라고 합시다)를 하거나 $\B$에서 행동 하나($b$라고 합시다)를 하거나인데, 전자는 행동 집합이 $a+B$가 되고 후자는 행동 집합이 $A+b$가 되므로 $A+B$를 아래와 같이 재귀적으로 표현할 수 있습니다.
위 예시에서는
행동 집합의 덧셈은 교환법칙과 결합법칙을 만족합니다. 교환법칙은 정의에 의해 자명하고, 결합법칙은 $(\A,\B)$와 $\C$를 더하든 $\A$와 $(\B,\C)$를 더하든 결국 각 차례마다 $\A$, $\B$, $\C$ 셋 중 한 게임을 골라서 행동을 취하는 것이 된다는 것으로 증명할 수 있습니다. 결합법칙이 성립하므로 세 게임의 합을 간단하게 $(\A,\B,\C)$로 씁시다. 그리고 이때 행동 집합은 $A+B+C$로 쓸 수 있겠습니다.
$\P$-행동 집합과 $\N$-행동 집합
항상 유한한 차례 안에 끝나는 2인용 순차적, 완전 정보, 공정, 노멀 게임의 모든 행동 집합은 두 가지로 나눌 수 있습니다. 첫째는 이번 차례의 참가자가 무조건 이기는 차례의 행동 집합들로, $\N$-행동 집합($\N$-position)이라고 합니다. 다른 하나는 이전 차례의 참가자가 무조건 이기는 차례의 행동 집합들로, $\P$-행동 집합($\P$-position)이라고 합니다. 노멀 게임의 경우 내 차례에 행동 집합이 $*0$이 되면 패배하기 때문에 $*0$은 $\P$-행동 집합에 속하고, 내 차례에 $*1$이 되면 다음 상대방 차례엔 $*0$이 되어 내가 이길 수 밖에 없기 때문에 $*1$은 $\N$-행동 집합에 속합니다.
만약 현재 행동 집합에 $\P$-행동 집합에 속하는 행동이 존재한다면 현재 행동 집합은 $\N$-행동 집합에 속하고, 모든 행동이 $\N$-행동 집합에 속한다면 현재 행동 집합은 $\P$-행동 집합에 속하게 됩니다.
행동 집합의 동등
두 행동 집합 $A$와 $B$가 다음을 만족하면 동등하다고 하고, $A\approx B$로 나타냅니다.
한 마디로 게임 $\A$와 $\B$가 있는데 어떤 게임 $\G$를 들고 오더라도 $(\A,\G)$의 전략과 $(\B,\G)$의 전략이 완전히 똑같으면 두 게임을 같은 것으로 보자는 이야기죠. 또 정의에 따라 $A\approx B$이고 $B\approx C$이면 $A\approx C$임이 증명됩니다.
행동 집합의 동등에 관한 정리 두 가지를 짚고 넘어갑시다.
행동 집합 $A$가 $\P$-행동 집합에 속하면 임의의 행동 집합 $G$에 대해 $G\approx A+G$이다.
정의에 의해 임의의 행동 집합 $H$에 대해 $G+H$와 $A+G+H$가 둘 다 $\N$-행동 집합에 속하거나 $\P$-행동 집합임을 증명하면 됩니다.
$G+H$가 $\P$-행동 집합이라고 가정해봅시다. 즉, 내 차례에 행동 집합이 $G+H$인데 상대방이 필승 전략을 가지고 있어서 내가 어떻게 행동을 취하든 절대 이길 수 없습니다. 그런데 $A$도 $\P$-행동 집합이므로 상대방은 이쪽 게임에서도 필승 전략을 가지고 있습니다. 그럼 상대방 입장에서는 다음과 같이 게임 $\A$와 $(\G,\H)$의 합에서 필승 전략을 세울 수 있습니다.
- 내가 $\A$를 골라서 행동을 취할 경우: $\A$에서 필승 전략을 구사합니다.
- 내가 $(\G,\H)$를 골라서 행동을 취할 경우: 역시 이쪽에서도 필승 전략을 구사합니다.
어떻게 하든 질 수밖에 없죠. 따라서 $A+G+H$도 $\P$-행동 집합에 속합니다.
이번엔 $G+H$가 $\N$-행동 집합이라고 가정해봅시다. 즉, 내가 필승 전략을 가지고 있어서 내가 $G+H$ 차례에서 어떻게 행동을 취하든 항상 이길 수 있습니다. 그럼 내가 $(\G,\H)$에서 한 행동을 하고 나면 그 다음 상대방의 행동 집합은 $\P$-행동 집합이죠. 무조건 질 수 밖에 없으니까! 그럼 $A$와 $(\G,\H)$를 같이 하는 경우엔 필승 전략을 이렇게 세울 수 있습니다.
- 먼저 $(\G,\H)$를 골라서 행동을 취합니다. 그 다음부턴 상대방의 행동에 따라 달라집니다.
- 상대방이 $(\G,\H)$를 골라서 행동을 취할 경우, 어차피 내가 필승 전략을 가지고 있으니 구사합시다.
- 상대방이 $\A$를 골라서 행동을 취할 경우, 위와는 반대로 상대방이 $\A$를 골랐기 때문에 이번엔 내 쪽이 $\A$에 대한 필승 전략을 가지고 있습니다. 역시 구사합시다.
결국 어떻게 하든 내가 이기니까, $A+G+H$도 $\N$-행동 집합에 속합니다.
$A\approx B$인 것과 $A+B$가 $\P$-행동 집합에 속하는 것은 동치이다.
만약 $A\approx B$이면 정의에 의해 $A+A$와 $A+B$는 둘 다 $\N$-행동 집합이거나 $\P$-행동 집합입니다. 그런데 $A+A$는 똑같은 게임 $A$를 두 개 갖다놓고 한다는 것이고, 여기서 내가 어떻게 두든 상대방은 반대쪽 게임판을 고르고 나랑 똑같은 행동을 해버리면 먼저 행동 집합이 소진되는 쪽은 내 쪽입니다. 결국 $A+A$는 $\P$-행동 집합이고, $A+B$ 또한 $\P$-행동 집합입니다.
역으로 $A+B$가 $\P$-행동 집합이면 정리 1에 의해 $A\approx A+A+B$입니다. 그리고 $A+A$도 $\P$-행동 집합이기 때문에 역시 정리 1에 의해 $B\approx A+A+B$입니다. 따라서 $A\approx B$입니다.
스프라그-그런디 정리
스프라그-그런디 정리는 모든 행동 집합이 대응되는 어떤 그런디 수와 동등하다는 정리입니다. 주요 증명 아이디어는 구조적 귀납법으로, 행동 집합 $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'$을 생각해봅시다. 내가 $\G$를 골라서 행동 $G_i$를 취하면 상대방은 $\G'$을 골라서 $*n_i$를 취하고, 내가 $\G'$을 골라서 그 중에 행동 $*n_i$를 취하면 상대방은 $\G$를 골라서 $G_i$를 취한다고 해봅시다. 어느 경우건 두 차례 이후 행동 집합은 $G_i+*n_i$가 되는데, $G_i\approx*n_i$라고 했으니 정리 2에 의해 $G_i+*n_i$는 $\P$-행동 집합에 속합니다. 따라서 내가 $(\G,\G')$에서 어떻게 두든 상대방이 저렇게 둬버리면 나는 $\P$-행동 집합에 빠져버려 패배하므로 $G+G'$도 $\P$-행동 집합이고, 정리 2에 의해 $G\approx G'$입니다.
행동 집합 $G'=\{*n_1, *n_2, \cdots, *n_k\}$에 대해 집합 $\{n_1, n_2, \cdots, n_k\}$에 속하지 않는 가장 작은 음이 아닌 정수를 $m$이라 하면 $G'+*m$은 $\P$-행동 집합에 속한다.
만약 $G'$과 $*m$이 공집합이면 $G'+*m$도 공집합이므로 자명하게 $\P$-행동 집합입니다. 아니라면 나한테 두 가지 경우의 수가 있습니다. 내가 $*m=\{*0,*1,\cdots,*(m-1)\}$에서 $*m'$을 취하면($m'<m$) $m'$과 같은 $n_i$가 하나 존재하므로($m$의 정의에 의해) 상대방은 $G'$에서 $*n_i$를 골라 그 다음 내 차례에 행동 집합을 $*m'+*n_i=*m'+*m'$으로 만들어서 날 패배시킬 수 있습니다(자기 자신과의 합은 무조건 $\P$-행동 집합이라고 증명했습니다). 한편 내가 $G'$에서 $*n_i$를 취했다고 해봅시다. $n_i<m$이면 상대방은 $*m$에서 $*n_i$를 골라 내 차례에 행동 집합을 $*n_i+*n_i$로 만들어버릴 거고, $n_i>m$이면 상대방은 $*n_i$에서 $*m$을 골라서 내 차례에 행동 집합을 $*m+*m$으로 만들어버릴 겁니다. 결국 나는 무조건 지고, $G'+*m$은 $\P$-행동 집합입니다.
정리 2와 4에 의해 $G’\approx*m$이고 정리 3에 의해 $G\approx G’$이므로 $G\approx*m$입니다. 따라서 $G$와 동등한 그런디 수 $*m$을 찾았습니다!
이제 $m$이 0인 경우를 생각해봅시다. $G\approx*0$이면 동등의 정의에 의해 $G+{}$와 $*0+{}={}+{}$는 둘 다 $\N$-행동 집합이거나 $\P$-행동 집합이고 ${}+{}$는 당연히 $\P$-행동 집합이기 때문에 $G+{}$도 $\P$-행동 집합입니다. 그런데 ${}$는 이미 끝난 게임이고, 이걸 다른 게임에 더한다고 게임 양상이 달라지진 않죠. 결국 원래 게임만 고를 수 밖에 없으니까요. 따라서 $G$도 $\P$-행동 집합입니다.
반면에 $G$가 $*0$이 아닌 다른 그런디 수와 동등하면 다음 차례에 $*0$으로 만들 수 있으므로 $\N$-행동 집합입니다. 즉, 현재 상태에서 그런디 수를 계산해서 $*0$이면 후공이 승리, 아니면 선공이 승리합니다.
노멀 게임이 아니라면?
노멀 게임이 아니란 건 더 이상 행동할 수 없는 사람이 이긴다는 뜻이죠. 즉, 공집합이 $\N$-행동 집합에 속합니다. 이 때 만약 내 차례에 할 수 있는 행동들이 다 행동 집합을 공집합으로 만드는 행동들이면 난 무조건 질 거고, 그럼 그런디 수는 $*0$이죠. 따라서 공집합의 그런디 수를 $*1$로 정하고 똑같이 그런디 수를 계산하면 됩니다.
여러 게임의 합의 그런디 수
위에서 언급했듯이 행동 집합에 공집합을 더해도 그런디 수는 그대로입니다. 다시 말해 행동 집합 $G$가 그런디 수 $*n$과 동등하다면 $G+{}=G+*0$도 $*n$과 동등합니다. 따라서
0말고 다른 수는 어떨까요?
음이 아닌 정수 $n$과 $m$에 대하여 다음이 성립한다.
여기서 $\oplus$는 배타적 논리합(XOR)을 뜻한다.
$m=0$일 때 $*n+*0 \approx *n = *(n+0)$으로 성립함은 위에서 보였습니다. 이제 $m\le l$일 때 모든 $n$에 대해 $*n+*m \approx *(n\oplus m)$이라고 가정하고 $m=l+1$일 때에도 모든 $n$에 대해 $*n+*m \approx *(n\oplus m)$임을 보여주면 됩니다. 이건 다시 또 귀납법을 씁니다.
$*0+*(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$, …, $*[[(k+1)\oplus(l+1)]-1]$은 포함하지만 $*[(k+1)\oplus(l+1)]$은 포함하지 않음을 증명하면 됩니다. 이하 $t=(k+1)\oplus(l+1)$로 쓰겠습니다.
- $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)$이고, \begin{equation*} *[u\oplus(k+1)]+*(l+1)\approx*[u\oplus(k+1)\oplus(l+1)]\in*(k+1)+*(l+1)=S \end{equation*} 입니다. 그런데 $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$는 \begin{equation*} \{*0+*(l+1),*1+(l+1),\cdots,*k+*(l+1)\}\approx\{*[0\oplus(l+1)],\cdots,*[k\oplus(l+1)]\} \end{equation*} 의 원소 중 하나입니다. 하지만 $*t=*[(k+1)\oplus(l+1)]$이므로 모순입니다.
이를 확장하면
가 됩니다. 즉, 여러 게임의 합은 각 게임의 그런디 수를 모두 배타적 논리합한 값이 $*0$이면 후공이 승리, 아니면 선공이 승리합니다.
더 많은 예제들
예제 다시 보기: 돌 가져가기 게임의 그런디 수
돌이 4개일 때 행동 집합은 ${*1,*2,*3}\approx*0$입니다. 5개일 땐
이고, 돌이 6개일 땐 돌이 5개($*1$), 4개($*0$), 3개($*3$)인 경우로 갈 수 있으므로 행동 집합이 다음과 같습니다.
이렇게 재귀적으로 계산해나가면 아래와 같은 결과를 얻습니다.
| 남은 돌의 개수 | 그런디 수 |
|---|---|
| 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개 가져갈 수 있는 돌 가져가기 게임
직접 그런디 수를 돌 개수가 0개일 때부터 계산해보면 주기 7로 0, 1, 0, 1, 2, 3, 2가 반복됩니다. 따라서 돌 개수를 7로 나눈 나머지가 0이나 2면 후공이, 아니면 선공이 승리합니다.
돌을 1개, 3개, 또는 4개 가져갈 수 있지만 마지막 돌을 가져가면 지는 게임
돌 개수가 0개일 때 그런디 수가 1임에 주의합시다. 계산해보면 7을 주기로 1, 0, 1, 0, 2, 3, 2가 반복됩니다.
돌을 4의 거듭제곱(1, 4, 16, …)개 가져갈 수 있는 돌 가져가기 게임
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\le 5k$를 만족하는 가장 큰 정수입니다. 돌을 1개 가져가면 돌이 $5k-1$개가 되므로 가정에 따라 그런디 수는 $*2$입니다. 돌을 4개 가져가면 돌이 $5k-4$개가 되므로 그런디 수는 $*1$이고요. 일반적으로 돌을 4$2t$개 가져가면($t$는 음이 아닌 정수) 돌이 $5k-4^{2t}$개가 되고 \begin{equation*} 4^{2t}\equiv(5-1)^{2t}\equiv1\pmod5 \end{equation*} 이므로 이때 그런디 수는 $*2$입니다. 돌을 $4^{2t+1}$개 가져가면 마찬가지 방법으로 그런디 수는 1입니다. 따라서 $n=5k$일 때 행동 집함은 $\{*1,*2\}$이므로 그런디 수는 $*0$입니다.
나머지 경우도 동일하게 증명할 수 있습니다.
님 게임
님 게임(Nim game)은 여러 돌 무더기를 두고 두 사람이 차례로 하는 게임입니다. 각 차례에서 참가자는 돌 무더기 하나를 골라 돌을 하나 이상 가져갑니다. 마지막 돌을 가져가는 사람이 이깁니다.
사실 님 게임은 돌 무더기 하나에서 하는 게임을 동시에 여러 개 하는 것이기 때문에, 여러 게임을 동시에 할 때의 그런디 수로 풀 수 있습니다. 돌 무더기가 하나일 때 그런디 수는 계산해보면 그냥 돌의 개수이고, 돌 무더기가 여러 개일 때 총 그런디 수는 각 돌 무더기의 그런디 수를 모두 xor한 값, 즉 돌의 개수의 xor 총합이 됩니다.