필승 전략 게임

개요

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

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

가장 많이 알려진 필승 전략 게임은 "배스킨 라빈스 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의 개수를 짝수 개로 만들어 주는 것이다. 단, 가장 마지막에는 각 자릿수에 존재하는 1의 개수를 홀수 개로 맞춰줘야 한다. 만약 마지막 돌을 가져가면 이기는 게임일 경우에는 상관 없다.

위 과정을 좀 더 일반화 및 추상화 시켜보자. 일반적인 연산 방법은 통하지 않기에 새로운 방법이 필요하다. 이 미지의 연산을 기호로 [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으로 만들어 주는 수가 존재하냐이다. 결론부터 말하면 그렇다이며, 증명은 아랫 문단을 참조하자.