필승 전략 게임

이 문서는 리브레 위키 사용자들의 추천으로 좋은 글로 인증된 문서입니다!

필승 전략 게임은 어느 한 쪽이 반드시 이길 수 있는 전략을 가진 게임을 말한다.

정의

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

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

가장 많이 알려진 필승 전략 게임은 배스킨 라빈스 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]라 하자. 또한, [math]\displaystyle{ s\neq0 }[/math]이기 때문에 [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\gt y_k }[/math]임을 보일 것이다. [math]\displaystyle{ x_k }[/math]와 [math]\displaystyle{ y_k }[/math]의 [math]\displaystyle{ d }[/math]자리 왼쪽은 전부 똑같고, [math]\displaystyle{ d }[/math]자리의 수는 1에서 0으로 줄어든다. 이 차이는 10진법으로 [math]\displaystyle{ 2^d }[/math]이고, [math]\displaystyle{ d }[/math]자리 오른쪽의 수는 아무리 차이나 봤자 [math]\displaystyle{ 2^d-1 }[/math]이다. 따라서 [math]\displaystyle{ x_k }[/math]는 [math]\displaystyle{ y_k }[/math]보다 적어도 1 크다. 이는 곧 [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진법의 님 합을 정의해야 한다. 그룬디 게임에서의 님 합의 정의는 다음과 같다.

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

힌트 홀수와 짝수가 서로 연산되는 경우에만 홀수가 나온다. 홀수의 개수를 세어볼것 이해가 안되면 모든 짝수는 0 모든 홀수는 1로 놓고 계산해볼것

풀이 끝까지 해보면 결국 칠판의 모든 수를 다 더한 것과 결과가 같습니다. 중간에 두 수의 차를 구해도, 결과의 기우성에는 변함이 없죠. n을 4로 나눴을 때 나머지가 1, 2면 최후에 홀수가 남기 때문에 후공을, n을 4로 나눴을 때 나머지가 0, 3이면 최후에 짝수가 남기 때문에 선공을 하면 됩니다. 전략은 필요 없고, 아무 생각없이 숫자를 지우기만 하면 됩니다.

칠판에 1부터 31까지의 자연수가 있다. 번갈아 가면서 숫자 하나를 지우는데, 최후에 남은 두 숫자의 합이 5로 나누어 떨어지면 선공의 승리, 아니면 후공의 승리다. 이 때, 당신의 필승 전략은?

힌트 5로 나눈 나머지에 따라 숫자를 다섯 가지 종류로 분류가 가능합니다.

풀이 선공을 해야 합니다. 5로 나눈 나머지에 따라 숫자를 다섯 가지로 분류하면, A={1, 6, 11, 16, 21, 26, 31}, B={2, 7, 12, 17, 22, 27}, C={3, 8, 13, 18, 23, 28}, D={4, 9, 14, 19, 24, 29}, E={5, 10, 15, 20, 25, 30}입니다. 당신이 A 그룹의 숫자를 지우면 상대방은 D 그룹의 숫자를, B→C, C→B, D→A, E→E를 지워줘야 합니다. 그러면 최후에 남는 세 수는 A 그룹에서 하나, 그리고 대응되는 두 그룹에서 각각 하나씩이고, 당신은 A 그룹의 숫자 하나를 지워주면 됩니다. 만약 상대방이 전략적이지 못해 대응되는 그룹의 숫자를 지우지 않으면 조금 꼬이게 되는데, 마지막 턴에 대응되는 두 그룹에서 각각 하나씩, 그리고 E 그룹을 제외한 다른 그룹에서 하나, 이렇게 3 숫자가 남게 맞춰주면 됩니다.

칠판에 2부터 1000까지의 자연수가 있다. 번갈아 가면서 숫자 하나를 지우는데, 최후에 남은 두 수가 서로소이면 선공의 승리, 아니면 후공의 승리다. 이 때, 당신의 필승 전략은?

힌트 연속된 두 수는 항상 서로소입니다.

풀이 선공을 해야 합니다. 먼저 2를 지웁니다. 이제, 상대방이 홀수를 지우면 그 뒤의 수를, 짝수를 지우면 그 앞의 수를 지우면 최후에는 이웃한 두 수만이 남고, 이웃한 두 수는 항상 서로소라 선공의 승리입니다.

칠판에 10부터 99까지의 수가 있다. 번갈아 가면서 숫자를 최대 3개까지 지우는 데, 지운 숫자 위에 그 수의 각 자릿수의 합을 적는다. 만약 똑같은 각 자릿수의 합이 3번째 나오면, 그 사람의 패배다. 이 때, 당신의 필승 전략은?

힌트 가능한 자릿수의 합과 그 개수부터 찾아보세요.

풀이 선공을 해야 합니다. 가능한 각 자릿수의 합은 1부터 18까지고, 이 중 1과 18은 단 한 번 밖에 나올 수 없습니다. 2부터 17까지는 두 번 이상 나옵니다. 그럼 지울 수 있는 수의 최댓값은 2+2×16=34 입니다. 이제, 당신이 먼저 10과 99를 지웁니다. 그 뒤에 상대방이 1개를 지우면 3개를, 2개를 지우면 2개, 3개를 지우면 1개씩 지워주면 당신의 차례에 34개의 수를 모두 지우게 됩니다. 이 뒤에 상대방이 숫자를 지우면 같은 각 자릿수의 합이 세 번째 등장하고, 상대방의 패배입니다. 아 물론, 당신이 수를 지울 때 같은 각 자릿수의 합이 세 번 등장하지 않게 지워야 합니다.

기타

어느 문단에도 속하기 애매한 필승 전략 게임들. 윗 문단의 숫자 지우기가 정수론적 성질을 주로 활용한다면, 이쪽은 그 외 수학 성질들을 활용하는 문제가 많다.

[math]\displaystyle{ ?x^n+?x^{n-1}+\cdots+?x+?=0 }[/math]이란 방정식이 있다 하자. 번갈아 가면서 ?에 숫자를 하나씩 채워 넣는다 (굳이 실수일 필요는 없다). 모든 ?가 채워졌을 때, 그 방정식에 정수해가 존재하면 선공의 승리, 그렇지 않으면 후공의 승리다. 당신의 필승 전략은?

힌트 짠! 너무 쉬워서 힌트가 필요 없어요! 아니 이 녀석이 또...

풀이 상수항이 0이면 x=0을 무조건 근으로 가집니다. 즉, 마지막 ?를 채우는 사람이 반드시 이기게 되죠. n이 짝수면 ?의 개수가 홀수이므로 선공의 승리, 홀수면 ?가 짝수 개 있으므로 후공의 승리입니다.

2부터 시작하여, 번갈아 가면서 그 수의 약수를 원래 수에 더하는 게임을 한다 하자. 예를 들면, 2→3→6→9→18→24→…와 같이. 100 이상의 수를 먼저 부르면 이기는 것이라 할 때, 필승 전략은 무엇인가?

힌트 49를 부르면 이깁니다.

풀이 먼저 3을 부르면 됩니다. 홀수의 약수는 모두 홀수이므로, 상대방이 어떤 약수를 더하든 짝수가 됩니다. 따라서 상대방은 절대 49를 부를 수 없죠. 반면, 당신은 1씩만 올려주면 여유롭게 49를 부를 수 있습니다. 만약 그 전에 상대방이 50이상의 수를 부르면 두 배를 하고, 당신의 승리. 당신이 49를 부르면 상대방이 무슨 약수를 더하든 50 이상이 되고, 당신이 이기게 됩니다.

관련 용어

• 조합론적 게임 이론 (Combinatorial game theory): 완전한 정보를 가진 턴제 게임에 대해 수학적으로 연구하는 학문. 불완전한 정보를 가진 게임에 대해 연구하는 학문은 게임 이론 참조.
• 완전한 정보 (Perfect information): 조합론적 게임 이론에선, 수를 두기 위한 모든 정보를 알고 있는 것을 말한다.

• 공정 게임 (Impartial game): 수를 둘 때, 선공인지 후공인지에만 영향을 받고, 그 외의 모든 규칙이나 요인과는 관계가 없는 게임. 다르게 말하면, 선공과 후공의 차이는 먼저 하냐 나중에 하냐, 그것 뿐인 게임을 말한다. 예를 들면, 선공에 여러 가지 제한이 붙는 오목은 공정 게임이 아니며, 자신의 말만 움직일 수 있는 바둑이나 체스 역시 공정 게임이 아니다. 반면, NIM 게임은 공정 게임이다. 필승 전략이 있는데???
• 편파 게임 (Partisan game): 공정 게임이 아닌 게임. 대부분의 게임이 이 분류에 속한다.
• 노말 게임 (Normal game): 최후의 수를 두는 사람이 이기는 게임. 즉, 자기 차례에 할 게 없으면 진다.
• 미저 게임 (Misère game): 노말 게임의 반대로, 지는 것이 이기는 게임. 모순 다르게 표현하면, 최후의 수를 두는 사람이 지는 게임이다.

• 님 (Nim): 원래는 님 게임만을 가르키지만, 게임의 특성 때문에 필승 전략이 있는 게임을 NIM이라 부르기도 한다.
• 님 힙 (Nim-heap): 님 게임에서, 특정 값들의 묶음을 말한다.
• 님버(Nimber): 님 힙의 값.
• 님 값 (Nim value, Grundy value): 공정 게임과 동일한 특수한 값.
• 님 합 (Nim-sum): 님 값을 더하는 특수한 방법.

관련 문서

• 사기죄
• 승부조작
• 게임 이론

외부 링크

• Wikipedia:Nim
• Wikipedia:Sprague–Grundy theorem: 간단히 설명하면, 모든 노말 공정 게임은 님버와 동등하다는 정리이다.
• 공정 게임 이론
• 3줄 짜리 님
• 슈퍼 님
• 그룬디 게임