| 최신판 |
당신의 편집 |
| 1번째 줄: |
1번째 줄: |
| {{추천 문서}} | | {{학술}} |
| '''필승 전략 게임'''은 어느 한 쪽이 반드시 이길 수 있는 전략을 가진 [[게임]]을 말한다.
| |
|
| |
|
| == 정의 == | | == 개요 == |
| 필승 전략 게임을 정의하는 데에 있어 중요한 점은 운이나 실력이 아닌 철저한 '''수학적 계산'''만을 사용하여 이기는 게임인지 여부다. 이 때문에 확률 놀음인 [[포커]]나 실력이 중요한 [[바둑]]은 이 범위에서 제외된다. 또한, 무수히 많은 [[경우의 수]]를 사용한 승리 전략이나 승패가 결정되지 않는 게임 역시 제외된다. 전자의 예로는 [[오목]]이 있으며,<ref>아무런 규칙도 택하지 않을 경우, 먼저 두는 흑에게 필승 전략이 있기는 하지만 경우의 수가 너무 많다.</ref> 후자의 예는 [[틱택토]]가 있다.<ref>두 사람이 모두 전략적으로만 플레이하면 비기게 된다.</ref> 마지막으로, 여러명이 하는 게임이 아닌 일대일 대결 게임만을 다룬다. | | '''필승 전략 게임'''이란, 이름 그대로 어느 한 쪽이 반드시 이길 수 있는 전략을 가진 게임을 말한다. 중요한 것은, 운이나 실력이 아닌 철저한 '''수학적 계산'''만을 사용하여 이기는 게임만을 다룬다. 이 때문에 확률 놀음인 [[포커]]나 실력이 중요한 [[바둑]]은 이 범위에서 제외된다. 또한, 무수히 많은 [[경우의 수]]를 사용한 승리 전략이나 승패가 결졍되지 않는 게임 역시 제외된다. 전자의 예로는 [[오목]]이 있으며,<ref>아무런 규칙도 택하지 않을 경우, 먼저 두는 흑에게 필승 전략이 있기는 하지만 경우의 수가 너무 많다.</ref> 후자의 예는 [[틱택토]]가 있다.<ref>두 사람이 모두 전략적으로만 플레이하면 비기게 된다.</ref> 마지막으로, 여러명이 하는 게임이 아닌 일대일 대결 게임만을 다룬다. |
|
| |
|
| 어떤 게임의 필승 전략을 찾는 것은 소위 말하는 창의력 수학의 단골 소재. [[수학 경시대회]]에 나오는 경우도 간혹 있다. 대부분의 경우는 방법을 찾는 것만으로 끝나게 되지만, 게임에 따라서는 그 방법이 왜 필승 전략인지 [[증명]]을 해야하는 경우도 있다. 하지만 문제 유형이 거기서 거기라 몇 가지 유형을 풀어봤다면 "아, 이거는 이 방법이구나"하고 감이 온다. | | 어떤 게임의 필승 전략을 찾는 것은 소위 말하는 창의력 수학의 단골 소재. [[수학 경시대회]]에 나오는 경우도 간혹 있다. 대부분의 경우는 방법을 찾는 것만으로 끝나게 되지만, 게임에 따라서는 그 방법이 왜 필승 전략인지 [[증명]]을 해야하는 경우도 있다. 하지만 문제 유형이 거기서 거기라 몇 가지 유형을 풀어봤다면 "아, 이거는 이 방법이구나"하고 감이 온다. |
|
| |
|
| 가장 많이 알려진 필승 전략 게임은 배스킨 라빈스 31이라는 게임일 것이다. 31을 부르면 지는<ref>규칙에 따라서는 이기는</ref> 게임으로, 초등학교 수준의 필승 전략이 존재하지만 이 사실을 모르는 사람이 매우 많다. 그러나 필승 전략을 사용하여 상대방을 농락하는 짓은 착한 위키러라면 하지 말자. 더욱이 게임에 '''돈'''을 건다면…….{{ㅊ|사기죄}} | | 가장 많이 알려진 필승 전략 게임은 "배스킨 라빈스 31"이라는 게임일 것이다. 31을 부르면 지는<ref>규칙에 따라서는 이기는</ref> 게임으로, 초등학교 수준의 필승 전략이 존재하지만 이 사실을 모르는 사람이 매우 많다. 그러나 필승 전략을 사용하여 상대방을 농락하는 짓은 착한 위키러라면 하지 말자. 더욱이 필승 전략 게임에 '''돈'''을 건다면... {{ㅊ|사기죄}} |
|
| |
|
| == 목록 == | | == 목록 == |
| === NIM 게임 === | | === NIM 게임 === |
| 가장 대표적인 유형으로, 개요에서 예시로 들은 배스킨 라빈스 31도 님 게임의 일종이다. 이름의 NIM의 어원은 알려지지 않았으며, 훔치다라는 뜻의 영어 동사 nim에서 왔다는 설,<ref>nim은 현재 사어(死語)다.</ref> 가지고 가다라는 뜻의 독일어 nimm에서 왔다는 설, NIM을 뒤집으면 WIN이기 때문에 NIM이라는 설 등이 있다. 이름 뿐만 아니라 게임 자체의 기원도 명확하지 않은데, 고대 중국의 돌 줍기 게임에서 왔다는 설,<ref>Yaglom, I. M. (2001), "Two games with matchsticks", in Tabachnikov, Serge, Kvant Selecta: Combinatorics, I, Volume 1, Mathematical world 17, American Mathematical Society, p. 1–8</ref> 유럽의 선술집에서 하던 성냥개비 게임에서 왔다는 설 등이 있다. 어느 쪽이든 확실한 증거는 없다. {{ㅊ|그럼 도대체 뭐야 이 게임}} | | 가장 대표적인 유형으로, 개요에서 예시로 들은 배스킨 라빈스 31도 님 게임의 일종이다. 이름의 NIM의 어원은 알려지지 않았으며, 훔치다라는 뜻의 영어 동사 nim에서 왔다는 설,<ref>nim은 현재는 사어(死語)다.</ref> 가지고 가다라는 뜻의 독일어 nimm에서 왔다는 설, NIM을 뒤집으면 WIN이기 때문에 NIM이라는 설 등이 있다. 이름 뿐만 아니라 게임 자체의 기원도 명확하지 않은데, 고대 중국의 돌 줍기 게임에서 왔다는 설,<ref>Yaglom, I. M. (2001), "Two games with matchsticks", in Tabachnikov, Serge, Kvant Selecta: Combinatorics, I, Volume 1, Mathematical world 17, American Mathematical Society, p. 1–8</ref> 유럽의 선술집에서 하던 성냥개비 게임에서 왔다는 설 등이 있다. 어느 쪽이든 확실한 증거는 없다. {{ㅊ|그럼 도대체 뭐야 이 게임}} |
|
| |
|
| 기본적인 룰은 여러 개의 돌 더미 중 하나를 골라 그 더미 안의 돌을 가져가는 것이며, 가장 마지막 돌을 가져가는 사람이 지는 게임이다. 규칙에 따라서는 마지막 돌을 가져가는 사람이 이기게 만들 수도 있으며, 수학적인 필승 전략과 그 원리는 동일하다. 아래 내용은 특별한 말이 없는한 마지막 돌을 가져가는 사람이 패배하는 규칙을 따른다. | | 기본적인 룰은 여러개의 돌 더미 중 하나를 골라 그 더미 안의 돌을 가져가는 것이며, 가장 마지막 돌을 가져가는 사람이 지는 게임이다. 규칙에 따라서는 마지막 돌을 가져가는 사람이 이기게 만들 수도 있으며, 수학적인 필승 전략과 그 원리는 동일하다. 아래 내용은 특별한 말이 없는한 마지막 돌을 가져가는 사람이 패배하는 규칙을 따른다. |
|
| |
|
| ==== 한 더미 ==== | | ==== 한 더미 ==== |
| 20번째 줄: |
19번째 줄: |
| {{숨기기|힌트|30을 부르면 반드시 이길 수 있습니다. 30을 부르려면 어떤 수를 불러야 할까요?}} | | {{숨기기|힌트|30을 부르면 반드시 이길 수 있습니다. 30을 부르려면 어떤 수를 불러야 할까요?}} |
| {{숨기기|풀이|30을 부르면 당신의 승리가 보장됩니다. 한 번에 숫자를 세 개까지 부를 수 있으므로, 30-(3+1)<nowiki>=</nowiki>26을 당신이 부르면 상대방이 몇 개의 숫자를 부르든 당신은 30을 부를 수 있습니다. 26을 부르기 위해서는 22를 부르면 되고, 22를 부르기 위해서는 18, 이런 식으로 쭉 내려가면 2를 불렀을 때 승리가 보장됩니다. 따라서 당신이 '''먼저''' 수를 2까지 부르면 승리합니다.}} | | {{숨기기|풀이|30을 부르면 당신의 승리가 보장됩니다. 한 번에 숫자를 세 개까지 부를 수 있으므로, 30-(3+1)<nowiki>=</nowiki>26을 당신이 부르면 상대방이 몇 개의 숫자를 부르든 당신은 30을 부를 수 있습니다. 26을 부르기 위해서는 22를 부르면 되고, 22를 부르기 위해서는 18, 이런 식으로 쭉 내려가면 2를 불렀을 때 승리가 보장됩니다. 따라서 당신이 '''먼저''' 수를 2까지 부르면 승리합니다.}} |
| | |
| 위 문제를 해결했으면, 일반적인 경우에 도전해 보자. | | 위 문제를 해결했으면, 일반적인 경우에 도전해 보자. |
| {{인용문2|두 사람이 1부터 번갈아 숫자를 부른다. 한 번에 x개의 숫자를 부를 수 있으며, n을 부르면 진다. 필승 전략은 무엇일까?}} | | {{인용문2|두 사람이 1부터 번갈아 숫자를 부른다. 한 번에 x개의 숫자를 부를 수 있으며, n을 부르면 진다. 필승 전략은 무엇일까?}} |
| {{숨기기|풀이|n-1을 부르면 이깁니다. n-1을 부르기 위해서는 n-1-(x+1)<nowiki>=</nowiki>n-x-2을 부르면 됩니다. 이 과정을 계속 반복하여 최초에 불러야 하는 수를 부르면 됩니다.}} | | {{숨기기|풀이|n-1을 부르면 이긴다. n-1을 부르기 위해서는 n-1-(x+1)<nowiki>=</nowiki>n-x-2을 부르면 된다. 이 과정을 계속 반복하여 최초에 불러야 하는 수를 부르면 된다.}} |
| | |
| 마지막으로, n을 부르면 '''이기는''' 경우의 필승 전략도 생각해 보자. | | 마지막으로, n을 부르면 '''이기는''' 경우의 필승 전략도 생각해 보자. |
| {{숨기기|풀이|상대방이 n을 부를 수 없게 할려면, 자신이 n-(x+1)<nowiki>=</nowiki>n-x-1을 부르면 됩니다. 그러면 상대방이 몇 개의 수를 부르든 당신 차례에 n은 x개의 안에 있으므로, 당신은 항상 n을 부를 수 있습니다. 이 과정을 반복하면 됩니다.}} | | {{숨기기|풀이|상대방이 n을 부를 수 없게 할려면, 자신이 n-(x+1)<nowiki>=</nowiki>n-x-1을 부르면 된다. 그러면 상대방이 몇 개의 수를 부르든, n은 x개의 안에 있으므로 당신은 항상 n을 부를 수 있다. 이 과정을 반복하면 된다.}} |
|
| |
|
| ==== 두 더미 ==== | | ==== 두 더미 ==== |
| 돌 더미가 두 개인 경우. 매 턴, 한 더미를 정해 돌을 가져가며, 가져가는 돌의 개수에는 제한이 없다. 한 더미의 돌 전체를 싹 다 빼버려도 가능하단 소리. 아래 예시를 직접 해결해 보자.
| |
| {{인용문2|두 줄의 돌 더미가 있습니다. 첫 번째 줄에는 돌이 10개, 두 번째 줄에는 돌이 7개. 당신이 이기기 위해서는 먼저 해야할까요 나중에 해야할까요? 당신의 필승 전략은?}}
| |
| {{숨기기|힌트|2, 2를 만들면 당신의 승리가 보장됩니다. 왜 일까요?}}
| |
| {{숨기기|풀이|당신이 먼저 해야합니다. 첫 번째 줄에서 돌 3개를 빼 7, 7을 만듭니다. 상대방이 바보가 아닌 이상 한 줄 전체를 빼거나 한 줄에 돌을 하나만 남겨 놓을리는 없습니다. 만약 상대방이 그러면 비웃어 주세요. 그렇지 않으면, 두 줄의 돌의 개수를 똑같이 맞춰 주면 됩니다. 2, 2 상태가 된 후, 상대방이 한 줄을 지우면 당신은 남은 줄에서 돌 하나를 빼면됩니다. 만약 상대방이 돌 하나만 뺐다면 당신이 다른 줄을 지우면 됩니다.}}
| |
| 마지막 돌을 가져가면 승리하는 경우의 전략도 한번 생각해 보자.
| |
| {{숨기기|풀이|똑같은 방법으로, 두 줄의 돌의 개수를 같게 맞춰주면 됩니다. 2, 2가 아닌 1, 1을 만드는 것을 목표로 하면 됩니다. 상대방이 한 줄 전체를 비우면 비웃어 주세요.}}
| |
| 똑같은 방법으로 일반화 된 전략을 세울 수 있으니 일반적인 경우의 해결법은 생략한다. 하지만 중요한 것은, 어째서 위 전략이 '''항상''' 성립하는지 모른다는 것이다. 문제의 답을 알지만 풀이는 모르는 그런 경우. 이 필승 전략에 대한 증명은 아랫 문단을 참조하자.
| |
|
| |
|
| ==== 세 더미 이상 ==== | | ==== 세 더미 이상 ==== |
| 돌 더미가 세 개 이상인 경우. 규칙은 두 더미의 경우와 같다. 아래 쉬운 예시를 직접 해결해 보자.
| |
| {{인용문2|세 줄의 돌 더미가 있습니다. 첫째 줄에는 1개, 둘째 줄에는 3개, 셋째 줄에는 4개. 당신이 이기기 위한 필승 전략은 무엇일까요?}}
| |
| 당신이 천부적인 수학적 재능을 가지지 않은 한, 위 문제의 필승 전략을 찾지는 못할 것이다. 설녕 위 문제를 해결했다 해도, 일반적인 경우에 대한 필승 전략을 유추하기는 매우 힘들며, 그 필승 전략의 수학적 당위성을 보이는 것은 더더욱 어렵다. 일단 위 문제의 풀이는 다음과 같다.
| |
| {{숨기기|풀이|셋째 줄에서 2개를 먼저 가져갑니다. 상대방이 줄 하나를 비우면 윗 문단의 두 더미 전략을 쓰면 됩니다. 상대방이 셋째 줄에서 돌 한 개를 가져갔거나 둘째 줄에서 돌 두 개를 가져갔다면 둘째 줄에서 두 개를 가져갑니다. 그럼 1, 1, 1이 되고, 당신의 승리입니다. 만약 상대방이 둘째 줄에서 돌 한 개를 가져갔다면 첫째 줄을 비우면 됩니다.}}
| |
|
| |
| ==== 수학적 이론 ====
| |
| 윗 문단의 풀이를 보면 도대체 이게 뭔가싶은 생각이 들 것이다. 필승 전략의 원리가 [[2진법]]이기 때문에 어찌 보면 당연한 일. 아래 케이스를 살펴보자.
| |
| {|class="wikitable"
| |
| |-
| |
| !차례||돌의 수||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>\oplus</math>로 나타내고, 님 합(Nim-sum)이라 부르기로 하자. 님 합은 다음과 같이 계산한다.
| |
| #2진법에서만 정의 된다.
| |
| #두 수의 님 합을 구할 때, 각 자릿수끼리 연산을 한다.
| |
| #각 자릿수끼리의 연산은 XOR 연산<ref>즉, 0+0=0, 0+1=1, 1+0=1, 1+1=0</ref>을 따른다.
| |
| 이제, 각 차례의 돌 더미의 님 합을 구해 보자.
| |
| {|width=250
| |
| |-
| |
| |rowspan="4"|<br /><br /><math>\oplus</math><br />=
| |
| |001||001||001||000
| |
| |-
| |
| |011||011||010||010
| |
| |-
| |
| |100||010||010||010
| |
| |-
| |
| !110||000||001||000
| |
| |}
| |
| 이제 뭔가 확실히 눈에 띄는가? 상대방의 차례에는 님 합이 항상 0이다! 이를 토대로 추상화 된 필승 전략을 세우면 다음과 같다.
| |
| #최초의 님 합이 0이 아니면 먼저, 0이면 나중에 시작한다.
| |
| #당신의 차례에 님 합을 0으로 만들어 준다.
| |
| #마지막 돌을 가져가는 것이 승리인지 패배인지에 따라 조금 다르다.
| |
| #*승리일 경우: 계속 님 합을 0으로 만들어 준다.
| |
| #*패배일 경우: 돌이 한 개 밖에 없는 더미를 홀수 개 만들어 준다. 이 외에는 님 합을 0으로 만들어 주면 된다.
| |
| 여기서 문제는, 님 합이 0이 아닐 때, '''항상''' 님 합을 0으로 만들어 주는 수가 존재하냐이다. 결론부터 말하면 '''그렇다'''이며, 증명은 아랫 문단을 참조하자.
| |
|
| |
| ==== 증명<ref>Bouton, C. L. (1901–1902), "Nim, a game with a complete mathematical theory", Annals of Mathematics 3 (14): 35–39을 참조.</ref> ====
| |
| 먼저 님 합은 일반적인 [[결합법칙]]과 [[교환법칙]]을 만족함을 쉽게 보일 수 있다. 또한, <math>x\oplus x=0</math>이고, <math>0\oplus x=x</math>이다. 이제 <math>x_1,x_2,\cdots,x_n</math>을 수를 두기 전의 각 더미의 돌의 개수, <math>y_1,y_2,\cdots,y_n</math>을 수를 둔 후의 각 더미의 돌의 개수라 하자. 또한, <math>s=x_1\oplus x_2\oplus\cdots\oplus x_n,\,t=y_1\oplus y_2\oplus\cdots\oplus y_n</math>라 하자. <math>k</math>번째 더미에서 돌을 가져가면, <math>i\neq k</math>일 때 <math>x_i=y_i</math>이고, <math>i=k</math>일 때는 <math>x_i> y_i</math>이다. 그러면,
| |
| :<math>\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><br /><math>\therefore t=s\oplus x_k\oplus y_k\quad\cdots\left(*\right)</math>
| |
| 이다.
| |
|
| |
| 이제, 우리가 보이고자 하는 것은 아래의 두 명제이다.
| |
| {{인용문2|<math>s=0</math>이면, 어떤 수를 둬도 <math>t\neq0</math>이다.<br /><math>s\neq0</math>이면, <math>t=0</math>으로 만들 수 있는 수가 존재한다.}}
| |
| #먼저, <math>s=0</math>이라 가정하자. 돌이 아예 없는 경우에는 승패가 명확하게 결정 된 상태이므로 의미가 없다. 따라서 수를 둘 수 있다 가정하자. 그러면 (*)에서, <math>t=0\oplus x_k\oplus y_k=x_k\oplus y_k</math>이고, <math>x_k\neq y_k</math>이므로 <math>t=x_k\oplus y_k\neq0</math>이다.
| |
| #이제 <math>s\neq0</math>이라 가정하자. <math>s</math>를 2진법으로 나타내었을 때, 제일 왼쪽에 존재하는 1의 자리를 <math>d</math>라 하자.<ref>만약 <math>s</math>가 00101101이면, <math>d=6</math>이다.</ref> 또한, <math>s\neq0</math>이기 때문에 <math>d</math>의 존재가 보장된다. 이제 2진법으로 나타냈을 때, <math>d</math>번째 자리의 수가 0이 아닌 <math>x_k</math>를 고른다. 만약 이런 <math>x_k</math>가 존재하지 않는다면, 모든 <math>x_i</math>의 <math>d</math>번째 자리는 0이고, 님 합을 구하면 <math>s</math>의 <math>d</math>번째 자리는 0이 되어 모순이다. 이제 <math>y_k=s\oplus x_k</math>라 하자. <math>x_k> y_k</math>임을 보일 것이다. <math>x_k</math>와 <math>y_k</math>의 <math>d</math>자리 왼쪽은 전부 똑같고,<ref><math>s</math>의 <math>d</math>자리 왼쪽은 전부 0이므로</ref> <math>d</math>자리의 수는 1에서 0으로 줄어든다. 이 차이는 10진법으로 <math>2^d</math>이고, <math>d</math>자리 오른쪽의 수는 아무리 차이나 봤자 <math>2^d-1</math>이다. 따라서 <math>x_k</math>는 <math>y_k</math>보다 적어도 1 크다. 이는 곧 <math>x_k-y_k</math>개의 돌을 <math>k</math>번째 더미에서 가져갈 수 있음을 보장한다. 또한, (*)에서, <math>t=s\oplus x_k\oplus y_k=s\oplus x_k\oplus\left(s\oplus x_k\right)=0</math>이다.
| |
|
| |
|
| ==== 변형 NIM ==== | | ==== 변형 NIM ==== |
| 역사가 오래된 게임인 만큼, 여러 가지 변형된 님 게임이 존재한다. 사실 엄밀하게 따지면, 돌 더미가 한 개인 경우의 님 게임은 이쪽에 속한다.
| |
| *원형 님 (Circular Nim)
| |
| 돌 더미가 한 개인 경우의 님 게임과 비슷하지만, 돌들이 '''원형'''으로 놓여있는 경우. 한 번에 가져갈 수 있는 돌의 개수에 제한이 있는 것 까지는 같지만, 가져가는 돌들은 서로 '''인접'''해야 한다. 원조 님 게임과 비슷한 이론을 쓰긴 하지만 이 게임 만의 독특한 수학 이론이 많이 필요하다.<ref>[http://web.calstatela.edu/faculty/sheubac/presentations/SLOtalk.pdf 1], [http://arxiv.org/pdf/1211.0091.pdf 2] 참조</ref>
| |
| *슈퍼 님 (Super Nim)
| |
| 돌 더미가 일차원적으로 나열되어 있는게 아니라, '''이차원'''적으로 나열되어 있는 경우. 다르게 설명하자면, 바둑판의 격자 위에 돌들이 나열되어 있고, 매 턴 가로, 세로 중 한 줄을 골라 돌을 가져가는 것이다.
| |
| *구성 님 (Building Nim)
| |
| 돌 더미를 구성하는 것 부터 시작하는 님 게임. n개의 돌과 k개의 빈 더미가 있을 때, 번갈아가면서 돌 '''하나'''를 임의의 더미에 놓는다. 모든 돌을 사용했을 때, 님 게임이 시작된다. 얼핏보면 님 게임과 다를게 없어보이지만, 돌의 개수에 따라 님 게임이 시작되었을 때 선공인지 후공인지가 먼저 결정되어 있다. 즉, 님 합을 0으로 만드느냐 아니냐를 먼저 생각해 주어야 하는 복잡한 게임. <ref>[http://arxiv.org/pdf/1502.04068v1.pdf #] 참조</ref>
| |
|
| |
|
| === 그룬디 게임 === | | === 그룬디 게임 === |
| 위키백과에서는 님 게임의 일종으로 보고 있지만, 실제로 해보면 님 게임과는 이질적이다. 기본적인 규칙은 아래와 같다.
| |
| #숫자 하나가 있다. 예로 10이 있다 하자.
| |
| #번갈아가면서 숫자를 두 개의 '''다른''' 숫자로 쪼갠다. 즉, 10→7, 3은 되지만, 10→5, 5는 안 된다.
| |
| #자기 차례에 더이상 쪼갤 숫자가 없다면 패배. 즉, 모든 숫자가 1 또는 2면 진다.
| |
| 이 게임의 필승 전략은 [[Wikipedia:Sprague-Grundy theorem|스프라그-그룬디 정리]]를 응용하여 해결할 수 있다. 영포자나 수포자를 위해 아주 정말 단순하게 결과만을 설명하자면, 각 숫자에는 수학적으로 계산된 님 더미 숫자(nim heap size, 님 값)가 있는데, 수를 쪼갠 뒤의 님 합이 0이 되도록 해주면 이긴다. 참고로 위 에서는 님 합이 2진법에서만 정의된다 하였는데, 그룬디 게임에선 10진법의 님 합을 정의해야 한다. 그룬디 게임에서의 님 합의 정의는 다음과 같다.
| |
| #더하는 두 수(님 값이 아니라 원 수)가 같으면 0.
| |
| #더하는 두 수가 다르면 평범하게 더해준다.
| |
| 20까지의 님 더미 숫자를 나열하면 다음과 같다.<ref>더 많은 값은 [https://oeis.org/A002188 #] 여기로. 참고로 1이 아니라 0부터 시작이다.</ref> 참고로 님 값에 규칙성이 있는지 아닌지는 밝혀지지 않았고, 언젠가는 주기를 띌 것이라는 추측만이 있다.<ref>E. Berlekamp, J. H. Conway, R. Guy. Winning Ways for your Mathematical Plays. Academic Press, 1982.</ref> 그런데 2<sup>35</sup>까지 님 값을 구한 사람에 따르면, 규칙성은 보이지 않는다고.
| |
| :{|width=100%
| |
| |-
| |
| |숫자||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
| |
| |}
| |
| 이제 위 표를 활용하여 실제로 플레이 해보자.
| |
| #첫 숫자는 9. 9의 님 숫자가 0이 아니므로, 선공을 해야한다. 7과 2로 쪼개면 님 합이 0이다.
| |
| #7을 1, 6로 쪼갰다 하자.
| |
| #*6을 2, 4로 쪼개면 당신의 승리.
| |
| #7을 2, 5로 쪼갰다 하자.
| |
| #*5를 1, 4로 쪼개면 당신의 승리.
| |
| #7을 3, 4로 쪼갰다 하자.
| |
| #*3을 1, 2로 쪼개면 당신의 승리.
| |
| 눈치가 빠른 사람은 "님 합을 0으로 만들 수 없는 경우가 있는 데?"라고 질문을 던질 것이다. 확실히, 15같은 경우는 어떤 수로 쪼개도 님 합을 0으로 만들 수 없다. 이런 경우의 당신의 전략은, '''상대방도 님 합을 0으로 만들 수 없게''' 쪼개는 것이다. 15의 경우는 2와 13으로 쪼개는 쪽이 가장 낫다.
| |
|
| |
| 요약하자면, 그룬디 게임의 필승 전략은 각 수의 님 값을 전부 알아 놓은 뒤, 님 합을 0으로 만드는 쪽으로 플레이 하면 된다.
| |
|
| |
|
| === 숫자 지우기 === | | === 숫자 지우기 === |
| 여러 개의 숫자가 있고, 번갈아 가면서 숫자를 지울 때, 최후에 남은 숫자 하나, 혹은 둘의 규칙성에 따라 승패가 결정되는 게임. 경우에 따라서는 숫자를 지운 뒤 규칙에 따라 새로운 숫자를 쓰는 경우도 있다. 위의 님 게임과 그룬디 게임이 대학 이상에서나 볼 수 있다면, 이쪽은 [[수학 경시대회]]에 자주 출몰하는 유형. 중, 고등학생을 대상으로 하는 문제이기 때문에 복잡한 수학이론 보다는 간단한 수학적 사실을 활용하는 문제가 많다. 또한, 문제가 하나 같이 다 "칠판에 x개의 수, 1, 2, …, x가 있습니다. 갑과 을이 번갈아…"로 시작한다는 것도 특징이라면 특징. 사실 이 유형은 만들려면 한 없이 많이 만들 수 있다.
| |
|
| |
| {{인용문2|칠판에 1부터 n까지의 자연수가 있다. 번갈아 가면서 두 수를 골라 지우고, 칠판에 두 수의 합, 또는 차를 새로 적는다. 최후에 남은 숫자가 짝수면 선공의 승리, 홀수면 후공의 승리일 때, 당신의 필승 전략은?}}
| |
| {{숨기기|힌트|'''홀수와 짝수가 서로 연산되는 경우에만 홀수가 나온다. 홀수의 개수를 세어볼것 이해가 안되면 모든 짝수는 0 모든 홀수는 1로 놓고 계산해볼것''' }}
| |
| {{숨기기|풀이|끝까지 해보면 결국 칠판의 모든 수를 다 더한 것과 결과가 같습니다. 중간에 두 수의 차를 구해도, 결과의 기우성에는 변함이 없죠. n을 4로 나눴을 때 나머지가 1, 2면 최후에 홀수가 남기 때문에 후공을, n을 4로 나눴을 때 나머지가 0, 3이면 최후에 짝수가 남기 때문에 선공을 하면 됩니다. 전략은 필요 없고, 아무 생각없이 숫자를 지우기만 하면 됩니다.}}
| |
|
| |
| {{인용문2|칠판에 1부터 31까지의 자연수가 있다. 번갈아 가면서 숫자 하나를 지우는데, 최후에 남은 두 숫자의 합이 5로 나누어 떨어지면 선공의 승리, 아니면 후공의 승리다. 이 때, 당신의 필승 전략은?}}
| |
| {{숨기기|힌트|5로 나눈 나머지에 따라 숫자를 다섯 가지 종류로 분류가 가능합니다.}}
| |
| {{숨기기|풀이|선공을 해야 합니다. 5로 나눈 나머지에 따라 숫자를 다섯 가지로 분류하면, A<nowiki>=</nowiki>{1, 6, 11, 16, 21, 26, 31}, B<nowiki>=</nowiki>{2, 7, 12, 17, 22, 27}, C<nowiki>=</nowiki>{3, 8, 13, 18, 23, 28}, D<nowiki>=</nowiki>{4, 9, 14, 19, 24, 29}, E<nowiki>=</nowiki>{5, 10, 15, 20, 25, 30}입니다. 당신이 A 그룹의 숫자를 지우면 상대방은 D 그룹의 숫자를, B→C, C→B, D→A, E→E를 지워줘야 합니다. 그러면 최후에 남는 세 수는 A 그룹에서 하나, 그리고 대응되는 두 그룹<ref>(A, D), (B, C), (E, E) 중 하나</ref>에서 각각 하나씩이고, 당신은 A 그룹의 숫자 하나를 지워주면 됩니다. 만약 상대방이 전략적이지 못해 대응되는 그룹의 숫자를 지우지 않으면 조금 꼬이게 되는데, 마지막 턴에 대응되는 두 그룹에서 각각 하나씩, 그리고 E 그룹을 제외한 다른 그룹에서 하나, 이렇게 3 숫자가 남게 맞춰주면 됩니다.}}
| |
|
| |
| {{인용문2|칠판에 2부터 1000까지의 자연수가 있다. 번갈아 가면서 숫자 하나를 지우는데, 최후에 남은 두 수가 [[서로소]]이면 선공의 승리, 아니면 후공의 승리다. 이 때, 당신의 필승 전략은?}}
| |
| {{숨기기|힌트|연속된 두 수는 항상 서로소입니다.}}
| |
| {{숨기기|풀이|선공을 해야 합니다. 먼저 2를 지웁니다. 이제, 상대방이 홀수를 지우면 그 뒤의 수를, 짝수를 지우면 그 앞의 수를 지우면 최후에는 이웃한 두 수만이 남고, 이웃한 두 수는 항상 서로소라 선공의 승리입니다.<ref>[[최대공약수]]의 성질 중, <math>\gcd\left(a+kb,b\right)=\gcd\left(a,b\right)</math>이 있다. 이를 활용하면, <math>\gcd\left(n+1,n\right)=\gcd\left(\left(n+1\right)-n,n\right)</math><br /><math>=\gcd\left(1,n\right)=1</math></ref>}}
| |
|
| |
| {{인용문2|칠판에 10부터 99까지의 수가 있다. 번갈아 가면서 숫자를 최대 3개까지 지우는 데, 지운 숫자 위에 그 수의 각 자릿수의 합을 적는다. 만약 똑같은 각 자릿수의 합이 3번째 나오면, 그 사람의 패배다. 이 때, 당신의 필승 전략은?}}
| |
| {{숨기기|힌트|가능한 자릿수의 합과 그 개수부터 찾아보세요.}}
| |
| {{숨기기|풀이|선공을 해야 합니다. 가능한 각 자릿수의 합은 1부터 18까지고, 이 중 1과 18은 단 한 번 밖에 나올 수 없습니다. 2부터 17까지는 두 번 이상 나옵니다. 그럼 지울 수 있는 수의 최댓값은 2+2×16<nowiki>=</nowiki>34 입니다. 이제, 당신이 먼저 10과 99를 지웁니다. 그 뒤에 상대방이 1개를 지우면 3개를, 2개를 지우면 2개, 3개를 지우면 1개씩 지워주면 당신의 차례에 34개의 수를 모두 지우게 됩니다. 이 뒤에 상대방이 숫자를 지우면 같은 각 자릿수의 합이 세 번째 등장하고, 상대방의 패배입니다. '''아 물론, 당신이 수를 지울 때 같은 각 자릿수의 합이 세 번 등장하지 않게 지워야 합니다.'''}}
| |
|
| |
|
| === 기타 === | | === 기타 === |
| 어느 문단에도 속하기 애매한 필승 전략 게임들. 윗 문단의 숫자 지우기가 [[정수론]]적 성질을 주로 활용한다면, 이쪽은 그 외 수학 성질들을 활용하는 문제가 많다.
| |
|
| |
| {{인용문2|<math>?x^n+?x^{n-1}+\cdots+?x+?=0</math>이란 방정식이 있다 하자. 번갈아 가면서 ?에 숫자를 하나씩 채워 넣는다 (굳이 실수일 필요는 없다). 모든 ?가 채워졌을 때, 그 방정식에 정수해가 존재하면 선공의 승리, 그렇지 않으면 후공의 승리다. 당신의 필승 전략은?}}
| |
| {{숨기기|힌트|'''짠! 너무 쉬워서 힌트가 필요 없어요!''' <s>아니 이 녀석이 또...</s>}}
| |
| {{숨기기|풀이|상수항이 0이면 x{{=}}0을 무조건 근으로 가집니다. 즉, 마지막 ?를 채우는 사람이 반드시 이기게 되죠. n이 짝수면 ?의 개수가 홀수이므로 선공의 승리, 홀수면 ?가 짝수 개 있으므로 후공의 승리입니다.}}
| |
|
| |
| {{인용문2|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]]: 간단히 설명하면, 모든 노말 공정 게임은 님버와 동등하다는 정리이다.
| |
| * [http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf 공정 게임 이론]
| |
| * [http://www.transience.com.au/pearl3.html 3줄 짜리 님]
| |
| * [http://www.cut-the-knot.org/Games/SuperNim/SNim.shtml 슈퍼 님]
| |
| * [http://www.cut-the-knot.org/Curriculum/Games/Grundy.shtml 그룬디 게임]
| |
|
| |
|
| {{각주}} | | {{각주}} |
| [[분류:수학]] | | [[분류:수학]] |
| [[분류:추상 전략 게임]]
| |
