하노이의 탑은 일본 고등학교 수학(수학B)의 점화식이나 수학적 귀납법의 소재로 교과서와 입시 문제에 자주 나와요. 이 기사에서는 예제를 풀면서 생각하는 법을 연습해요. 원판에는 작은 것부터 차례로 1, 2, 3…번을 붙이고, 원판 n개의 탑을 옮기는 최소 수를 aₙ이라고 써요.
예제 1 점화식 세우기
문제: 기둥 A·B·C 3개가 있고, A에 크기가 다른 원판 n개가 큰 순서대로 쌓여 있다. 원판을 한 번에 1개씩 움직이고, 작은 원판 위에 큰 원판을 놓지 않도록 하며, 모든 원판을 C로 옮긴다. 최소 수를 aₙ이라고 할 때, aₙ₊₁을 aₙ으로 나타내라.
푸는 법: 가장 큰 원판(n+1번)에 주목해요. 이 원판을 C로 움직이려면 그 순간 위의 n개가 모두 B에 쌓여 있어야 해요.
- 위의 n개를 A에서 B로 옮긴다 … 최소 aₙ수
- n+1번 원판을 A에서 C로 움직인다 … 1수
- B의 n개를 C로 옮긴다 … 최소 aₙ수
이 순서로 n+1개를 옮길 수 있으니 aₙ₊₁ ≦ 2aₙ + 1이에요. 거꾸로 어떤 순서든 1~3의 수는 반드시 드니 aₙ₊₁ ≧ 2aₙ + 1이에요. 따라서,
aₙ₊₁ = 2aₙ + 1(a₁ = 1)
입시에서는 ”≦“와 ”≧“를 둘 다 보여서 등호를 단정하는 것이 요구되기도 해요. 자세한 설명은 최소 수 공식에 있어요.
예제 2 일반항 구하기
문제: a₁ = 1, aₙ₊₁ = 2aₙ + 1로 정해지는 수열의 일반항을 구하라.
푸는 법: aₙ₊₁ = paₙ + q 꼴의 점화식은 α = 2α + 1을 만족하는 α를 써서 변형해요. α = −1이니 양변에 1을 더하면,
aₙ₊₁ + 1 = 2(aₙ + 1)
이 돼요. 수열 aₙ + 1은 첫째항 a₁ + 1 = 2, 공비 2인 등비수열이에요. 따라서 aₙ + 1 = 2 · 2ⁿ⁻¹ = 2ⁿ이고,
aₙ = 2ⁿ − 1
검산으로 a₁ = 1, a₂ = 3, a₃ = 7이 점화식과 맞는지 확인해 두어요.
예제 3 수학적 귀납법으로 증명하기
문제: 원판 n개를 옮기는 최소 수가 2ⁿ − 1임을 수학적 귀납법으로 증명하라.
푸는 법:
- n = 1일 때, 원판 1개는 1수로 옮길 수 있고 그보다 적게는 할 수 없으니, 최소 수는 1 = 2¹ − 1로 성립한다.
- n = k일 때 최소 수가 2ᵏ − 1이라고 가정한다. n = k+1일 때, 예제 1의 생각에 따라 최소 수는 2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1이 되어 n = k+1일 때도 성립한다.
- 1, 2에 의해 모든 자연수 n에 대해 성립한다.
예제 1의 “≦와 ≧ 둘 다”를 귀납법의 2단계에서 쓰고 있다는 것이 요점이에요.
예제 4 옆 기둥으로만 움직일 수 있는 경우
문제: 기둥 A·B·C가 일렬로 놓여 있고, 원판은 A와 B, B와 C 사이에서만 움직일 수 있다(A에서 C로 바로는 움직일 수 없다). 원판 n개를 A에서 C로 옮기는 최소 수 bₙ을 구하라.
푸는 법: 가장 큰 원판 n은 A → B → C로 2번 움직여야 해요.
- 위의 n−1개를 A에서 C로 옮긴다 … bₙ₋₁수(n을 B로 움직이려면 B를 비워 두어야 한다)
- 원판 n을 A에서 B로 … 1수
- n−1개를 C에서 A로 옮긴다 … bₙ₋₁수(n을 C로 움직이려면 C를 비워 두어야 한다)
- 원판 n을 B에서 C로 … 1수
- n−1개를 A에서 C로 옮긴다 … bₙ₋₁수
따라서 bₙ = 3bₙ₋₁ + 2(b₁ = 2). α = 3α + 2에서 α = −1이니 bₙ + 1 = 3(bₙ₋₁ + 1). 수열 bₙ + 1은 첫째항 3, 공비 3인 등비수열이니,
bₙ = 3ⁿ − 1
원판 1~6개에 대해 모든 배치를 조사하는 계산으로도 이 수가 최소임을 확인했어요. 재미있게도 3ⁿ − 1수 동안 3ⁿ가지 모든 배치를 한 번씩 지나가요(배치의 수는 규칙성 기사).
예제 5 연습 문제
마지막으로 직접 풀어 봐요. 답은 아래에 있어요.
- 원판이 10개일 때의 최소 수를 구하라.
- 최소 수가 1000수를 넘는 것은 원판이 몇 개 이상일 때인가.
- 최소 순서로 원판 n개를 옮길 때 가장 작은 원판은 몇 번 움직이는가.
답: 1. 2¹⁰ − 1 = 1023수. 2. 2ⁿ − 1 > 1000에서 2ⁿ > 1001, 2⁹ = 512, 2¹⁰ = 1024이니 10개 이상. 3. 2ⁿ⁻¹번(이유는 규칙성 기사의 “원판별로 움직이는 횟수”).
