Invariants: what stays put while everything moves.
규칙에 따라 상태가 마구 바뀌는 게임이 있습니다. "이 상태에서 저 상태로 갈 수 있나?"를 일일이 시도해 보는 건 끝이 없죠. 그런데 — 어떤 조작을 해도 절대 변하지 않는 양(불변량) 하나만 찾으면, 시작과 목표의 그 값이 다른 순간 "불가능"이 단번에 증명됩니다. 무한 체스판의 돌 옮기기부터, IMO 쇼트리스트, 그리고 역대 최악으로 불리는 입시 문제까지 — 불변량 하나로 관통해 봅니다.
발상은 한 줄입니다. 규칙대로 상태가 아무리 바뀌어도 절대 안 변하는 양을 하나 찾아라. 그러면 시작과 목표에서 그 값이 다른 순간, "둘은 못 잇는다"가 — 시도 한 번 없이 — 증명됩니다.
가장 유명한 예가 잘린 체스판(마주 보는 두 모서리를 떼면 도미노로 못 덮음 — 색칠 불변량)인데, 이건 보드 게임 페이지에서 직접 칸을 떼어 보며 확인할 수 있으니 여기선 넘어갈게요. 더 가벼운 한 입만 맛보면 — \(m\times n\) 초콜릿 바를 조각으로 다 쪼개는 데 필요한 쪼개기 횟수는, 어떤 순서로 부수든 늘 \(mn-1\)입니다(한 번 쪼갤 때마다 조각 수가 정확히 \(1\)씩 늘어나는 게 불변량이거든요). "전략"을 고민할 필요가 아예 없죠.
핵심은 늘 같습니다 — 조작이 보존하는 양을 찾고, 시작과 목표에서 그 값을 비교한다. 이제 이 무기를 훨씬 사나운 문제들에 휘둘러 봅시다(겹치지 않게, 게임 페이지의 15 퍼즐·님·페그 솔리테어와는 다른 결로).
무한 격자 위에 돌을 \(n\times n\) 정사각형으로 빈틈없이 깔아 둡니다. 허용된 동작은 펙 솔리테어(말판 뛰기) — 한 돌이 바로 옆 돌을 뛰어넘어 그 너머 빈칸에 내려앉고, 뛰어넘긴 돌은 사라집니다(가로·세로만). 기호로 적으면 세 칸이 ●●□ → □□●로 바뀌는 거죠.
비밀 병기는 칸마다 \(3,5,7\)을 \((i{+}j)\bmod 3\)에 따라 번갈아 적는 것입니다(아래 패턴이 무한히 반복):
3 5 7
5 7 3
7 3 5
가로든 세로든 연속한 세 칸은 늘 \(\{3,5,7\}\) 한 벌이라, 그 곱은 \(3\cdot5\cdot7=105\equiv1\pmod8\). 한편 \((\mathbb Z/8)^\times=\{1,3,5,7\}\)에선 모든 원소가 제 자신이 역원(\(3^2,5^2,7^2\equiv1\)).
동작 \(\,a,b\) 자리에 돌, \(c\) 빈칸 \(\to\) \(a,b\) 비고 \(c\)에 돌. 돌이 놓인 칸의 값들의 곱은 \(\dfrac{v_c}{v_a v_b}=v_a v_b v_c=105\equiv1\)배가 됩니다 — 즉 곱은 안 변해요(가로·세로 모두).
시작이 \(n=3k\) 정사각형이면, 각 줄이 \(\{3,5,7\}\)을 \(k\)벌씩 가져 곱 \(\equiv105^k\equiv1\), 전체도 \(\equiv1\pmod8\). 그런데 돌 한 개만 남으면 그 칸 값은 \(3,5,7\) 중 하나라 결코 \(1\)이 아닙니다. 모순 — \(3\mid n\)이면 한 개로 못 줄입니다. \(\blacksquare\)
아래에서 직접 뛰어 보세요. 무슨 짓을 해도 곱 mod 8이 꿈쩍 않는 걸, 그리고 \(3\times3\)에선 한 개에 영영 닿지 못하는 걸 확인할 수 있습니다.
이번엔 한 줄로 놓인 동전들. 각 동전은 한 면이 흰색, 한 면이 검은색이고, 처음엔 \(n\)개가 모두 흰 면이 위입니다. 동작은: 양 끝이 아닌 흰 면 동전 하나를 골라 치우고, 그 좌우의 가장 가까운 동전을 각각 뒤집습니다. 목표는 동전을 2개만 남기는 것.
비가환군 \(S_3\)(세 원소의 대칭군)가 모든 걸 기억합니다. 흰 면엔 \(x=(1\,2\,3)\), 검은 면엔 \(y=(1\,2)\)를 붙이고, 줄을 왼쪽부터 차례로 곱한 순열 \(P\)를 보죠.
동작은 부분열 "\(\ell\ x\ r\)"(가운데가 흰 면)를 "\(\ell'\ r'\)"로 바꿉니다(\(\ell',r'\)은 \(\ell,r\)을 뒤집은 것, 즉 \(x\leftrightarrow y\)). 네 경우(\(\ell,r\in\{\)흰,검\(\}\))를 모두 따져 보면 \(S_3\)에서 \(P(\ell)\,x\,P(r)=P(\ell')\,P(r')\) — 곱 \(P\)는 안 변합니다.
처음 전부 흰 \(n\)개의 곱은 \(P=x^n\). \(x=(1\,2\,3)\)는 위수 3이라 \(x^n\)은 \(n\bmod3\)에 따라 \(x,\,x^2,\,e\)로 돕니다. 한편 동전 2개가 만들 수 있는 곱은 \(x^2(\text{흰흰}),\,xy,\,yx,\,e(\text{검검})\)뿐 — \(x=(1\,2\,3)\)는 이 안에 없습니다. 그러니 \(x^n=x\), 곧 \(n\equiv1\pmod3\)이면 2개로 못 줄입니다. \(\blacksquare\)
아래에서 흰 동전을 치우며 \(S_3\) 곱이 그대로인 걸 보세요. \(n\equiv1\pmod3\)으로 시작하면, 아무리 해도 2개에 닿는 순간의 곱이 안 맞아 막힙니다.
놀랍게도, 방금 그 문제는 IMO 쇼트리스트(2005)보다 7년 먼저 일본의 한 입시장에 나왔습니다. 1998년 도쿄대학교 후기 이과 수학 제3문 — "대학 입시 사상 최고의 난문"으로 전설이 된 문제입니다. 워낙 어려워 시험 당일 대형 입시학원들이 풀이를 내놓지 못했다고 전해지죠.
문제는 막대로 이어 붙인 오셀로 돌(흑/백) 줄을 다룹니다. 돌을 늘리는 두 규칙이 있어요 — (가) 줄의 한쪽 끝에 새 흰 돌을 붙이면 그 끝에 있던 돌이 색이 뒤집히고, (나) 두 돌 사이에 새 흰 돌을 끼우면 양옆 두 돌이 모두 뒤집힙니다. 어떤 흑백 배열을 만들 수 있느냐 — 그리고 못 만드는 배열이 있음을 보이라는 것이었죠.
고등학교 교육과정에 없는 발상(불변량·군론)을 요구했다는 점에서 "악명"을 얻었지만 — 거꾸로, 불변량이라는 무기 하나를 쥐고 있으면 전설의 난문도 3장에서 본 그 한 줄로 관통됩니다.
불변량이 늘 "한 숫자"인 건 아닙니다. 때론 최종 결과 자체가 불변이죠. 모래더미(아벨 sandpile)가 그렇습니다. 격자의 각 칸에 모래알을 쌓다가, 한 칸이 4알 이상이 되면 무너지며(toppling) 네 이웃에 한 알씩 흘려보냅니다.
아래에 모래를 뿌려 보세요. 어디를 어떤 순서로 눌러도, 같은 양을 부었다면 늘 같은 무늬로 가라앉습니다.
큐브를 분해해 한 조각만 살짝 비틀어 끼우면, 다시 못 맞춥니다. 정상적인 회전이 보존하는 세 불변량이 그걸 막거든요.
그래서 코너 하나만 \(120^\circ\) 비틀기(방향 합이 \(\pm1\)), 엣지 하나만 뒤집기(엣지 합이 \(1\)), 두 조각만 swap(부호 불일치)은 — 셋 다 불변량을 깨므로 불가능합니다. 큐브 \(4.3\times10^{19}\)가지 상태 중 실제로 도달 가능한 건 정확히 그 \(1/12\)뿐인데, 그 \(12=3\times2\times2\)가 바로 이 세 불변량이 가두는 몫이에요.
컵 \(n\)개가 한 줄로 놓여 있고, 한 번에 정확히 두 개를 뒤집을 수 있습니다. 전부 바로 선 상태(\(\uparrow\))에서 시작해 전부 엎어진 상태(\(\downarrow\))로 만들 수 있을까요?
불변량의 사촌이 단조량(monovariant)입니다. "절대 안 변한다"가 아니라 "항상 한 방향으로만 변한다"는 양이죠. 아래로만 가는데 바닥이 있으면 — 언젠가 반드시 멈춥니다. 끝나는지(종료성)를 증명하는 가장 깔끔한 무기예요.
예컨대 줄 세운 수에서 왼쪽이 더 큰 이웃 쌍을 골라 맞바꾸기를 반복하면, 매번 뒤집힌 쌍(inversion)의 수가 정확히 \(1\)씩 줄고 \(0\) 아래로는 못 가니 — 유한 번에 정렬이 끝납니다. (5장 모래더미가 늘 멈추는 것도 같은 이유 — 적당한 단조량이 줄어들거든요.)
겉모습은 다 달랐습니다 — 돌 뛰기, 동전 치우기, 오셀로 늘리기, 모래더미, 큐브, 컵 뒤집기. 그래도 공략법은 하나였죠. 조작이 보존하는 양을 찾아 시작과 목표에서 견주는 것. 색칠(\(\bmod2\)), 곱(\(\bmod8\)), 비가환군 \(S_3\), 최종 상태 자체(아벨 모래더미), 세 가지 합동식(큐브)까지 — 불변량은 산수부터 군론까지 옷만 갈아입습니다. 그리고 "안 변한다" 대신 "한 방향으로만 변한다"의 단조량은, 게임이 반드시 끝남까지 증명해 주죠.
"강산이 변해도 변하지 않는 것" — 수학에서 그건 시(詩)가 아니라 증명의 칼날입니다. 변하는 것들의 소용돌이 속에서 꿈쩍 않는 단 하나를 찾는 순간, 불가능이 한눈에 증명되니까요. 같은 무기를 게임에 휘두른 보드 게임 페이지(잘린 체스판·15 퍼즐·님·페그 솔리테어), 그리고 패턴을 믿지마·패러독스도 함께 보세요.