먼저 두면 이긴다 — 그런데 어떻게?
독초콜릿을 피하는 필승의 수
가로세로 격자 모양의 초콜릿 판이 있습니다. 맨 왼쪽 아래의 한 조각에는 치명적인 독이 묻어 있습니다.
두 사람이 번갈아 조각 하나를 골라 그 조각의 오른쪽과 위쪽에 있는 모든 조각을 먹어치웁니다. 마지막 독초콜릿을 먹는 사람이 집니다. 먼저 두는 사람이 100% 이기는 필승 전략이 존재한다는 증명이 있습니다. 그런데 왜 아무도 그 구체적인 첫 수를 모를까요?
이야기
직사각형 초콜릿이 있습니다. 두 사람이 번갈아 한 칸을 고르면, 그 칸과 오른쪽 아래에 있는 모든 칸이 사라집니다. 왼쪽 맨 위 칸에는 독이 발라져 있어서, 그것을 먹는 사람이 집니다.
이 놀이에는 놀라운 사실이 있습니다. 먼저 두는 사람이 반드시 이깁니다. 1×1이 아닌 어떤 크기에서도 그렇습니다.
증명은 이렇습니다. 만약 오른쪽 맨 아래 한 칸을 먹는 것이 이기는 수라면 그것으로 이깁니다. 그것이 지는 수라고 해 봅시다. 그러면 상대가 그 상태에서 이기는 수를 갖고 있다는 뜻입니다.
그런데 그 수를 내가 처음부터 두면 됩니다. 오른쪽 아래 한 칸을 먹는 것은 다른 어떤 수의 결과에도 포함되기 때문입니다. 그러니 어느 쪽이든 먼저 두는 사람이 이깁니다.
여기서 소름 돋는 점은 이것입니다. 이기는 방법이 있다는 것은 알지만, 그 방법이 무엇인지는 모릅니다. 이런 것을 비구성적 증명이라 합니다.
이 놀이를 만든 사람은 데이비드 게일입니다. 1974년의 일입니다. 앞서 제109장에서 안정한 짝짓기를 만든 그 사람입니다. 그는 놀이를 좋아했고, 이 초콜릿 판 놀이도 그렇게 나왔습니다.
「이기는 방법이 있다는 것은 아는데 그것이 무엇인지는 모른다」는 드문 예입니다.
존재는 증명되었지만 방법은 미지 — 수학에는 이런 비구성적 증명이 많고, 그것이 「알고 있다」의 뜻을 다시 묻게 합니다.
계단 넷 — 같은 사실을 네 깊이로
초콜릿 판으로 겨뤄 본다
가로 2, 세로 2인 4조각 판이나 가로 3, 세로 2인 판을 종이에 그려 바둑돌을 놓고 둘이 겨뤄 봅니다. 독이 묻은 (1,1) 자리를 상대에게 남겨주어야 합니다.
2×2 판에서는 첫 번째 사람이 오른쪽 위 (2,2) 조각 하나만 딱 먹으면 독 주위에 3조각이 대칭으로 남아 상대가 두는 대로 따라 두어 무조건 이기는 자리를 손으로 찾아보세요.
초콜릿을 베어 물어 보세요
그런데 어떻게 두어야 하는지는 모릅니다.
작은 판에서 이기는 수
가로세로가 같은 정사각형 판에서는 먼저 두는 사람이 맨 오른쪽 위 대각선 꼭짓점 조각 하나만 먹고 나면, 판이 대각선을 기준으로 완벽한 대칭이 됩니다.
이후 상대가 가로 쪽에서 몇 칸을 먹으면 나는 세로 쪽에서 똑같이 먹어치우는 대칭 전략(Symmetry Strategy)을 쓰면 먼저 두는 사람이 언제나 100% 승리합니다.
전략 훔치기
그 뒤 나중 쪽에게 이기는 수가 있다면 내가 처음에 그 수를 두면 됩니다 — 모순.
전략 훔치기 논증
직사각형 판에서도 선공 필승임이 수학적으로 증명되어 있습니다. 1974년 데이비드 게일(David Gale)은 기막힌 '전략 훔치기 논증(Strategy-Stealing Argument)'을 제시했습니다.
만약 후공에게 필승 전략이 있다면, 선공이 첫 수로 맨 오른쪽 위 조각 단 1개만 먹은 후, 후공이 둘 승리의 수를 선공이 그대로 가로채어 둘 수 있으므로 모순이 발생합니다. 따라서 후공 필승은 불가능하며 반드시 선공 필승 전략이 존재합니다.
증명은 있는데 방법은 없습니다
3×n 부터는 컴퓨터로 하나하나 찾아야 합니다.
비구성적 증명
전략 훔치기 증명의 놀라운 점은 선공이 이긴다는 사실은 완벽하게 증명하지만, "그 첫 수가 구체적으로 어디인가"는 전혀 알려주지 않는 비구성적 증명(Non-constructive Proof)이라는 점입니다.
촘프와 헥스(Hex) 게임의 이러한 존재성 증명은 조합 게임 이론과 알고리즘 복잡도론에서 완전 정보 유한 게임의 상태 트리 탐색 및 PSPACE-완전 계산 복잡도를 연구하는 환상적인 모델로 사랑받고 있습니다.
비구성적 증명
수학에는 이런 증명이 꽤 많습니다 — 존재는 아는데 찾을 수는 없는.
풀어 보기
촘프 게임과 전략 훔치기. 맨 왼쪽 아래 (1,1)에 독이 든 격자 판에서 두 사람이 조각을 지워나가는 게임을 한다.
(1) 2×2 크기의 초콜릿 판에서 첫 번째 사람이 반드시 이기기 위해 첫 수로 지워야 하는 조각의 위치를 쓰시오.
(2) 정사각형 판에서 첫 번째 사람이 (1)의 조각을 지운 후 승리를 보장받기 위해 사용하는 대칭 전략의 원리를 설명하시오.
(3) 선공 필승 전략이 존재함을 증명하면서도 구체적인 수순을 제시하지 않는 수학적 증명 방식을 무엇이라 부르는가?
(1) 맨 오른쪽 위 조각인 (2,2)입니다. (3) 비구성적 증명(Non-constructive Proof)입니다.
답과 풀이 보기
(1) 맨 오른쪽 위 (2,2) 조각 하나만 지웁니다.
그러면 독이 든 (1,1) 을 낀 L 자 세 칸이 남습니다 — 가로로 하나, 세로로 하나가 뻗은 모양입니다.
(2) 거울처럼 따라 하기입니다.
판에서 먼저 오른쪽 위 덩어리를 통째로 먹으면, 남는 것은 가로 한 줄과 세로 한 줄이 (1,1) 에서 만나는 완벽하게 대칭인 L 입니다.
이제 상대가 가로줄에서 번째를 먹으면 나는 세로줄에서 번째를 먹습니다. 언제나 대칭이 되도록 되돌려 놓으면 마지막에 남는 독 한 칸은 반드시 상대 차례가 됩니다.
(3) 비구성적 증명이라 합니다 — 촘프에서는 전략 훔치기가 그것입니다.
만약 후공에게 필승 전략이 있다고 해 봅시다. 그러면 선공이 오른쪽 위 한 칸만 먹고 그 전략을 그대로 훔쳐 쓰면 됩니다 (그 한 칸은 이미 먹혔으니 손해가 아닙니다). 그러면 둘 다 이긴다는 모순이 생깁니다. 그러므로 이기는 쪽은 선공입니다.
이 증명은 선공이 이긴다고만 말할 뿐, 어떻게 두어야 하는지는 한 마디도 하지 않습니다.
실제로 일반적인 촘프에서 첫 수를 어디에 둬야 하는지는 지금도 아무도 모릅니다. 이길 줄 아는데 두는 법을 모릅니다.
더 멀리
「있다는 것은 아는데 어디 있는지는 모른다」는 수학에 흔합니다.
- 전략 훔치기 — 이 논증 방식은 다른 놀이에도 쓰입니다
- 존재 증명 — 답이 있음을 보이는 것과 찾는 것은 다른 일입니다
- 직접 해 보기 — 3×3 초콜릿으로 겨뤄 보세요. 먼저 두는 쪽이 이깁니다
이어지는 장
돌을 가져가는 규칙으로 필승 전략을 직접 계산할 수 있는 놀이와 달리, 여기서는 이기는 수가 존재한다는 사실만 알고 구체적인 수는 감추어져 있습니다 — 제54장 과 견주어 보세요.
영감을 받은 곳
데이비드 게일(David Gale)이 1974년 미국수학월보(The American Mathematical Monthly)에 낸 논문 「A Curious Nim-Type Game」에서 제안한 놀이와, 존 내시(John Nash)가 1950년 전후 헥스(Hex) 게임의 선공 필승을 보이기 위해 고안한 전략 훔치기 논증(strategy-stealing argument)에서 왔습니다.