편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
1번째 줄: | 1번째 줄: | ||
{{추천 문서}} | {{추천 문서|2015년 10월}} | ||
'''필승 전략 게임'''은 어느 한 쪽이 반드시 이길 수 있는 전략을 가진 [[게임]]을 말한다. | '''필승 전략 게임'''은 어느 한 쪽이 반드시 이길 수 있는 전략을 가진 [[게임]]을 말한다. | ||
13번째 줄: | 13번째 줄: | ||
가장 대표적인 유형으로, 개요에서 예시로 들은 배스킨 라빈스 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> 유럽의 선술집에서 하던 성냥개비 게임에서 왔다는 설 등이 있다. 어느 쪽이든 확실한 증거는 없다. {{ㅊ|그럼 도대체 뭐야 이 게임}} | ||
기본적인 룰은 | 기본적인 룰은 여러개의 돌 더미 중 하나를 골라 그 더미 안의 돌을 가져가는 것이며, 가장 마지막 돌을 가져가는 사람이 지는 게임이다. 규칙에 따라서는 마지막 돌을 가져가는 사람이 이기게 만들 수도 있으며, 수학적인 필승 전략과 그 원리는 동일하다. 아래 내용은 특별한 말이 없는한 마지막 돌을 가져가는 사람이 패배하는 규칙을 따른다. | ||
==== 한 더미 ==== | ==== 한 더미 ==== | ||
64번째 줄: | 64번째 줄: | ||
{|width=250 | {|width=250 | ||
|- | |- | ||
|rowspan="4"|<br /><br /><math>\oplus</math><br />= | |rowspan="4"|<br/><br/><math>\oplus</math><br/>= | ||
|001||001||001||000 | |001||001||001||000 | ||
|- | |- | ||
83번째 줄: | 83번째 줄: | ||
==== 증명<ref>Bouton, C. L. (1901–1902), "Nim, a game with a complete mathematical theory", Annals of Mathematics 3 (14): 35–39을 참조.</ref> ==== | ==== 증명<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>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> | :<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>으로 만들 수 있는 수가 존재한다.}} | {{인용문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=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>이다. | #이제 <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>이다. | ||
103번째 줄: | 103번째 줄: | ||
위키백과에서는 님 게임의 일종으로 보고 있지만, 실제로 해보면 님 게임과는 이질적이다. 기본적인 규칙은 아래와 같다. | 위키백과에서는 님 게임의 일종으로 보고 있지만, 실제로 해보면 님 게임과는 이질적이다. 기본적인 규칙은 아래와 같다. | ||
#숫자 하나가 있다. 예로 10이 있다 하자. | #숫자 하나가 있다. 예로 10이 있다 하자. | ||
#번갈아가면서 숫자를 두 개의 '''다른''' 숫자로 쪼갠다. 즉, 10→7, 3은 되지만, 10→5, 5는 | #번갈아가면서 숫자를 두 개의 '''다른''' 숫자로 쪼갠다. 즉, 10→7, 3은 되지만, 10→5, 5는 안된다. | ||
#자기 차례에 더이상 쪼갤 숫자가 없다면 패배. 즉, 모든 숫자가 1 또는 2면 진다. | #자기 차례에 더이상 쪼갤 숫자가 없다면 패배. 즉, 모든 숫자가 1 또는 2면 진다. | ||
이 게임의 필승 전략은 [[Wikipedia:Sprague-Grundy theorem|스프라그-그룬디 정리]]를 응용하여 해결할 수 있다. 영포자나 수포자를 위해 아주 정말 단순하게 결과만을 설명하자면, 각 숫자에는 수학적으로 계산된 님 더미 숫자(nim heap size, 님 값)가 있는데, 수를 쪼갠 뒤의 님 합이 0이 되도록 해주면 이긴다. 참고로 위 에서는 님 합이 2진법에서만 정의된다 하였는데, 그룬디 게임에선 10진법의 님 합을 정의해야 한다. 그룬디 게임에서의 님 합의 정의는 다음과 같다. | 이 게임의 필승 전략은 [[Wikipedia:Sprague-Grundy theorem|스프라그-그룬디 정리]]를 응용하여 해결할 수 있다. 영포자나 수포자를 위해 아주 정말 단순하게 결과만을 설명하자면, 각 숫자에는 수학적으로 계산된 님 더미 숫자(nim heap size, 님 값)가 있는데, 수를 쪼갠 뒤의 님 합이 0이 되도록 해주면 이긴다. 참고로 위 에서는 님 합이 2진법에서만 정의된다 하였는데, 그룬디 게임에선 10진법의 님 합을 정의해야 한다. 그룬디 게임에서의 님 합의 정의는 다음과 같다. | ||
128번째 줄: | 128번째 줄: | ||
=== 숫자 지우기 === | === 숫자 지우기 === | ||
여러개의 숫자가 있고, 번갈아 가면서 숫자를 지울 때, 최후에 남은 숫자 하나, 혹은 둘의 규칙성에 따라 승패가 결정되는 게임. 경우에 따라서는 숫자를 지운 뒤 규칙에 따라 새로운 숫자를 쓰는 경우도 있다. 위의 님 게임과 그룬디 게임이 대학 이상에서나 볼 수 있다면, 이쪽은 [[수학 경시대회]]에 자주 출몰하는 유형. 중, 고등학생을 대상으로 하는 문제이기 때문에 복잡한 수학이론 보다는 간단한 수학적 사실을 활용하는 문제가 많다. 또한, 문제가 하나 같이 다 "칠판에 x개의 수, 1, 2, …, x가 있습니다. 갑과 을이 번갈아…"로 시작한다는 것도 특징이라면 특징. 사실 이 유형은 만들려면 한 없이 많이 만들 수 있다. | |||
{{인용문2|칠판에 1부터 n까지의 자연수가 있다. 번갈아 가면서 두 수를 골라 지우고, 칠판에 두 수의 합, 또는 차를 새로 적는다. 최후에 남은 숫자가 짝수면 선공의 승리, 홀수면 후공의 승리일 때, 당신의 필승 전략은?}} | {{인용문2|칠판에 1부터 n까지의 자연수가 있다. 번갈아 가면서 두 수를 골라 지우고, 칠판에 두 수의 합, 또는 차를 새로 적는다. 최후에 남은 숫자가 짝수면 선공의 승리, 홀수면 후공의 승리일 때, 당신의 필승 전략은?}} | ||
140번째 줄: | 140번째 줄: | ||
{{인용문2|칠판에 2부터 1000까지의 자연수가 있다. 번갈아 가면서 숫자 하나를 지우는데, 최후에 남은 두 수가 [[서로소]]이면 선공의 승리, 아니면 후공의 승리다. 이 때, 당신의 필승 전략은?}} | {{인용문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를 지웁니다. 이제, 상대방이 홀수를 지우면 그 뒤의 수를, 짝수를 지우면 그 앞의 수를 지우면 최후에는 이웃한 두 수만이 남고, 이웃한 두 수는 항상 서로소라 선공의 승리입니다.<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번째 나오면, 그 사람의 패배다. 이 때, 당신의 필승 전략은?}} | {{인용문2|칠판에 10부터 99까지의 수가 있다. 번갈아 가면서 숫자를 최대 3개까지 지우는 데, 지운 숫자 위에 그 수의 각 자릿수의 합을 적는다. 만약 똑같은 각 자릿수의 합이 3번째 나오면, 그 사람의 패배다. 이 때, 당신의 필승 전략은?}} | ||
160번째 줄: | 160번째 줄: | ||
*[[조합론적 게임 이론]] (Combinatorial game theory): 완전한 정보를 가진 턴제 게임에 대해 수학적으로 연구하는 학문. 불완전한 정보를 가진 게임에 대해 연구하는 학문은 [[게임 이론]] 참조. | *[[조합론적 게임 이론]] (Combinatorial game theory): 완전한 정보를 가진 턴제 게임에 대해 수학적으로 연구하는 학문. 불완전한 정보를 가진 게임에 대해 연구하는 학문은 [[게임 이론]] 참조. | ||
*완전한 정보 (Perfect information): 조합론적 게임 이론에선, 수를 두기 위한 '''모든''' 정보를 알고 있는 것을 말한다. | *완전한 정보 (Perfect information): 조합론적 게임 이론에선, 수를 두기 위한 '''모든''' 정보를 알고 있는 것을 말한다. | ||
*공정 게임 (Impartial game): 수를 둘 때, 선공인지 후공인지에만 영향을 받고, 그 외의 모든 규칙이나 요인과는 관계가 없는 게임. 다르게 말하면, 선공과 후공의 차이는 먼저 하냐 나중에 하냐, 그것 뿐인 게임을 말한다. 예를 들면, 선공에 여러 가지 제한이 붙는 [[오목]]은 공정 게임이 아니며, 자신의 말만 움직일 수 있는 [[바둑]]이나 [[체스]] 역시 공정 게임이 아니다. 반면, NIM 게임은 공정 게임이다. {{ㅊ|필승 전략이 있는데???}} | *공정 게임 (Impartial game): 수를 둘 때, 선공인지 후공인지에만 영향을 받고, 그 외의 모든 규칙이나 요인과는 관계가 없는 게임. 다르게 말하면, 선공과 후공의 차이는 먼저 하냐 나중에 하냐, 그것 뿐인 게임을 말한다. 예를 들면, 선공에 여러 가지 제한이 붙는 [[오목]]은 공정 게임이 아니며, 자신의 말만 움직일 수 있는 [[바둑]]이나 [[체스]] 역시 공정 게임이 아니다. 반면, NIM 게임은 공정 게임이다. {{ㅊ|필승 전략이 있는데???}} | ||
*편파 게임 (Partisan game): 공정 게임이 아닌 게임. 대부분의 게임이 이 분류에 속한다. | *편파 게임 (Partisan game): 공정 게임이 아닌 게임. 대부분의 게임이 이 분류에 속한다. | ||
*노말 게임 (Normal game): 최후의 수를 두는 사람이 이기는 게임. 즉, 자기 차례에 할 게 없으면 진다. | *노말 게임 (Normal game): 최후의 수를 두는 사람이 이기는 게임. 즉, 자기 차례에 할 게 없으면 진다. | ||
*미저 게임 (Misère game): 노말 게임의 반대로, 지는 것이 이기는 게임. {{ㅊ|모순}} 다르게 표현하면, 최후의 수를 두는 사람이 지는 게임이다. | *미저 게임 (Misère game): 노말 게임의 반대로, 지는 것이 이기는 게임. {{ㅊ|모순}} 다르게 표현하면, 최후의 수를 두는 사람이 지는 게임이다. | ||
*님 (Nim): 원래는 님 게임만을 가르키지만, 게임의 특성 때문에 필승 전략이 있는 게임을 NIM이라 부르기도 한다. | *님 (Nim): 원래는 님 게임만을 가르키지만, 게임의 특성 때문에 필승 전략이 있는 게임을 NIM이라 부르기도 한다. | ||
*님 힙 (Nim-heap): 님 게임에서, 특정 값들의 묶음을 말한다. | *님 힙 (Nim-heap): 님 게임에서, 특정 값들의 묶음을 말한다. |