수학 배틀 보고서
수학 배틀 관리위원회 위원장 뵤도인 코리(平等院公理) 님께.
수학 배틀(제 00010192호)의 결과를 보고드립니다.
수학 배틀 제 00010192호(이하 본 배틀)는 아래와 같이 이루어졌습니다.
일시 : ○○○○년 ○월 ○일, 13시 56분~15시 7분
장소 : ○○대 제 2식당 (도쿄 도 △△구 △△ □□-□)
형식 : 일대일 배틀
제목 : 돌줍기 게임
참가자 : 혼죠 케이스케, 난죠 코코로
승자 : 난죠 코코로
승자 보상 (난죠 코코로) : 혼죠 케이스케의 수학과 학생연합 회원권 및 도쿄 도 수학과 학생연합 회원권 포기
패자 보상 (혼죠 케이스케) : 난죠 코코로의 웃음
이제부터 본 배틀의 개요를 상세히 알려드리고자 합니다.
****************
『돌줍기 게임』
규칙 :
한 경기가 시작되면 번갈아가며 테이블에 놓인 돌을 가져간다. 더 이상 가져갈 수 없는 경우 그 경기의 패자가 된다. 패자가 아닌 사람은 그 경기의 승자가 된다. 더 많은 경기에서 이긴 사람이 본 배틀의 승자가 된다.
조건 :
1. 돌을 한 번 가져갈 때 한 무더기에서만 가져갈 수 있다.
2. 자신의 차례에 최소 한 개 이상의 돌을 가져가야 한다.
3. 돌을 늘리거나 자기 차례에 가져가는 것 외의 방법으로 돌을 줄일 수 없다.
4. 선공은 첫 경기에선 동전으로 정하고, 이후에는 이전 경기의 승자가 후공이 된다.
5. 경기는 총 다섯 번 한다.
세팅 :
1. 본 배틀에서는 지정된 컵을 돌로 사용한다.
2. 돌무더기는 총 네 개로 하며, 각각 돌 다섯, 넷, 셋, 둘을 둔다.
수학 배틀 결과 :
패자 ; 난죠 코코로
승자 ; 혼죠 케이스케 (5회전 기권)
배틀 경위 보고 :
금속제 동전을 하나 위로 던져 그 앞뒷면에 따라 선공 및 후공을 정하는 방법(이하 동전 던지기)을 쓴 결과 난죠 코코로(이하 난죠)가 선공이 되었다. 이 때 동전 던지기에 사용된 동전이 둘로 쪼개졌으나, 선공을 정하는 데 지장을 주지는 않았다고 판단하였다. 조건에 따라 테이블에는 돌 다섯, 넷, 셋, 둘로 이루어진 돌무더기가 배치되었다. (그림 1 참조)
A:◯◯◯◯◯
B:◯◯◯◯
C:◯◯◯
D:◯◯
[그림 1]
선공을 맡은 난죠는 그림 1의 B 무더기에서 돌 네 개를 가져갔다. 이후 후공이었던 혼죠는..................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
...................................................................................................................................................
제 5회전, 선공이던 혼죠는 긴 침묵 후 기권 의사를 표명하였다. 혼죠는 제 4회전에서 가슴에 어떠한 통증을 느끼는 듯한 모습을 보여주었기에, 건강 상의 문제로 인해 내린 결정이라 판단하여 기권 의사를 재차 확인하였다. 그럼에도 혼죠는 기권 의사를 정정하지 않았기에 제 5회전의 승자를 난죠로 정하였다. 이와 동시에 수학 배틀의 승자는 3승 2패를 한 난죠로 확정되었다.
수학적 배경 :
이제부터 본 배틀의 수학적 배경을 설명한다.
본 돌줍기 게임(별칭 NIM게임)은 게임 이론에서 말하는 이른바 공정한 게임(impartial game)으로, 게임의 초기 조건이 정해지면 두 플레이어의 차이가 선공이냐 후공이냐에 따라서만 결정되는 게임이다. 돌줍기 게임을 예로 들겠다.
A:◯◯◯
B:◯◯
와 같이 컵이 배치되어 있고 플레이어 X, Y가 게임을 한다고 하자. 만약 X가 선공이라면 무더기 A나 B에서 원하는 만큼 돌을 가져갈 수 있다. Y가 선공일 때 역시 마찬가지이다. 따라서 "선공과 후공을 뒤바꿔도 게임의 내용이 변하지 않는 대칭적인 게임"이라 할 수 있다. 반면 바둑과 장기는 선공 후공 여부가 바뀌면 움직일 수 있는 말 종류가 달라지므로 대칭적이지 않으며, 따라서 공정한 게임이 아니다. 이러한 게임은 불공정한 게임(partial game)이라고 부른다.
다시 돌줍기 게임으로 돌아가자. 사실 돌줍기 게임은 돌의 배치에 따라 선공 필승이냐 후공 필승이냐가 완전히 결정되는 게임이다. 누가 필승하는 지는 nim sum을 계산하여 알 수 있다. Nim sum이란 두 수를 이진수로 표현한 후 각 자리수마다 배타적 논리합을 하는 연산이다. 예컨대 3⊕2＝(11⊕10)_2＝(１)_2＝1이다. 돌줍기 게임은 각 무더기의 돌 갯수의 nim sum이 0일 때 후공 필승이며, 그렇지 않으면 선공 필승이라는 것이 알려져 있다. 이의 증명은 참고문헌 [1]-[3]을 참조하라. [1]은 돌줍기 게임을 다루는 책 중에선 제일 정석적인 명저이며, [2]는 가장 최근에 출판된 것으로 입문자가 읽기 쉽게 쓰여 있다. [3]은 웹에서 무료로 배포된 강의록이다. 게임 이론에 대해 알고 싶은 독자는 군죠 스즈가 유학생 시절 교과서로 썼던 [4] 등을 참고하라. [4] 역시 돌줍기 게임에 대한 설명을 담고 있다.
참고문헌
[1] 《돌줍기 게임의 수학적 원리》. 히토츠마츠 신, 수학 라이브러리 교양편, 모리키타 출판사, 1968
[2] 《돌줍기 게임의 수학: 게임과 대수의 신기한 연관성》, 사토 후미히로, 수학책방, 2014
[3] 《게임의 전략 - Nim을 알고 계신가요?》, 나이토 히사시, 1999 나고야대 수학 공개강좌, https://www.math.nagoya-u.ac.jp/~naito/lecture/high_school_1999/note.pdf
[4] 《Game Theory, Alive》, Yuval Peres, http://www.stat.berkeley.edu/~peres/gtlect.pdf
이상으로 돌줍기 게임의 수학적 배경에 대한 설명을 마친다. 그러나 난죠에 따르면 본 배틀을 개최한 배경엔 Boolean ring의 예시를 소개하는 것에 있다고 하였으므로 그에 대한 보충 설명을 아래에 기술한다.
Boolean ring이란 모든 원소가 멱등원(제곱하여 자기 자신이 되는 원소)이 되는 환이다. Boolean ring은 무조건 가환 환이 된다. 가장 간단한 Boolean ring은 F_2={0,1}을 들 수 있다. 난죠는 혼죠에게 F_2가 아닌 예시를 구성할 것을 요구하였고, 혼죠는 게임이 끝난 이후 자연수 집합에 nim sum ⊕과 nim product ⊗(nim sum의 배타적 논리합을 AND로 바꾼 것)를 부여하면 Boolean ring이 된다는 것을 알았다. 자연수 집합이 이들 연산 아래 Boolean ring을 이룬다는 것은 임의의 자연수 a,b,c에 대해
1. (a⊕b)⊕c=a⊕(b⊕c)
2. a⊕0=a
3. -a가 존재하여 a⊕(-a)=0
4. a⊕b=b⊕a
5. (a⊗b)⊗c=a⊗(b⊗c)
6. a⊗1=a
7. a⊗(b⊕c)=(a⊗b)⊕(a⊗c)
8. (a⊕b)⊗c=(a⊗c)⊕(b⊗c)
9. a⊗a=a
가 모두 성립한다는 것이다. 본 보고서의 독자에게 연습문제로 남긴다.
난죠는 nim sum과 nim product가 언뜻 부자연스러운 연산으로 보일 수 있으나, 사실 흔히 볼 수 있는 집합 연산과 같다는 점을 언급하였다. 예를 들면, 집합 {a,b,c}에 대해 그 부분집합은 아래처럼 모두 여덟 개이다.
{} (공집합}
{a}
{b}
{c}
{a,b}
{a,c}
{b,c}
{a,b,c}
이제 이들 집합을 이진법으로 세 자리수인 자연수에 대응시키자. a,b,c를 각각 첫 번째, 두 번째, 세 번째 자리수에 대응시키고, a를 포함한 집합은 첫 번째 자리수 1인 수에, 포함하지 않은 집합은 첫 번째 자리수가 0인 수에 대응시킨다. b,c에 대해서도 똑같이 대응시키면, 아래와 같은 대응 관계가 생긴다.
{} ↔ 000
{a}↔ 001
{b} ↔ 010
{c} ↔ 100
{a,b} ↔ 011
{b,c} ↔ 110
{a,c} ↔ 101
{a,b,c} ↔ 111
이제 이들 부분집합을 교집합하자. 가령
{a,b}∩{b,c}={b}
이다. 이제 각 부분집합에 대응되는 수의 nim product를 생각하면
011⊗110=010
인데, 010에 대응되는 집합은 {b}이므로,
{a,b}∩{b,c}={b}
⇅
011⊗110=010
교집합과 nim product가 완전히 같은 연산임을 알 수 있다.
그러면 nim sum은 어떤 연산에 대응되는가. 바로 대칭차집합 △이다. 대칭차집합이란 두 집합의 합집합에서 교집합을 뺀 것이다. 예컨대
{a,b}△{b,c}=({a,b}∪{b,c})-({a,b}∩{a,c})={a,b,c}-{b}={a,c}
이다. 한편 이에 대응되는 nim sum을 생각하면
011⊕110=101
이며 101은 {a,c}에 대응되므로, 대칭차집합과 nim sum이 같은 연산임을 알 수 있다.
일반적인 n자리 이진수는 n개의 원소를 포함한 집합의 부분집합과 일대일 대응된다. 따라서 이진수 전체의 집합은 자연수의 유한 부분집합과 일대일 대응된다. 고로 자연수에 nim sum과 nim product을 부여해 만든 Boolean ring은 자연수 집합의 유한부분집합들을 모두 모은 집합에 대칭차집합과 교집합을 준 환과 동형이다.
이제 임의의 집합의 부분집합을 잘 모아 이들 부분집합의 모임에 대칭차집합과 교집합을 주면 Boolean ring이 됨에 주목하자. 따라서 우리는 원하는 만큼 Boolean ring을 만들 수 있다. 사실 난죠가 언급한 Stone's representation theorem에 따르면 모든 Boolean ring은 이 방법으로 만든 것밖에 없다.
마지막으로 Boolean Gröbner basis에 대해 기술한다. 난죠가 Boolean ring에 대해 말을 꺼내게 된 계기는, 앞서 혼죠와 군죠가 이야기하고 있던 '거짓말쟁이 문제*' (*별지 참조)였다. 군죠는 F_2 위의 다항식환 F_2[x1,x2,x3,…,xn] 상의 연립방정식을 거짓말쟁이 문제에 대응시키는 방법을 제안하였다. 연립방정식을 그뢰브너에 기저에 대응시키는 과정에서 x^2+1=0같은 다항식이 나타날 가능성이 있으나, x에 들어가는 값은 0과 1밖에 없기에 x^2을 x로 바꾸어도 무방하다. 따라서 F_2에서는
x^2+1=0 ⇔ x+1=0
이 성립한다. 방금 x^2를 예로 들었지만, 사실 x^1000000이 나와도 다를 것은 없다.
x^1000000+1=0 ⇔ x+1=0
F_2[x,y]/(x^2-x, y^2-y)
를 생각할 수 있다. 환이 친숙하지 않으면 x^2를 x와, y^2를 y와 동일시하는 규칙을 도입한다고 생각하여도 무방하다. 이렇게 만든 환은 boolean ring이 된다. 예컨대 다항식 x+y의 제곱을 계산해보면,
(x+y)^2=(x+y)(x+y)=x^2+2xy+y^2=x+0*xy+y=x+y
이다. (F_2에서는 2=0임에 유념하라) 따라서 F_2[x,y]/(x^2-x, y^2-y)에서는 변수의 차수가 2 이상이 될 수 없으므로 작은 차수만으로 다항식을 표현할 수 있다. 이 환을 Boolean polynomial ring이라고 부르자. 이 polynomial ring 위의 그뢰브너 기저가 바로 Boolean Gröbner basis다. (일반적으로 boolean ring B에 대해 B[x1,…,xn]/(x1^2-x1,…,xn^2-xn) 위의 그뢰브너 기저를 Boolean Gröbner basis라고 부른다)
요컨대 난죠의 주장은 다음과 같다.
거짓말쟁이 문제→연립방정식 in 평범한 다항식 → 그뢰브너 기저
⇦ 차수가 너무 커지는데?
거짓말쟁이 문제→연립방정식 in Boolean polynomial ring → Boolean Gröbner basis
⇦ 차수가 커지지 않는다!
하지만 계산이 얼마나 빨라질 지는 실제로 계산기 실험을 하기 전까지는 알 수 없을 것이다.
아래에는 Boolean Gröbner basis에 관한 참고문헌 [5], [6]을 소개한다.
그 외에도 [7]에서는 Boolean Gröbner basis를 스도쿠의 해법에 응용하고 있다.
[5] 《Boolean Gröbner bases》, Yosuke Sato，Shutaro Inoue，Akira Suzuki，Katsusuke Nabeshima，Ko Sakai，Journal of Symbolic Computation，2011， http://www.sciencedirect.com/science/article/pii/S074771711000180X
[6] 《Boolean Gröbner basis를 응용한 집합 제약 조건의 개선》, 이노우에 히데타로, 수리해석연구소 강구록,
http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1907-13.pdf
[7]《Boolean Gröbner basis를 이용한 스도쿠의 해법》 이노우에 히데타로 외, 수리해석연구소 강구록, http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1666-01.pdf
이상으로 본 배틀의 보고를 마친다.
◯◯◯◯년 ◯월 ◯일
보고자 : 뵤도인 메다이
역자 주 :
레퍼런스를 적을 때는 서지 사항을 원어 그대로 작성해야 하지만, 여기 있는 레퍼런스는 인용을 위함이 아닌 소설을 위한 장치이므로 서지 사항을 번역하였다. 실제로 참고 문헌을 참고하고 싶다면 아래 목록을 참고하기 바란다.
[1]「石とりゲームの数理」一松信，数学ライブラリー 教養篇，森北出版社，1968
[2]「石とりゲームの数学:ゲームと代数の不思議な関係」佐藤文広，数学書房，2014
[3]「ゲームの戦略– Nim って知ってますか？ –」内藤 久資，１９９９年度名古屋大学数学公開講座，https://www.math.nagoya-u.ac.jp/~naito/lecture/high_school_1999/note.pdf
[4]「Game Theory, Alive」Yuval Peres，http://www.stat.berkeley.edu/~peres/gtlect.pdf
[5]「Boolean Gröbner bases」Yosuke Sato，Shutaro Inoue，Akira Suzuki，Katsusuke Nabeshima，Ko Sakai，Journal of Symbolic Computation，2011， http://www.sciencedirect.com/science/article/pii/S074771711000180X
[6]「ブーリアングレブナ基底を使用した集合制約解法の改良」井上秀太郎，数理解析研究所講究録，http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1907-13.pdf
[7]「ブーリアングレブナ基底を使った数独の解法」井上秀太郎他，数理解析研究所講究録，http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1666-01.pdf