필승 전략 게임

개요

필승 전략 게임이란, 이름 그대로 어느 한 쪽이 반드시 이길 수 있는 전략을 가진 게임을 말한다. 중요한 것은, 운이나 실력이 아닌 철저한 수학적 계산만을 사용하여 이기는 게임만을 다룬다. 이 때문에 확률 놀음인 포커나 실력이 중요한 바둑은 이 범위에서 제외된다. 또한, 무수히 많은 경우의 수를 사용한 승리 전략이나 승패가 결졍되지 않는 게임 역시 제외된다. 전자의 예로는 오목이 있으며, 후자의 예는 틱택토가 있다. 마지막으로, 여러명이 하는 게임이 아닌 일대일 대결 게임만을 다룬다.

어떤 게임의 필승 전략을 찾는 것은 소위 말하는 창의력 수학의 단골 소재. 수학 경시대회에 나오는 경우도 간혹 있다. 대부분의 경우는 방법을 찾는 것만으로 끝나게 되지만, 게임에 따라서는 그 방법이 왜 필승 전략인지 증명을 해야하는 경우도 있다. 하지만 문제 유형이 거기서 거기라 몇 가지 유형을 풀어봤다면 "아, 이거는 이 방법이구나"하고 감이 온다.

가장 많이 알려진 필승 전략 게임은 "배스킨 라빈스 31"이라는 게임일 것이다. 31을 부르면 지는 게임으로, 초등학교 수준의 필승 전략이 존재하지만 이 사실을 모르는 사람이 매우 많다. 그러나 필승 전략을 사용하여 상대방을 농락하는 짓은 착한 위키러라면 하지 말자. 더욱이 게임에 돈을 건다면... 사기죄

목록

NIM 게임

가장 대표적인 유형으로, 개요에서 예시로 들은 배스킨 라빈스 31도 님 게임의 일종이다. 이름의 NIM의 어원은 알려지지 않았으며, 훔치다라는 뜻의 영어 동사 nim에서 왔다는 설, 가지고 가다라는 뜻의 독일어 nimm에서 왔다는 설, NIM을 뒤집으면 WIN이기 때문에 NIM이라는 설 등이 있다. 이름 뿐만 아니라 게임 자체의 기원도 명확하지 않은데, 고대 중국의 돌 줍기 게임에서 왔다는 설, 유럽의 선술집에서 하던 성냥개비 게임에서 왔다는 설 등이 있다. 어느 쪽이든 확실한 증거는 없다. 그럼 도대체 뭐야 이 게임

기본적인 룰은 여러개의 돌 더미 중 하나를 골라 그 더미 안의 돌을 가져가는 것이며, 가장 마지막 돌을 가져가는 사람이 지는 게임이다. 규칙에 따라서는 마지막 돌을 가져가는 사람이 이기게 만들 수도 있으며, 수학적인 필승 전략과 그 원리는 동일하다. 아래 내용은 특별한 말이 없는한 마지막 돌을 가져가는 사람이 패배하는 규칙을 따른다.

한 더미

배스킨 라빈스 31이 바로 이 유형. 돌 더미가 하나인 경우, 가져가는 돌의 개수에 제한을 두지 않으면 먼저하는 사람이 반드시 이기게 되어 게임의 의미가 없다. 그래서 한 번에 가져갈 수 있는 돌의 수에 제한을 두게 된다. 아래 게임의 필승 전략을 스스로 한번 생각해 보자.

두 사람이 1부터 번갈아 숫자를 부른다. 한 번에 세 숫자까지 부를 수 있으며, 31을 부르면 진다. 당신이 이기기 위해서 먼저 숫자를 불러야 할까 나중에 불러야 할까? 필승 전략은?

힌트 30을 부르면 반드시 이길 수 있습니다. 30을 부르려면 어떤 수를 불러야 할까요?

풀이 30을 부르면 당신의 승리가 보장됩니다. 한 번에 숫자를 세 개까지 부를 수 있으므로, 30-(3+1)=26을 당신이 부르면 상대방이 몇 개의 숫자를 부르든 당신은 30을 부를 수 있습니다. 26을 부르기 위해서는 22를 부르면 되고, 22를 부르기 위해서는 18, 이런 식으로 쭉 내려가면 2를 불렀을 때 승리가 보장됩니다. 따라서 당신이 먼저 수를 2까지 부르면 승리합니다.

위 문제를 해결했으면, 일반적인 경우에 도전해 보자.

두 사람이 1부터 번갈아 숫자를 부른다. 한 번에 x개의 숫자를 부를 수 있으며, n을 부르면 진다. 필승 전략은 무엇일까?

풀이 n-1을 부르면 이긴다. n-1을 부르기 위해서는 n-1-(x+1)=n-x-2을 부르면 된다. 이 과정을 계속 반복하여 최초에 불러야 하는 수를 부르면 된다.

마지막으로, n을 부르면 이기는 경우의 필승 전략도 생각해 보자.

풀이 상대방이 n을 부를 수 없게 할려면, 자신이 n-(x+1)=n-x-1을 부르면 된다. 그러면 상대방이 몇 개의 수를 부르든, n은 x개의 안에 있으므로 당신은 항상 n을 부를 수 있다. 이 과정을 반복하면 된다.

두 더미

돌 더미가 두 개인 경우. 매 턴, 한 더미를 정해 돌을 가져가며, 가져가는 돌의 개수에는 제한이 없다. 한 더미의 돌 전체를 싹 다 빼버려도 가능하단 소리. 아래 예시를 직접 해결해 보자.

두 줄의 돌 더미가 있습니다. 첫 번째 줄에는 돌이 10개, 두 번째 줄에는 돌이 7개. 당신이 이기기 위해서는 먼저 해야할까요 나중에 해야할까요? 당신의 필승 전략은?

힌트 2, 2를 만들면 당신의 승리가 보장됩니다. 왜 일까요?

풀이 당신이 먼저 해야합니다. 첫 번째 줄에서 돌 3개를 빼 7, 7을 만듭니다. 상대방이 바보가 아닌 이상 한 줄 전체를 빼거나 한 줄에 돌을 하나만 남겨 놓을리는 없습니다. 만약 상대방이 그러면 비웃어 주세요. 그렇지 않으면, 두 줄의 돌의 개수를 똑같이 맞춰 주면 됩니다. 2, 2 상태가 된 후, 상대방이 한 줄을 지우면 당신은 남은 줄에서 돌 하나를, 상대방이 돌 하나만 빼면 당신은 다른 줄을 지우면 당신의 승리입니다.

마지막 돌을 가져가면 승리하는 경우의 전략도 한번 생각해 보자.

풀이 똑같은 방법으로, 두 줄의 돌의 개수를 같게 맞춰주면 됩니다. 2, 2가 아닌 1, 1을 만드는 것을 목표로 하면 됩니다. 상대방이 한 줄 전체를 비우면 비웃어 주세요.

똑같은 방법으로 일반화 된 전략을 세울 수 있으니 일반적인 경우의 해결법은 생략한다. 하지만 중요한 것은, 어째서 위 전략이 항상 성립하는지 모른다는 것이다. 문제의 답을 알지만 풀이는 모르는 그런 경우. 이 필승 전략에 대한 증명은 아랫 문단을 참조하자.

세 더미 이상

돌 더미가 세 개 이상인 경우. 규칙은 두 더미의 경우와 같다. 아래 쉬운 예시를 직접 해결해 보자.

세 줄의 돌 더미가 있습니다. 첫째 줄에는 1개, 둘째 줄에는 3개, 셋째 줄에는 4개. 당신이 이기기 위한 필승 전략은 무엇일까요?

당신이 천부적인 수학적 재능을 가지지 않은 한, 위 문제의 필승 전략을 찾지는 못할 것이다. 설녕 위 문제를 해결했다 해도, 일반적인 경우에 대한 필승 전략을 유추하기는 매우 힘들며, 그 필승 전략의 수학적 당위성을 보이는 것은 더더욱 어렵다. 일단 위 문제의 풀이는 다음과 같다.

풀이 셋째 줄에서 2개를 먼저 가져갑니다. 상대방이 줄 하나를 비우면 윗 문단의 두 더미 전략을 쓰면 됩니다. 상대방이 셋째 줄에서 돌 한 개를 가져갔거나 둘째 줄에서 돌 두 개를 가져갔다면 둘째 줄에서 두 개를 가져갑니다. 그럼 1, 1, 1이 되고, 당신의 승리입니다. 만약 상대방이 둘째 줄에서 돌 한 개를 가져갔다면 첫째 줄을 비우면 됩니다.

수학적 이론

윗 문단의 풀이를 보면 도대체 이게 뭔가싶은 생각이 들 것이다. 필승 전략의 원리가 2진법이기 때문에 어찌 보면 당연한 일. 아래 케이스를 살펴보자.

차례	돌의 수	2진법	비고
최초 (당신)	1, 3, 4	001, 011, 100	셋째 줄에서 두 개
상대방	1, 3, 2	001, 011, 010	둘째 줄에서 한 개
당신	1, 2, 2	001, 010, 010	첫째 줄에서 한 개
상대방	0, 2, 2	000, 010, 010	상대방의 패배

상대방의 2진법 표기를 잘 보자. 각 자릿수에 존재하는 1의 개수가 짝수 개임을 알 수 있다. 즉, 당신의 필승 전략은, 모든 돌의 개수를 2진법으로 바꿨을 때, 각 자릿수에 존재하는 1의 개수를 짝수 개로 만들어 주는 것이다. 단, 00…01(돌이 하나 밖에 없는 더미)의 개수는 홀수 개로 맞춰줘야 한다. 만약 마지막 돌을 가져가면 이기는 게임일 경우에는 상관 없다.

위 과정을 좀 더 일반화 및 추상화 시켜보자. 일반적인 연산 방법은 통하지 않기에 새로운 방법이 필요하다. 이 미지의 연산을 기호로 [math]\displaystyle{ \oplus }[/math]로 나타내고, 님 합(Nim-sum)이라 부르기로 하자. 님 합은 다음과 같이 계산한다.

1. 2진법에서만 정의 된다.
2. 두 수의 님 합을 구할 때, 각 자릿수끼리 연산을 한다.
3. 각 자릿수끼리의 연산은 XOR 연산을 따른다.

이제, 각 차례의 돌 더미의 님 합을 구해 보자.

[math]\displaystyle{ \oplus }[/math] =	001	001	001	000
	011	011	010	010
	100	010	010	010
	110	000	001	000

이제 뭔가 확실히 눈에 띄는가? 상대방의 차례에는 님 합이 항상 0이다! 이를 토대로 추상화 된 필승 전략을 세우면 다음과 같다.

1. 최초의 님 합이 0이 아니면 먼저, 0이면 나중에 시작한다.
2. 당신의 차례에 님 합을 0으로 만들어 준다.
3. 마지막 돌을 가져가는 것이 승리인지 패배인지에 따라 조금 다르다.
   • 승리일 경우: 계속 님 합을 0으로 만들어 준다.
   • 패배일 경우: 돌이 한 개 밖에 없는 더미를 홀수 개 만들어 준다. 이 외에는 님 합을 0으로 만들어 주면 된다.

여기서 문제는, 님 합이 0이 아닐 때, 항상 님 합을 0으로 만들어 주는 수가 존재하냐이다. 결론부터 말하면 그렇다이며, 증명은 아랫 문단을 참조하자.

증명

먼저 님 합은 일반적인 결합법칙과 교환법칙을 만족함을 쉽게 보일 수 있다. 또한, [math]\displaystyle{ x\oplus x=0 }[/math]이고, [math]\displaystyle{ 0\oplus x=x }[/math]이다. 이제 [math]\displaystyle{ x_1,x_2,\cdots,x_n }[/math]을 수를 두기 전의 각 더미의 돌의 개수, [math]\displaystyle{ y_1,y_2,\cdots,y_n }[/math]을 수를 둔 후의 각 더미의 돌의 개수라 하자. 또한, [math]\displaystyle{ s=x_1\oplus x_2\oplus\cdots\oplus x_n,\,t=y_1\oplus y_2\oplus\cdots\oplus y_n }[/math]라 하자. [math]\displaystyle{ k }[/math]번째 더미에서 돌을 가져가면, [math]\displaystyle{ i\neq k }[/math]일 때 [math]\displaystyle{ x_i=y_i }[/math]이고, [math]\displaystyle{ i=k }[/math]일 때는 [math]\displaystyle{ x_i\gt y_i }[/math]이다. 그러면,

[math]\displaystyle{ \begin{align*}t&=0\oplus t\\&=s\oplus s\oplus t\\&=s\oplus\left(x_1\oplus x_2\oplus\cdots\oplus x_n\right)\oplus\left(y_1\oplus y_2\oplus\cdots\oplus y_n\right)\\&=s\oplus\left(x_1\oplus y_1\right)\oplus\left(x_2\oplus y_2\right)\oplus\cdots\oplus\left(x_n\oplus y_n\right)\\&=s\oplus0\oplus\cdots\oplus\left(x_k\oplus y_k\right)\oplus0\oplus\cdots\oplus0\\&=s\oplus x_k\oplus y_k\end{align*} }[/math]
[math]\displaystyle{ \therefore t=s\oplus x_k\oplus y_k\quad\cdots\left(*\right) }[/math]

이다.

이제, 우리가 보이고자 하는 것은 아래의 두 명제이다.

[math]\displaystyle{ s=0 }[/math]이면, 어떤 수를 둬도 [math]\displaystyle{ t\neq0 }[/math]이다. [math]\displaystyle{ s\neq0 }[/math]이면, [math]\displaystyle{ t=0 }[/math]으로 만들 수 있는 수가 존재한다.

1. 먼저, [math]\displaystyle{ s=0 }[/math]이라 가정하자. 돌이 아예 없는 경우에는 승패가 명확하게 결정 된 상태이므로 의미가 없다. 따라서 수를 둘 수 있다 가정하자. 그러면 (*)에서, [math]\displaystyle{ t=0\oplus x_k\oplus y_k=x_k\oplus y_k }[/math]이고, [math]\displaystyle{ x_k\neq y_k }[/math]이므로 [math]\displaystyle{ t=x_k\oplus y_k\neq0 }[/math]이다.
2. 이제 [math]\displaystyle{ s\neq0 }[/math]이라 가정하자. [math]\displaystyle{ s }[/math]를 2진법으로 나타내었을 때, 제일 왼쪽에 존재하는 1의 자리를 [math]\displaystyle{ d }[/math]라 하자. 이제 2진법으로 나타냈을 때, [math]\displaystyle{ d }[/math]번째 자리의 수가 0이 아닌 [math]\displaystyle{ x_k }[/math]를 고른다. 만약 이런 [math]\displaystyle{ x_k }[/math]가 존재하지 않는다면, 모든 [math]\displaystyle{ x_i }[/math]의 [math]\displaystyle{ d }[/math]번째 자리는 0이고, 님 합을 구하면 [math]\displaystyle{ s }[/math]의 [math]\displaystyle{ d }[/math]번째 자리는 0이 되어 모순이다. 이제 [math]\displaystyle{ y_k=s\oplus x_k }[/math]라 하자. 즉, [math]\displaystyle{ x_k }[/math]와 [math]\displaystyle{ y_k }[/math]의 [math]\displaystyle{ d }[/math]자리 왼쪽은 전부 똑같고, [math]\displaystyle{ d }[/math]자리의 수는 1에서 0으로 줄어든 것이다. 다른 말로 하면, [math]\displaystyle{ x_k-y_k }[/math]개의 돌을 [math]\displaystyle{ k }[/math]번째 더미에서 가져간 것이다. 그러면, (*)에서, [math]\displaystyle{ t=s\oplus x_k\oplus y_k=s\oplus x_k\oplus\left(s\oplus x_k\right)=0 }[/math]이다.

변형 NIM

역사가 오래된 게임인 만큼, 여러가지 변형된 님 게임이 존재한다. 사실 엄밀하게 따지면, 돌 더미가 한 개인 경우의 님 게임은 이쪽에 속한다.

• 원형 님 (Circular Nim)

돌 더미가 한 개인 경우의 님 게임과 비슷하지만, 돌들이 원형으로 놓여있는 경우. 한 번에 가져갈 수 있는 돌의 개수에 제한이 있는 것 까지는 같지만, 가져가는 돌들은 서로 인접해야 한다. 원조 님 게임과 비슷한 이론을 쓰긴 하지만 이 게임 만의 독특한 수학 이론이 많이 필요하다.

• 슈퍼 님 (Super Nim)

돌 더미가 일차원적으로 나열되어 있는게 아니라, 이차원적으로 나열되어 있는 경우. 다르게 설명하자면, 바둑판의 격자 위에 돌들이 나열되어 있고, 매 턴 가로, 세로 중 한 줄을 골라 돌을 가져가는 것이다.

• 구성 님 (Building Nim)

돌 더미를 구성하는 것 부터 시작하는 님 게임. n개의 돌과 k개의 빈 더미가 있을 때, 번갈아가면서 돌 하나를 임의의 더미에 놓는다. 모든 돌을 사용했을 때, 님 게임이 시작된다. 얼핏보면 님 게임과 다를게 없어보이지만, 돌의 개수에 따라 님 게임이 시작되었을 때 선공인지 후공인지가 먼저 결정되어 있다. 즉, 님 합을 0으로 만드느냐 아니냐를 먼저 생각해 주어야 하는 복잡한 게임.

그룬디 게임

위키백과에서는 님 게임의 일종으로 보고 있지만, 실제로 해보면 님 게임과는 이질적이다. 기본적인 규칙은 아래와 같다.

1. 숫자 하나가 있다. 예로 10이 있다 하자.
2. 번갈아가면서 숫자를 두 개의 다른 숫자로 쪼갠다. 즉, 10→7, 3은 되지만, 10→5, 5는 안된다.
3. 자기 차례에 더이상 쪼갤 숫자가 없다면 패배. 즉, 모든 숫자가 1 또는 2면 진다.

이 게임의 필승 전략은 스프라그-그룬디 정리를 사용하여 해결할 수 있다. 영포자나 수포자를 위해 아주 정말 단순하게 설명하자면, 각 숫자에는 수학적으로 계산된 님 더미 숫자(nim heap size, 님 값)가 있는데, 수를 쪼갠 뒤의 님 합이 0이 되도록 해주면 이긴다. 참고로 위 에서는 님 합이 2진법에서만 정의된다 하였는데, 10진법에서도 특별한 오류없이 잘 정의된다. 10진법에서의 님 합의 정의는 다음과 같다.

1. 더하는 두 수(님 값이 아니라 원 수)가 같으면 0.
2. 더하는 두 수가 다르면 평범하게 더해준다.

20까지의 님 더미 숫자를 나열하면 다음과 같다. 참고로 님 값에 규칙성이 있는지 아닌지는 밝혀지지 않았고, 언젠가는 주기를 띌 것이라는 추측만이 있다. 그런데 2³⁵까지 님 값을 구한 사람에 따르면, 규칙성은 보이지 않는다고.

숫자	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
님	0	0	1	0	2	1	0	2	1	0	2	1	3	2	1	3	2	4	3	0

이제 위 표를 활용하여 실제로 플레이 해보자.

1. 첫 숫자는 9. 9의 님 숫자가 0이 아니므로, 선공을 해야한다. 7과 2로 쪼개면 님 합이 0이다.
2. 7을 1, 6로 쪼갰다 하자.
   • 6을 2, 4로 쪼개면 당신의 승리.
3. 7을 2, 5로 쪼갰다 하자.
   • 5를 1, 4로 쪼개면 당신의 승리.
4. 7을 3, 4로 쪼갰다 하자.
   • 3을 1, 2로 쪼개면 당신의 승리.

눈치가 빠른 사람은 "님 합을 0으로 만들 수 없는 경우가 있는 데?"라고 질문을 던질 것이다. 확실히, 15같은 경우는 어떤 수로 쪼개도 님 합을 0으로 만들 수 없다. 이런 경우의 당신의 전략은, 상대방도 님 합을 0으로 만들 수 없게 쪼개는 것이다. 15의 경우는 2와 13으로 쪼개는 쪽이 가장 낫다.

요약하자면, 그룬디 게임의 필승 전략은 각 수의 님 값을 전부 알아 놓은 뒤, 님 합을 0으로 만드는 쪽으로 플레이 하면 된다.

숫자 지우기

여러개의 숫자가 있고, 번갈아 가면서 숫자를 지울 때, 최후에 남은 숫자 하나, 혹은 둘의 규칙성에 따라 승패가 결정되는 게임. 경우에 따라서는 숫자를 지운 뒤 규칙에 따라 새로운 숫자를 쓰는 경우도 있다. 위의 님 게임과 그룬디 게임이 대학 이상에서나 볼 수 있다면, 이쪽은 수학 경시대회에 자주 출몰하는 유형. 중, 고등학생을 대상으로 하는 문제이기 때문에 복잡한 수학이론 보다는 간단한 수학적 사실을 활용하는 문제가 많다. 또한, 문제가 하나 같이 다 "칠판에 x개의 수, 1, 2, …, x가 있습니다. 갑과 을이 번갈아…"로 시작한다는 것도 특징이라면 특징. 사실 이 유형은 만들려면 한 없이 많이 만들 수 있다. 아래 문제들은 난이도 순으로 정렬하였다.

칠판에 1부터 n까지의 자연수가 있다. 번갈아 가면서 두 수를 골라 지우고, 칠판에 두 수의 합, 또는 차를 새로 적는다. 최후에 남은 숫자가 짝수면 선공의 승리, 홀수면 후공의 승리일 때, 당신의 필승 전략은?

힌트 쟈잔! 너무 쉬워서 힌트가 필요 없어요! 뭐 임마?

풀이 끝까지 해보면 결국 칠판의 모든 수를 다 더한 것과 결과가 같다. 중간에 두 수의 차를 구해도, 결과의 기우성에는 변함이 없다. n이 홀수면 전체 수의 합이 홀수이므로 후공, n이 짝수면 전체 수의 합이 짝수이므로 선공을 하자. 전략은 필요 없고, 아무 생각없이 숫자를 지우기만 하면 된다.