모서리를 자른 체스판
도미노 서른한 개로 덮을 수 있나
가로세로 8×8인 64칸 체스판에서 대각선 양 끝 모서리의 두 칸을 잘라내어 62칸을 만듭니다. 그리고 1×2 크기의 도미노 블록 31개를 준비하세요.
도미노 한 개는 정확히 두 칸을 덮으므로 31개면 62칸과 넓이가 완벽히 같습니다. 빈틈없이 겹치지 않게 전부 덮을 수 있을까요? 몇 시간을 끙끙대도 마지막 두 칸이 남는 까닭은 무엇일까요?
이야기
1946년, 철학자 막스 블랙이 논리학 교과서에 이 문제를 실었습니다. 수학책이 아니라 「생각하는 법」을 가르치는 책이었습니다. 「해 보기 전에 안 되는 줄 아는 법」의 본보기로 쓴 것입니다.
뒷날 이 문제는 인공지능 연구에서 자주 인용되었습니다. 사람은 한 번 듣고 아는데 기계는 좀처럼 못 보는 것의 예로 말입니다. 기계는 수억 가지 놓는 법을 다 해 보고서야 「안 된다」고 하는데, 사람은 색깔 하나로 한 줄에 끝냅니다.
그 한 줄이 이렇습니다. 도미노는 어디에 놓든 반드시 검은 칸 하나와 흰 칸 하나를 덮습니다. 이웃한 두 칸은 언제나 색이 다르기 때문입니다.
그러니 31개를 놓으면 검은 31칸과 흰 31칸을 덮어야 합니다. 그런데 대각선으로 마주 보는 두 모서리는 같은 색입니다. 그것을 잘라 내면 30칸과 32칸이 남습니다.
31대 31을 덮어야 하는데 30대 32가 놓여 있으니, 어떻게 놓아도 될 수가 없습니다. 시도해 볼 필요조차 없는 것입니다.
「해 보지 않고도 불가능함을 아는 법」입니다. 색칠 한 번으로 영원히 안 된다는 것을 증명했습니다.
프로그램이 어떤 상태에 절대 못 간다는 것을 보이는 불변량 기법이 이것이고, 자동 검증 도구가 쓰는 핵심 무기입니다.
계단 넷 — 같은 사실을 네 깊이로
직접 덮어 본다
작은 4×4 판에서 대각선 양 끝 두 칸을 가위로 오려내고 1×2 도미노 7개로 덮어 봅니다. 요리조리 돌려가며 아무리 빈틈없이 맞추려 해도 꼭 한 칸씩 어긋나거나 남습니다.
판의 색깔을 가만히 들여다보세요. 검은 칸과 흰 칸이 번갈아 칠해져 있습니다. 오려낸 두 칸의 색이 둘 다 같은 색이라는 사실을 눈으로 확인해 보세요.
체스판을 도미노로 덮어 보세요
홀수×홀수는 칸이 홀수라 절대 안 덮입니다.
색칠로 알아채기
체스판의 칸들은 검은색 32개, 흰색 32개였습니다. 그런데 대각선 양 끝의 모서리 두 칸은 항상 같은 색깔입니다.
흰 칸 두 개를 잘라냈다면 남은 칸은 검은 칸 32개, 흰 칸 30개입니다. 그런데 도미노 하나를 판 위에 놓으면 반드시 검은 칸 하나와 흰 칸 하나를 동시에 덮습니다. 도미노 31개가 덮으려면 검은 칸 31개, 흰 칸 31개가 필요한데 개수가 맞지 않으므로 절대로 덮을 수 없습니다.
모서리를 잘라 내면
마주 보는 모서리는 같은 색이라 잘라 내면 색 수가 어긋나 영영 못 덮습니다.
불변량 논증
이 증명은 수학에서 불변량(Invariant)과 착색 논증(Coloring Argument)의 가장 아름다운 본보기입니다. 직접 놓아보는 수천만 가지의 배치를 일일이 검사하지 않고도 대상의 본질적인 짝홀성 불균형을 짚어내어 불가능성을 단번에 증명합니다.
더 넓혀서 체스판에서 검은 칸 하나와 흰 칸 하나를 아무렇게나 잘라낸 62칸 판은 곰모리(Gomory)의 정리에 의해 항상 도미노로 덮을 수 있음도 해밀턴 닫힌 길(Hamiltonian cycle)을 이용해 증명할 수 있습니다.
직사각형은 어떨까요
구멍이 뚫리면 색칠하기로 따져야 합니다.
덮개 이론
도미노 덮개 문제는 통계물리학과 조합론에서 다이머 모델(Dimer Model) 및 이분 그래프의 완전 매칭(Perfect Matching) 이론으로 깊게 발전했습니다.
카스텔레인(Kasteleyn) 공식과 템펄리-피셔(Temperley-Fisher) 방법은 인접 행렬의 행렬식(Pfaffian)을 계산하여 임의의 격자를 덮는 총 경우의 수를 정확히 계산합니다. 물질의 상전이 현상과 나노 구조체의 결합 배열을 해석하는 강력한 도구로 쓰입니다.
덮는 방법이 몇 가지
8×8 판은 12,988,816 가지 — 카스텔레인이 공식을 찾았습니다.
풀어 보기
체스판과 도미노 덮기. 8×8 체스판의 총 64칸은 검은 칸 32개와 흰 칸 32개로 칠해져 있다.
(1) 대각선 양 끝의 두 모서리 칸을 제거했을 때, 남은 62칸을 1×2 도미노 31개로 덮을 수 없는 까닭을 흑백 칸의 개수로 설명하시오.
(2) 체스판에서 검은 칸 1개와 흰 칸 1개를 각각 하나씩 임의로 제거하여 62칸을 남겼다. 이 판을 1×2 도미노 31개로 항상 덮을 수 있는가? (답과 까닭을 쓰시오)
(3) 10×10 체스판에서 대각선 양 끝 2칸을 잘라낸 98칸을 1×2 도미노 49개로 덮을 수 있는지 판정하시오.
(2) 검은 칸과 흰 칸이 각각 31개씩 남으며 체스판 순환 회로(해밀턴 회로) 상에서 항상 분할 가능하므로 덮을 수 있습니다.
답과 풀이 보기
(1) 도미노는 한 칸이 검고 한 칸이 희게 반드시 두 색을 하나씩 덮습니다. 그러니 31 개로 덮으려면 검은 칸 31 개, 흰 칸 31 개가 있어야 합니다.
그런데 대각선 양 끝 두 귀퉁이는 같은 색입니다. 그 둘을 떼면 30 대 32 로 어긋납니다. 색의 수가 맞지 않기 때문에 절대 못 덮습니다.
(2) 항상 덮을 수 있습니다.
검은 칸 하나와 흰 칸 하나를 떼면 31 대 31 로 맞습니다. 그것만으로는 모자라 보이지만, 체스판을 한 붓으로 도는 닫힌 길(해밀턴 회로)이 있습니다. 그 고리에서 두 칸을 떼면 고리가 토막 둘로 갈리는데, 두 칸의 색이 다르므로 각 토막의 칸 수가 짝수가 되어 도미노로 차례차례 덮입니다. (1973 년 랄프 고몰리가 보인 증명입니다.)
(3) 도 마찬가지로 못 덮습니다.
짝수 크기 판에서는 대각선 양 끝이 늘 같은 색이라 48 대 50 으로 어긋납니다.
덮어 보려고 몇 시간을 써도 답이 안 나옵니다. 그런데 색을 세는 순간 한 줄로 끝납니다.
더 멀리
「변하지 않는 것을 찾아 불가능을 보이기」는 강력한 수법입니다.
- 불변량 — 아무리 움직여도 변하지 않는 값을 찾으면 도달할 수 없는 상태를 알 수 있습니다
- 15 퍼즐 — 두 칸만 바꿔 놓으면 절대 못 맞추는 것도 같은 이치입니다
- 화학과 물리 — 보존량을 찾는 것이 곧 법칙을 찾는 일입니다
이어지는 장
도미노 하나는 언제나 검은 칸 하나와 흰 칸 하나를 덮는다는 불변량(색의 짝홀성)은 타일을 이리저리 맞춰 보지 않고도 불가능함을 한눈에 꿰뚫어 보게 합니다 — 제60장 에서 15 퍼즐의 이동 가능성을 가르는 짝홀성 증명과 같은 눈으로 읽어보세요.
영감을 받은 곳
철학자 막스 블랙(Max Black)이 1946년 저서 『비판적 사고』(Critical Thinking)에서 처음 제시하고, 수학 퍼즐의 대가 마틴 가드너(Martin Gardner)가 널리 알린 유명한 '모서리가 잘린 체스판 문제'에서 왔습니다.