개요

  • 이 문서는 [[CONCRETE-MATH]]책의 1장을 공부하며 메모한 것입니다.
  • 이 문서는 메모일 뿐이니 자세한 내용은 교재를 참고해야 합니다.

1.1 하노이의 탑(THE TOWER OF HANOI)

  • 프랑스 수학자 에두아르 뤼카(Edouard Lucas)가 1883년에 만든 문제.
  • 하노이의 탑 규칙은 위키백과를 참고.

하노이의 탑 점화식

: 원반 n 개를 다른 한 기둥으로 옮기는 데 필요한 최소한의 이동 횟수

  •  
  •  
  • : 3번 만에 원반 2 개를 다른 한 기둥으로 옮길 수 있다.

python 코드로 표현하자면 다음과 같이 함수 T의 출력 결과 목록이라고 이해할 수 있다.

print( T(0) )   # 출력 결과는 0
print( T(1) )   # 출력 결과는 1
print( T(2) )   # 출력 결과는 3

다음 과정을 거치면 n개의 원반이 있는 하노이의 탑을 클리어할 수 있다.

  1. 가장 큰 원반 하나를 제외한 n - 1 개의 원반을 다른 기둥으로 옮긴다.
    • 이동 횟수는 .
  2. 가장 큰 원반을 나머지 기둥으로 옮긴다.
    • 이동 횟수는 1.
  3. n - 1 개의 원반을 가장 큰 원반 위로 옮긴다.
    • 이동 횟수는 .

그렇다면 총 이동 횟수는 이므로, 다음과 같은 일반식을 만들 수 있다.

식 1.1

이와 같이 '경곗값(boundary value)'과 등식으로 구성되는 등식들을 다음과 같이 부른다.

  • 점화식(recurrence)
  • 점화 관계식(recurrence relation)
  • 재귀식, 재귀관계식(recursion relation)

참고로 위의 점화식을 python 코드로 표현하자면 다음과 같다.

def T(n):
    if n == 0:
        return 0
    return 2*T(n-1) + 1

점화식의 해(solution)

작은 n 값들을 살펴보기

for n in range(7):
    print(
        "T_{input} = {result}"
        .format(input=n, result=T(n))
    )
# T_0 = 0
# T_1 = 1
# T_2 = 3
# T_3 = 7
# T_4 = 15
# T_5 = 31
# T_6 = 63

곰곰히 살펴보면 다음과 같은 추측을 할 수 있다.

식 1.2

def T(n):
    return 2**n - 1

수학적 귀납법(mathematical induction)

수학적 귀납법

  • 기초 단계(basis) : 에 대해 명제를 증명한다.
  • 귀납 단계(induction) : (에서 에 대해 명제가 증명되었다는 가정 하에서) 에 대해 명제를 증명한다.

기초 단계

기초 단계는 쉽게 해결할 수 있다.

귀납 단계

식 1.1을 사용해 식 1.2를 유도해 냄으로써, 식 1.2가 모든 에 대하여 성립함을 보인다.

점화식의 해를 간단하게 구하기

식 1.1의 양 변에 1을 더해보자.

이 때, 이라 하면 다음과 같이 간단하게 바꿀 수 있다.

def U(n):
    if n == 0:
        return 1
    return 2*U(n-1)

# T_0 = 0     U_0 = 1
# T_1 = 1     U_1 = 2
# T_2 = 3     U_2 = 4
# T_3 = 7     U_3 = 8
# T_4 = 15    U_4 = 16
# T_5 = 31    U_5 = 32
# T_6 = 63    U_6 = 64

Links