PROOF 182
증명하라.
하노이 탑의 최소 이동은 2ⁿ−1
자연수 ℕ 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
크기가 모두 다른 원판 n 장을 한 기둥에서 다른 한 기둥으로 규칙을 지키며 모두 옮기는 이동열이 있을 때, 그 길이 중 가장 작은 것을 M(n) 이라 한다.
증명.
(1)규칙은 넷이다. 한 번에 한 장을 옮기고, 옮기는 것은 기둥의 맨 위 원판이며, 큰 원판을 작은 원판 위에 놓지 않고, 기둥은 셋이다.A2, A3, A4, A5
(2)이동열의 길이는 자연수이므로, 그러한 이동열이 하나라도 있으면 길이의 집합에 최소가 있다.(1), A7
(3)원판이 한 장이면 그것을 목표 기둥으로 한 번 옮기면 되고, 한 번보다 적게는 옮길 수 없다. 그러므로 M(1) = 1 이다.(1), (2), A2
∎
보조정리 L1
n ≥ 2 이고 M(n−1) 이 정해지면, M(n) 도 정해지고 M(n) ≤ 2M(n−1) + 1
증명.
(1)원판에 크기 순으로 1 부터 n 까지 번호를 매기고, n 번을 가장 큰 것이라 한다.약속
(2)출발 기둥을 X, 목표 기둥을 Z, 나머지를 Y 라 한다. 기둥은 셋이므로 이것이 전부다.A5
(3)1 번부터 n−1 번까지를 X 에서 Y 로 M(n−1) 번에 옮긴다. n 번은 X 의 맨 아래에 있고 가장 크므로 어떤 원판도 그 위에 놓을 수 있다.가정, D1, A4
(4)n 번을 X 에서 Z 로 한 번 옮긴다. Z 는 비어 있다.(3), A2, A3
(5)1 번부터 n−1 번까지를 Y 에서 Z 로 M(n−1) 번에 옮긴다. n 번은 Z 의 맨 아래에 있고 가장 크므로 규칙에 어긋나지 않는다.(4), D1, A4
(6)이 이동열의 길이는 M(n−1) + 1 + M(n−1) = 2M(n−1) + 1(3), (4), (5), N
(7)n 장을 옮기는 이동열이 존재하므로 M(n) 이 정해지고, 최소는 이 길이를 넘지 않는다.(6), D1
∎
보조정리 L2
n ≥ 2 이면 M(n) ≥ 2M(n−1) + 1
증명.
(1)n 장을 옮기는 이동열 하나를 임의로 잡는다.가정, D1
(2)n 번은 출발 기둥에서 목표 기둥으로 가야 하므로 적어도 한 번 옮겨진다.(1), D1
(3)n 번을 처음 옮기는 순간, n 번은 그 기둥의 맨 위에 있고 놓일 기둥은 비어 있다. n 번은 가장 크므로 다른 원판 위에 놓을 수 없다.(2), A3, A4
(4)기둥은 셋이므로, 그 순간 1 번부터 n−1 번까지는 모두 나머지 한 기둥에 모여 있다.(3), A5
(5)그때까지의 이동은 n 번을 옮기지 않았으므로 1 번부터 n−1 번까지만의 이동이며, 그 n−1 장을 출발 기둥에서 다른 한 기둥으로 모두 옮긴 것이다.(3), (4)
(6)그동안 n 번은 출발 기둥의 맨 아래에 있고 가장 크므로 어떤 원판도 그 위에 놓는 것을 막지 않는다. 그러므로 그 이동은 n−1 장의 이동열이고, 횟수는 M(n−1) 이상이다.(5), A4, D1
(7)n 번을 마지막으로 옮기는 순간에도 같은 논의가 성립한다. 그 순간 1 번부터 n−1 번까지는 나머지 한 기둥에 모여 있고, 그 뒤의 이동으로 목표 기둥에 모여야 하므로 그 횟수도 M(n−1) 이상이다.(3), (4), (6), A5, D1
(8)세 부분은 서로 겹치지 않는다. n 번을 처음 옮기기 전, n 번의 이동, n 번을 마지막으로 옮긴 뒤다.(2), (6), (7)
(9)그러므로 이 이동열의 길이는 M(n−1) + 1 + M(n−1) = 2M(n−1) + 1 이상이다.(8), N
(10)임의의 이동열에 대하여 성립하므로 최소인 M(n) 도 그 이상이다.(1), (9), D1
∎
보조정리 L3
M(1) = 1 이고, n ≥ 2 이면 M(n) = 2M(n−1) + 1
증명.
(1)M(n) ≤ 2M(n−1) + 1L1
(2)M(n) ≥ 2M(n−1) + 1L2
(3)두 부등식에서 M(n) = 2M(n−1) + 1(1), (2), O
(4)M(1) = 1D1
∎
정리 T1
모든 자연수 n 에 대하여 M(n) = 2ⁿ − 1
증명.
(1)P(n) 을 「M(n) = 2ⁿ − 1」이라 한다.약속
(2)M(1) = 1 이고 2¹ − 1 = 2 − 1 = 1 이므로 P(1) 이 성립한다.L3, A6, N
(3)P(k) 라 하자. M(k) = 2ᵏ − 1가정
(4)M(k+1) = 2M(k) + 1L3
(5)2M(k) + 1 = 2(2ᵏ − 1) + 1 = 2ᵏ·2 − 2 + 1 = 2ᵏ⁺¹ − 1(3), (4), A6, N
(6)그러므로 P(k+1) 이 성립한다.(4), (5)
(7)그러므로 모든 n 에 대하여 P(n) 이다.(2), (6), A1
∎
비고
A1 은 이 증명에서 제거할 수 있는가.
L1 과 L2 와 L3 은 귀납을 쓰지 않는다. 제거하면 어디까지 남는지 확인하라.