#
@M

『구체 수학 1장. 재귀적인 문제들』

하노이의 탑

  • 문제를 일반화해서 작은 사례들을 살펴보는 것이 유익하다.
  • 원반 nn개를 뤼카의 규칙하에서 다른 한 기둥으로 옮기는 데 필요한 최소한의 이동 횟수를 TnT_n이라고 하면 T0=0T_0 = 0이고, T1=1T_1 = 1, T2=3T_2 = 3임이 자명함.
  • 크게 생각하는 쪽으로 관점을 바꿔보자:
    1. 작은 원반 n−1n - 1개를 다른 기둥으로 옮긴다. (Tn−1T_{n - 1})
    2. 가장 큰 원반을 다른 기둥으로 옮긴다. (T1=1T_1 = 1)
    3. 다시 작은 원반 n−1n - 1개를 가장 큰 원반 위로 옮긴다. (Tn−1T_{n - 1})
  • 따라서 원반 nn개의 이동 횟수는 2Tn−1+12T_{n - 1} + 1을 넘지 않는다:
Tn≤2Tn−1+1,n>0에 대해. T_n \leq 2T_{n - 1} + 1, n \gt 0 \text{에 대해.}
  • 등호가 아니라 부등호가 쓰인 이유는 탑을 옮기는 데 2Tn−1+12T{n - 1} + 1번 이동이 충분하다는 것만을 증명했기 때문.
  • 그러면 더 적은 수의 이동으로 탑을 옮길 수도 있을까?
    • 언젠가는 가장 큰 원반을 옮겨야 하는데, 그러기 위해서는 한 기둥에 n−1n - 1개의 작은 원반들이 한 기둥에 쌓여 있어야 한다.
    • 작은 원반들을 한 기둥에 쌓기 위해서는 Tn−1T_{n - 1}번 이동이 불가피하다.
    • 큰 원반을 마지막 기둥으로 옮긴 뒤에도 작은 원반들을 옮기려면 필연적으로 Tn−1T_{n - 1}번 이동이 발생한다.
  • 따라서 더 적은 수의 이동으로 탑을 옮길 수 없으며, 다음 식이 성립한다:
Tn≥2Tn−1+1,n>0에 대해.T0=0Tn=2Tn−1+1,n>0에 대해. (1.1) \begin{aligned} T_n &\geq 2T_{n - 1} + 1, n \gt 0 \text{에 대해.} \\ T_0 &= 0 \\ T_n &= 2T_{n - 1} + 1, n \gt 0 \text{에 대해. (1.1)} \end{aligned}
  • 이러한 식을 점화식이라고 하며, 경계값(boundary value)와 방정식으로 구성된다.
  • 닫힌 형식(closed form): 주어진 수량을 그 수량 자신을 이용하지 않고 표현하는 식. 이걸 구하면 nn이 아무리 커도 빠르게 점화식의 해를 구할 수 있다. 작은 사례들을 살펴보자:
T3=2×3+1T4=2×7+1T5=2×15+1T6=2×31+1…Tn=2n−1,n≥0에 대해. (1.2) \begin{aligned} T_3 &= 2 \times 3 + 1 \\ T_4 &= 2 \times 7 + 1 \\ T_5 &= 2 \times 15 + 1 \\ T_6 &= 2 \times 31 + 1 \\ &\dots \\ T_n &= 2^n - 1, n \geq 0 \text{에 대해. (1.2)} \end{aligned}
  • 수학적 귀납법에서 nn의 가장 작은 값 n0n_0에 대해 증명하는 것을 기초 단계라고 부른다.
  • 명제가 n0n_0에서 n−1n - 1까지의 값들에 대해 이미 증명되었다는 가정하에 n>n0n \gt n_0에 대해 증명하는 것을 귀납 단계라고 부른다.
  • T0=20−1=0T_0 = 2^0 - 1 = 0이므로 기초 단계는 자명하다.
  • 식 (1.2)가 성립한다는 가정하에, 식 (1.1)과 식 (1.2)로부터 다음 등식을 얻을 수 있음:
Tn=2Tn−1+1=2(2n−1−1)+1=2n−1 \begin{aligned} T_n &= 2T_{n - 1} + 1 \\ &= 2(2^{n - 1} - 1) + 1 \\ &= 2^n - 1 \end{aligned}

평면의 선들

  • 칼로 피자를 nn번 직선으로 자를 때 피자 조각이 최대 몇 개나 나올까?
  • 즉, 평면에 놓인 nn개의 직선으로 정의되는 영역의 최대 개수 LnL_n이 무엇일까?
  • L0=1L_0 = 1, L1=2L_1 = 2, L2=4L_2 = 4임이 자명하다. 그렇다면 Ln=2nL_n = 2^n일까? 아니다. L3=4+3=7L_3 = 4 + 3 = 7이 가능하다.
  • 하나의 새 선은 기존의 선 n−1n - 1개와 많아야 n−1n - 1개의 서로 다른 점에서 교차한다. 따라서 다음과 같은 점화식을 얻을 수 있다:
L0=1Ln=Ln−1+n,n>0에 대해. \begin{aligned} L_0 &= 1 \\ L_n &= L_{n - 1} + n, n \gt 0 \text{에 대해.} \end{aligned}
  • 닫힌 형식을 구해보자. 1,2,4,7,11,16,...1, 2, 4, 7, 11, 16, ...에서는 패턴을 찾기 힘들다. 점화식을 펼치면 점화식을 더 잘 이해할 수 있다:
Ln=Ln−1+n=Ln−2+(n−1)+n=Ln−3+(n−2)+(n−1)+n=L0+1+2+⋯+(n−2)+(n−1)+n=1+Sn,여기서Sn은1+2+3+⋯+(n−1)+n. \begin{aligned} L_n &= L_{n - 1} + n \\ &= L_{n - 2} + (n - 1) + n \\ &= L_{n - 3} + (n - 2) + (n - 1) + n \\ &= L_0 + 1 + 2 + \dots + (n - 2) + (n - 1) + n \\ &= 1 + S_n, \text{여기서} S_n \text{은} 1 + 2 + 3 + \dots + (n - 1) + n. \end{aligned}
  • 가우스가 9살 때 생각해낸 방법으로 해를 구할 수 있다. (이미 아르키메데스가 사용하긴 했다.)
2Sn=[1+2+3+⋯+(n−1)+n]+[n+(n−2)+(n−1)+⋯+2+1]=(n+1)+(n+1)+(n+1)+⋯+(n+1)+(n+1)=n(n+1),n≥에 대해.∴Ln=n(n+1)2+1,n≥에 대해. \begin{aligned} 2S_n &= [1 + 2 + 3 + \dots + (n - 1) + n] + [n + (n - 2) + (n - 1) + \dots + 2 + 1] \\ &= (n + 1) + (n + 1) + (n + 1) + \dots + (n + 1) + (n + 1) \\ &= n(n + 1), n \geq \text{에 대해.} \\ &\therefore L_n = {{n(n + 1)} \over 2} + 1, n \geq \text{에 대해.} \end{aligned}

요세푸스 문제

  • 유대-로마 전쟁 도중 로마군은 41명의 유대인을 한 동굴에 가뒀다. 이들은 둥글게 둘러 앉아 돌아가며 매번 세번째 사람을 직접 처형하는 식으로 모두 자결하기로 했다. 요세푸스는 자신과 친구가 살아남으려면 원의 어디에 있어야 할지 계산했다.
  • 문제를 변형해서 10명의 사람이 있고, 매번 두번째 사람이 죽는다고 하자. 그러면 2,4,6,8,10,3,7,12, 4, 6, 8, 10, 3, 7, 1 순서이므로 5번 사람이 살아남는다. 즉, J(10)=5J(10) = 5다.
  • 2n2n명이 있을때 첫 바퀴 후에는 1,3,5,7,…,2n−3,2n−11, 3, 5, 7, \dots, 2n - 3, 2n - 1이 살아남는다. J(2n)=2J(n)−1,n≥1에 대해.J(2n) = 2J(n) - 1, n \geq 1 \text{에 대해.}이다.
  • 사람이 홀수인 경우엔? 3,5,7,9,…,2n−1,2n+13, 5, 7, 9, \dots, 2n - 1, 2n + 1이다. 따라서 J(2n+1)=2J(n)+1,n≥1에 대해.J(2n + 1) = 2J(n) + 1, n \geq 1 \text{에 대해.}

이 문서를 인용한 문서