게임을 너무 진지하게 분석하면 생기는 일
가벼운 보드·카드 게임도 진지하게 파고들면 순열의 패리티부터 위상수학의 고정점 정리, 추상대수의 노터성까지 온갖 깊은 수학이 튀어나옵니다. 열두 게임을 직접 만져보며 확인해 보세요.
8×8 체스판에서 대각선 반대편 두 모서리 칸을 떼어낸 62칸을, 1×2 도미노 31개로 빈틈없이 덮을 수 있을까요? 직접 해보면 늘 한두 칸이 남아 막힙니다. 이유는 한 줄이면 끝나죠 — 색칠입니다.
체스판을 흑·백으로 칠하면 도미노 하나는 반드시 검정 1칸 + 흰색 1칸을 덮습니다. 그런데 대각선 두 모서리는 같은 색이라, 그 둘을 떼면 두 색의 칸 수가 30 대 32로 어긋납니다. 31개의 도미노는 검정 31·흰색 31을 요구하는데 \(30 \ne 31\) — 그래서 절대 못 덮습니다.
이 색칠 패리티는 바로 다음 장 15 퍼즐에서 빈칸이 흑·백을 번갈아 밟는 논증과 똑같은 무기입니다. 같은 칼로 다른 퍼즐을 벱니다.
4×4 칸에 1~15 타일과 빈칸 하나. 빈칸 옆 타일을 밀어 1부터 차례로 맞추는 고전 퍼즐입니다. 그런데 1879년 퍼즐 거장 샘 로이드는 14와 15만 뒤바뀐 배치를 내놓고 상금을 걸었습니다. 아무도 못 받았죠 — 그 배치는 풀이가 존재하지 않기 때문입니다. 왜인지 두 단계로 따져봅시다.
순열을 두 줄로 그려 봅시다. 위에는 \(1,2,\dots,n\)을 순서대로 놓고, 아래에는 섞인 순열을 놓은 뒤 같은 숫자끼리 선으로 잇습니다. 이때 생기는 교점의 개수가 바로 역위(inversion) 수 — 순서가 뒤집힌 쌍의 개수입니다. 핵심은 이것: 두 자리를 한 번 맞바꿀 때마다 교점 수의 홀짝이 반드시 뒤집힙니다. 그래서 이 "홀짝"은 순열에 붙는 부호 \(\mathrm{sgn} = (-1)^{\text{역위 수}}\)가 되고, 한 번의 교환(transposition)은 짝순열 ↔ 홀순열을 토글합니다. 직접 바꿔 보세요.
이제 15 퍼즐. 타일을 한 칸 미는 것은 빈칸과 이웃 타일의 자리를 맞바꾸는 교환 한 번입니다. 16칸을 체스판처럼 흑·백으로 칠해 보면, 빈칸은 한 번 움직일 때마다 반대 색 칸으로 옮겨갑니다(이웃 칸은 늘 반대 색이니까요).
풀린 상태에서 빈칸은 오른쪽 아래 제자리에 있어야 합니다. 14·15만 바꾼 배치에서도 빈칸은 이미 제자리에 있죠. 그러니 빈칸을 같은 색인 제자리로 되돌리려면 움직인 횟수가 반드시 짝수여야 합니다(색이 매번 바뀌니까). 움직임 하나가 교환 하나이므로, 풀이는 짝수 번의 교환 = 짝순열 이어야 합니다.
그런데 14·15를 맞바꾼 처음 배치는 교환 딱 한 번 = 홀순열입니다. 짝순열이어야 하는데 홀순열이라니 — 모순. 그래서 이 배치는 무슨 짓을 해도 풀리지 않습니다.
카드에는 네 속성이 있고(개수·색·모양·채움) 각 속성은 세 값을 가져, 카드는 \(3^4=81\)장. 세 장이 각 속성마다 모두 같거나 모두 다르면 "SET"입니다. 12장 중에서 SET을 찾아 외쳐 보세요.
속성을 \(0,1,2\)로 적으면 SET 조건은 깔끔합니다 — 각 속성마다 세 값의 합이 3의 배수. 그리고 카드 한 장 = \(\mathrm{AG}(4,3)\)(\(\mathbb F_3\) 위 4차원 공간)의 점, SET = 직선이죠.
$$ \text{SET} \iff \text{네 속성 모두 } (x_1+x_2+x_3)\equiv 0 \pmod 3 $$그러면 SET이 하나도 없도록 늘어놓을 수 있는 최대 카드 수는? 20장입니다(21장이면 반드시 SET이 생깁니다). 이는 직선을 품지 않는 최대 점집합 — 캡(cap)의 크기입니다.
증명은 작은 차원부터 쌓아 올립니다. 속성이 적은 경우는 모든 배치를 컴퓨터로 다 세어 정확히 확인됩니다.
| 속성 수 \(n\) | 카드 수 \(3^n\) | SET 없는 최대 |
|---|---|---|
| 2 | 9 | 4 |
| 3 (기본 SET) | 27 | 9 |
| 4 (실제 SET) | 81 | 20 |
핵심 도구는 평행한 평면으로 쪼개기입니다. 81장을 마지막 속성값(0·1·2)으로 갈라 세 덩어리로 나누면, 각 덩어리는 "속성 3개짜리 공간"(27장, 최대 9캡)이 됩니다. 그러니 순진하게는 \(9+9+9=27\)이 한계처럼 보이죠.
그런데 세 덩어리에 걸쳐 있는 SET — 각 덩어리에서 한 장씩 뽑은 세 장이 한 직선을 이루는 경우 — 이 발목을 잡습니다. 덩어리 0의 카드 \(P_0\)와 덩어리 1의 카드 \(P_1\)을 고르면 셋째 점 \(P_2 = -(P_0+P_1)\)은 덩어리 2에 자동으로 정해지고, SET을 피하려면 그 \(P_2\)가 우리 손에 없어야 합니다. 이 제약을 모두 따지면 세 덩어리를 9·9·9로 채우는 것은 불가능하고, 가능한 진짜 최댓값이 정확히 20으로 떨어집니다. 1971년 주세페 펠레그리노가 이 경우 분석을 완성했죠.
차원을 더 올린 캡 세트(cap set) 문제는 2016년 엘런버그–히스베이트가 다항식 방법으로 상한 \(O(2.756^n)\)을 증명하며 돌파한 현대 조합론의 이정표입니다.
Chomp은 과자 격자를 번갈아 베어 먹는 게임입니다. 한 칸을 고르면 그 칸과 위·오른쪽 칸이 모두 사라지고, 왼쪽 아래 독 칸을 먹는 사람이 집니다. 유한 보드는 당연히 끝나지만, 무한 보드라면 영원히 이어질 수도 있지 않을까요? 놀랍게도 아니오 — 그리고 그 보장이 힐베르트 기저 정리에서 나옵니다.
먹힌 영역은 항상 위·오른쪽으로 닫힌 영역(상집합)이고, 칸 \((i,j)\)를 단항식 \(x^i y^j\)에 대응시키면 이는 단항식 아이디얼입니다. 한 수마다 이 아이디얼이 커지는 오름 사슬 \(I_0\subsetneq I_1\subsetneq\cdots\) 이 생기죠.
헥스는 마름모꼴 육각 격자에서 두 사람이 번갈아 돌을 놓아, 빨강은 위–아래를, 파랑은 좌–우를 끊김 없이 잇는 쪽이 이기는 게임입니다.
헥스의 가장 신기한 성질은 무승부가 절대 없다는 것입니다. 보드가 꽉 차면 둘 중 한 색은 반드시 자기 양변을 잇습니다(게다가 둘이 동시에 잇는 일도 없습니다). 이 사실을 헥스 정리라 부르는데, 겉보기엔 게임 규칙이지만 속은 평면의 연결성에 관한 깊은 위상수학입니다. (참고로 헥스는 1번 플레이어 필승이기도 하지만, 그 전략은 일반적으로 알려져 있지 않습니다.)
브라우어 고정점 정리(2차원)는 이렇게 말합니다 — 정사각형(또는 원판)을 자기 자신으로 보내는 어떤 연속 함수 \(f\)에도 \(f(x)=x\)인 점(고정점)이 반드시 있다. 동치인 형태로는, 원판을 그 경계로 빈틈없이 밀어내는(연속 수축, retraction) 방법은 없다는 것이죠. 1979년 데이비드 게일은 "헥스에 무승부가 없다"는 정리가 바로 이 2차원 브라우어 정리와 정확히 동치임을 증명했습니다.
직관은 이렇습니다. \(f\)에 고정점이 없다고 가정해 봅시다. 그러면 모든 점에서 변위 \(f(x)-x\)가 0이 아니므로 "밀려나는 방향"이 정해집니다. 그 방향에 따라 보드의 칸을 두 색으로 칠하면 — 놀랍게도 헥스 한 판이 그려집니다. 그런데 헥스 정리는 "어느 한 색이 반드시 양변을 가로질러 잇는다"고 보장하죠. 그 가로지르는 사슬을 따라가 보면 밀려나는 방향이 서로 양립할 수 없는 지점에 갇히고 맙니다 — 거기선 변위가 0, 즉 고정점일 수밖에 없습니다. "고정점이 없다"는 가정이 깨지는 거죠. 거꾸로 브라우어 정리에서 "헥스는 비길 수 없다"를 끌어낼 수도 있어, 둘은 같은 이야기의 두 얼굴입니다.
요약하면 — 평면을 두 색으로 칠하면 어느 한 색이 반드시 반대편까지 이어진다는 헥스의 연결성 사실이, 연속성의 세계에서 고정점은 피할 수 없다는 브라우어 정리의 이산(조합론) 심장인 셈입니다.
님은 여러 더미의 돌을 번갈아 가져가는 게임입니다(한 번에 한 더미에서 원하는 만큼). 마지막 돌을 가져가는 사람이 이깁니다. 완벽한 전략은 충격적으로 단순한데, 각 더미 크기를 2진법으로 XOR한 값(님-합)을 0으로 만들어 넘기면 반드시 이깁니다.
더 놀라운 건 스프라그–그런디 정리입니다. 모든 공정 게임(impartial game)은 적당한 크기의 님 더미 하나와 완전히 똑같다는 것 — 게임마다 "그런디 수"가 붙고, 여러 게임의 합은 그 수들의 XOR로 분석됩니다. 님 하나가 공정 게임 전체의 보편 언어인 셈이죠.
돌 두 더미. 한 수에 ① 한 더미에서 원하는 만큼 가져가거나, ② 두 더미에서 똑같은 수만큼 가져갑니다. 마지막 돌을 가져가면 승리. 님과 닮았지만 "양쪽 동시" 수가 더해졌죠.
이 게임의 지는 자리(P-위치)를 작은 것부터 적으면 \((0,0),(1,2),(3,5),(4,7),(6,10),\dots\) 인데, \(n\)번째가 \((\lfloor n\varphi\rfloor,\ \lfloor n\varphi^2\rfloor)\) — 황금비 \(\varphi=\frac{1+\sqrt5}{2}\)가 튀어나옵니다. 두 수열이 자연수를 정확히 한 번씩 나눠 갖는 비티(Beatty) 수열이죠.
점 잇기(Dots and Boxes)는 점 격자에서 번갈아 선을 하나씩 긋고, 네 변을 완성하면 그 칸을 먹고 한 번 더 두는 게임입니다. 많이 먹는 사람이 이기죠. 규칙은 초등학생도 알지만, 그 전략은 엘윈 벌리캠프가 평생 파고든 깊은 조합 게임 이론입니다.
고수의 비밀은 "사슬(chain)"의 패리티 조절과 더블 크로스 기법 — 마지막 두 칸을 일부러 안 먹고 상대에게 떠넘겨 주도권을 쥡니다. 게임의 가치는 결국 님버(Sprague–Grundy 수)로 분석됩니다(앞 장의 님이 여기서 다시 등장하죠).
Lights Out은 5×5 전구판입니다. 한 칸을 누르면 그 칸과 상하좌우 칸의 불이 토글되고, 목표는 모든 불을 끄는 것. 같은 칸을 두 번 누르면 효과가 사라지고, 누르는 순서도 결과에 영향을 주지 않습니다.
그래서 이 퍼즐은 사실 \(\mathbb F_2\)(0과 1만 있는 체) 위의 선형대수 문제입니다. "각 칸을 누를까 말까"를 미지수로 두면 \(25\)개 방정식의 1차 연립방정식이 되고, 풀 수 있는지·해가 몇 개인지는 행렬의 계수(rank)로 정해집니다. "불을 차례로 밀어 끄는" 라이트 체이싱 기법도 사실은 이 가우스 소거법이죠.
페그 솔리테어는 십자 모양 33칸 판에서, 한 말로 이웃 말을 직선으로 뛰어넘어 잡는(잡힌 말 제거) 게임입니다. 가운데만 비운 채 시작해 마지막 한 말을 가운데에 남기면 성공이죠.
Lights Out처럼 이 퍼즐에도 불변량이 숨어 있습니다. 각 칸에 \(\mathbb Z_2\times\mathbb Z_2\)의 원소를 영리하게 배정하면 점프가 그 "자원"을 보존해서, 애초에 마지막 말이 놓일 수 없는 칸을 증명할 수 있습니다. 색칠·패리티 논법의 한 차원 위 버전이죠.
콘웨이의 병사: 가로선 아래에 말을 놓고, 페그 솔리테어처럼 이웃 말을 뛰어넘어 잡으며 말을 선 위로 전진시킵니다. 선 위 1·2·3·4번째 줄까지는 (충분한 말이 있으면) 도달할 수 있습니다. 그런데 5번째 줄은 — 무한히 많은 말을 동원해도 절대 도달할 수 없습니다.
증명이 일품입니다. 목표 칸에 1을 주고, 거리가 1칸 멀어질 때마다 가중치를 \(\sigma=1/\varphi\)배 (\(\varphi\)는 황금비)로 줄여 칸마다 포텐셜을 매깁니다. \(\sigma^2+\sigma=1\)이라 점프는 포텐셜을 절대 늘리지 못하고, 선 아래 전체를 다 합쳐도 5번째 줄 목표 칸의 값에 못 미칩니다. 여기서도 황금비가 결정적이죠.
하노이 탑: 기둥 셋에 크기순으로 쌓인 원반들을, 한 번에 하나씩, 큰 원반을 작은 원반 위에 올리지 않으면서 통째로 옮깁니다. 원반이 \(n\)개면 최소 \(2^n-1\)수가 필요하죠.
이유는 재귀입니다. \(n\)개를 옮기려면 위 \(n-1\)개를 옮기고, 가장 큰 원반을 옮기고, 다시 \(n-1\)개를 얹으니 \(H_n = 2H_{n-1}+1 \Rightarrow H_n = 2^n-1\). 더 놀라운 건, 최적 풀이에서 매 수의 원반 번호가 그레이 코드를 따르고, 가능한 모든 배치를 이으면 시에르핀스키 삼각형이 나타난다는 점입니다.
보드 게임에서 수학을 추구하면 안 되는 걸까요? 천만에요. 다만 타일을 미는 일이 순열의 패리티로, 과자를 베는 일이 추상대수로, 돌을 잇는 일이 고정점 정리로 답해질 뿐입니다. 게임은 더 깊고, 더 이상하고, 더 아름다워집니다.