15 퍼즐
딱 두 숫자만 바꿀 수 있나요
1부터 15까지 조각이 든 15 퍼즐이 있습니다. 빈 칸이 하나뿐이라 조각을 그리로 밀어 옮깁니다.
다 맞춰진 판에서 14와 15만 서로 바꿔 놓고 시작한다고 합시다. 두 칸만 어긋났으니 금방 되돌릴 수 있을 것 같지요. 그런데 밀고 또 밀어도 제자리로 안 갑니다. 덜 해 본 걸까요, 아니면 애초에 막혀 있는 걸까요?
이야기
가로세로 넉 줄, 열여섯 칸에 1부터 15까지 조각이 있고 한 칸이 비어 있습니다. 조각을 밀어 순서대로 맞추는 놀이입니다.
1870년대에 이 퍼즐이 미국과 유럽을 휩쓸었습니다. 그런데 14와 15만 바뀐 채 나머지는 다 맞은 상태로 파는 것이 있었습니다. 원래대로 맞추면 상금을 준다고 했습니다.
아무도 못 받았습니다. 영원히 못 맞추기 때문입니다.
까닭은 이렇습니다. 조각을 한 번 밀 때마다 빈 칸이 한 칸 움직입니다. 그리고 조각 배열의 뒤바뀜 횟수가 홀수인지 짝수인지가 정해진 규칙에 따라 변합니다. 이 짝홀이 맞지 않으면 아무리 밀어도 도달할 수 없습니다.
두 조각만 바꾼 상태는 짝홀이 반대입니다. 그래서 절대 못 갑니다. 상금을 안전하게 걸 수 있었던 것입니다.
1880년 미국의 퍼즐가 샘 로이드가 14와 15만 뒤바뀐 배열을 내놓고 1000달러를 걸었습니다. 온 나라가 이 퍼즐에 매달렸습니다. 그는 끝내 상금을 내주지 않았습니다. 그 배열은 애초에 맞출 수 없는 것이었기 때문입니다.
🚩 게다가 이 퍼즐을 자기가 만들었다는 로이드의 주장도 사실이 아닙니다. 실제로 만든 사람은 우체국장 노이스 채프먼이었습니다.
「섞을 수 있는 것과 없는 것」을 가릅니다. 15 퍼즐의 절반은 아무리 해도 못 맞춥니다.
로봇 팔이 어떤 자세에서 어떤 자세로 갈 수 있는지, 화학 분자가 거울상으로 뒤집힐 수 있는지를 판정하는 데 같은 홀짝 불변량이 쓰입니다.
계단 넷 — 같은 사실을 네 깊이로
퍼즐을 맞춰 본다
작은 2×2 판에 숫자 1, 2, 3이 적힌 조각 세 개를 넣고 빈칸으로 밀어 봅니다. 조각들을 이리저리 돌려 보면 순환하는 순서는 바꿀 수 있지만, 딱 두 숫자의 순서만 뒤집는 것은 불가능합니다.
조각을 위아래나 좌우로 아무리 밀어도 바꿀 수 없는 고유한 배열의 규칙이 판 속에 존재함을 손으로 직접 움직이며 느껴보세요.
15 퍼즐을 섞어 보세요
「14-15 퍼즐」로 1880년에 상금이 걸렸는데 아무도 못 탔습니다.
안 되는 배열이 있다는 것
퍼즐 조각을 가로로 움직일 때는 숫자들의 순서(앞뒤 관계)가 전혀 바뀌지 않습니다. 세로로 한 칸 움직이면 어떤 조각이 세 칸을 건너뛰게 되므로 역전(Inversion, 큰 수가 작은 수보다 앞에 오는 쌍)의 개수가 홀수 개(±1 또는 ±3)만큼 변합니다.
동시에 빈칸의 행 위치도 한 칸 바뀌므로, (역전의 총 개수 + 빈칸의 행 번호)의 홀짝성(Parity)은 조각을 아무리 움직여도 절대 변하지 않는 불변량이 됩니다.
빈 칸의 자리도 셉니다
이 둘의 합이 안 바뀌는 값(불변량) 입니다.
짝홀 불변량
수학적으로 15 퍼즐의 배치는 16개 원소의 치환(Permutation)에 해당합니다. 빈칸을 제자리로 돌려놓는 모든 조각의 이동은 짝수 번의 호환(Transposition)의 곱으로 표현되는 우치환(Even Permutation)만을 만들어냅니다.
14와 15만 맞바꾼 상태는 홀수 번의 호환으로 만들어진 기치환(Odd Permutation)입니다. 우치환들의 집합인 교대군 안에서만 움직일 수 있으므로 전체 가지 상태 중 정확히 절반()만 도달 가능하며, 나머지 절반은 영원히 풀 수 없습니다.
절반만 풀립니다
이것이 군론의 교대군입니다.
순열의 부호
1870년대 샘 로이드가 현상금을 걸어 전 세계를 열광시켰던 15 퍼즐은 추상대수학의 치환군과 불변량 이론을 대중에게 각인시킨 역사적 사건이었습니다.
현대에는 루빅스 큐브의 상태 공간 분석, 그래프 상의 조약돌 옮기기 문제(Pebbling), 로봇 팔의 장애물 회피 경로 계획 알고리즘의 도달 가능성(Reachability) 판정에 치환군의 불변량 구조가 핵심적으로 활용됩니다.
루빅스 큐브도 마찬가지
2×3×2 = 12 분의 1 만 풀립니다.
풀어 보기
15 퍼즐의 불변량. 4×4 격자판에 1부터 15까지의 숫자 조각과 빈칸 1개가 있다. 빈칸이 오른쪽 맨 아래(4행 4열)에 있을 때, 완성된 정상 상태의 역전 수는 0이다.
(1) 빈칸이 4행 4열에 그대로 있는 상태에서 14와 15의 위치만 서로 바꾼 배열의 역전 수의 짝홀성을 말하시오.
(2) 조각을 합법적으로 이동하여 빈칸이 4행 4열로 돌아왔을 때, 가능한 배열은 치환군 관점에서 우치환이어야 하는가, 기치환이어야 하는가?
(3) 14와 15만 바뀐 상태에서 퍼즐을 완성하는 것이 불가능한 까닭을 (1)과 (2)를 종합하여 설명하시오.
14와 15의 호환은 기치환(역전 수 1)이므로, 빈칸이 제자리일 때 우치환만 가능한 규칙과 모순됩니다.
답과 풀이 보기
(1) 14 와 15 만 맞바꾼 것은 호환(맞바꿈) 하나입니다. 그 둘 말고는 앞뒤가 뒤집힌 짝이 없으므로 역전 수는 1 — 홀수입니다.
(2) 우치환(짝치환)이어야 합니다.
조각을 한 번 밀 때마다 빈칸과 조각이 자리를 맞바꿉니다 — 호환 하나입니다. 그런데 빈칸은 판을 체스판처럼 칠했을 때 한 번 움직일 때마다 색이 바뀝니다. 그러니 빈칸이 제자리(4행 4열)로 돌아왔다면 움직인 횟수는 반드시 짝수이고, 짝수 번의 호환은 우치환입니다.
(3) (1) 에서 그 배열은 기치환(홀치환)이고, (2) 에서 손으로 닿을 수 있는 것은 우치환뿐입니다. 우치환과 기치환은 절대로 겹치지 않기 때문입니다. 그래서 아무리 오래 밀어도 맞출 수 없습니다.
1880 년 무렵 미국에서 이 퍼즐에 1,000 달러 상금이 걸렸습니다. 수많은 사람이 밤을 새웠지만 아무도 받지 못했습니다. 못 푼 것이 아니라 애초에 길이 없었습니다. 짝홀성 하나가 그것을 세 줄로 말해 줍니다.
더 멀리
「갈 수 있는 상태」와 「갈 수 없는 상태」를 가르는 것이 불변량입니다.
- 루빅스 큐브 — 스티커를 두 개만 바꿔 붙이면 영원히 못 맞춥니다
- 순열의 부호 — 짝홀은 수학에서 아주 널리 쓰이는 개념입니다
- 직접 확인 — 3×3(8퍼즐)로 해 보면 절반은 맞출 수 없습니다
이어지는 장
조각을 아무리 움직여도 치환의 짝홀성이 변하지 않아 결코 도달할 수 없는 배치가 존재한다는 원리는, 체스판 모서리를 자르면 도미노로 덮을 수 없는 제58장 과 똑같이 불변량의 눈으로 수학적 불가능을 꿰뚫어 보는 법을 가르쳐 줍니다.
영감을 받은 곳
1874년 노이스 채프먼(Noyes Chapman)이 고안하고 샘 로이드(Sam Loyd)가 14와 15를 뒤집어 현상금을 걸어 대유행을 일으켰으며, 1879년 존슨과 스토리가 『미국수학저널』(American Journal of Mathematics)에서 순열의 패리티(치환의 홀짝성)로 완전 증명했습니다.