도전 과제 : 하노이의 탑

본 자료는 인공지능을 활용하지 않고 작성되었음을 알립니다.

The Tower of Hanoi

학습 목표

• 하노이 탑 문제에 대해 재귀적인 문제 해결 방법을 제시할 수 있다.
• 하노이 탑 문제와 이진 카운팅(Binary Counting)의 연관성을 설명할 수 있다.
• 변형된 하노이 탑 문제와 시에르핀스키 삼각형(Sierpiński triangle)의 연관성을 설명할 수 있다.

소개

하노이의 탑 문제에 대해 알아보자.

하노이의 탑 (출처: Wikipedia)

하노이의 탑 문제는 프랑스의 수학자 에드워드 루카스(Édouard Lucas, 1842-1891)가 처음 발명했다.

이 문제와 관련하여 인도에 있는 카시 비슈와나트(Kashi Vishwanath) 사원에 대해 한 이야기가 전해지는데, 이곳에 있는 큰 방 안에는 $64$개의 황금 원반이 꽂힌 $3$개의 기둥이 있다. 전설의 내용은 고대 예언의 명령을 수행하는 브라만 사제들이 그 이후로 규칙에 따라 이 원반을 움직여 왔고, 퍼즐의 마지막 이동이 완료되면 세계가 멸망한다는 것이다.

만약 이 전설이 맞다면, 사제들이 하나의 원반을 옮길 때마다 $1$초가 걸릴 때 세계는 언제 멸망할까?

• 상황
  • 세 개의 막대$\textrm{(막대 1, 막대 2, 막대 3)}$와 크기가 서로 다른 $n$개의 원반$\textrm{(원반 0, 원반 1, 원반 2, …, }원반\;n-1)$이 있다.
  • 원반의 크기는 $\textrm{원반 0, 원반 1, 원반 2, …, }원반\;n-1$ 순으로 작다.
• 규칙

  • 각각의 막대에서는 반드시 크기 순서를 지켜서 원반을 꽂아야 한다.

    즉,$\textrm{막대 2}$에 $\textrm{원반 1, 원반 3, 원반 5}$가 꽂혀 있다면, 반드시 아래서부터 큰 순서$\textrm{(원반 5, 원반 3, 원반 1)}$로 꽂혀 있어야 한다.

  • 원반을 옮길 때는 반드시 하나씩만 옮길 수 있다.

    $막대\;1$에 있는 $\textrm{원반 1, 원반 2}$를 동시에 들어서 $막대\;3$으로 옮길 수 없다.

• 목표

  위의 규칙을 만족하면서 $n$개의 원반을 $막대\;1$에서 $막대\;3$으로 옮긴다.

• 질문

  $n$-원반 하노이 탑 문제를 풀기 위해 필요한 최소 이동 횟수 $h(n)$은 무엇일까?

해결 가이드

힌트를 보고 싶다면, 아래의 STEP들을 펼쳐보세요.

• STEP 1

  직접 $n=1, 2, 3, 4$의 경우에 대해서 답을 구해보자.

• STEP 2

  $h(3)$를 알 때, $h(4)$을 알 수 있는 방법에 대해서 생각해보자.

• STEP 3

  $h(n)$을 알 때, $h(n+1)$을 알 수 있는 방법에 대해서 생각해보자.

• STEP 4

  $h(n)$의 일반항을 구하고, 수학적 귀납법으로 이를 증명해보자.

정리하기

https://www.youtube.com/watch?v=rf6uf3jNjbo

위 영상을 보면서 하노이의 탑 문제를 다시 한 번 살펴보고, 추가 문제에 도전해보자.

추가 문제

• QUESTION #1

  $[a\rightarrow b]$는 하노이 탑 문제에서 $막대\;a$에서 $막대\;b$로 원반을 옮기는 ‘기본 이동’을 나타내며, 기본 이동 여러 개를 더하여 ‘과정’을 만들 수 있다.

  예를 들어, $[1\rightarrow 2]$와 $[1\rightarrow 3]$는 각각 $막대\;1$에서 $막대\;2$로, $막대\;1$에서 $막대\;3$으로 원반을 옮기는 기본 이동을 나타내며, 아래와 같이 이 둘을 더하여 새로운 과정을 만들 수 있다.

  \[[1\rightarrow 2]+[1\rightarrow 3]=[1\rightarrow 2,\;1\rightarrow 3]\]

  단, 덧셈의 교환 법칙은 성립하지 않는다.

  또한 아래와 같이 과정과 과정을 더하여 새로운 과정을 만들 수도 있다.

  \[[1\rightarrow 2,\;1\rightarrow 3]+[2\rightarrow 3]=[1\rightarrow 2,\;1\rightarrow 3,\;2\rightarrow 3]\]

  한편 $p(n, a\rightarrow b)$은 하노이 탑 문제에서 $n$개의 원반을 $막대\;a$에서 $막대\;b$로 옮기는 과정이다.

  예를 들어, $p(3, 1\rightarrow 3)$은 $3$개의 원반을 $막대\;1$에서 $막대\;2$으로 옮기는 과정이며, 아래와 같이 나타낸다:

  \[p(3, 1\rightarrow3)=[1\rightarrow3,\;1\rightarrow2,\;3\rightarrow2,\;1\rightarrow3,\;2\rightarrow1,\;2\rightarrow3,\;1\rightarrow3]\]

  $p(n, a\rightarrow b)$를 구하는 일반적인 방법을 설명하시오.

• QUESTION #2

  https://www.youtube.com/watch?v=2SUvWfNJSsM

  하노이의 탑 문제와 이진 카운팅(Binary Counting)의 관계를 설명하시오.

• QUESTION #3

  https://www.youtube.com/watch?v=bdMfjfT0lKk

  변형된 하노이의 탑 문제와 시에르핀스키 삼각형(Sierpiński triangle)의 관계를 설명하시오.