하노이탑은 고대 인도의 한 사원에서 유래되었는데요..

3개의 막대와 8개(9,10개)의 크기가 서로 다은 원반으로 구성이 되어 있습니다.

즉, 1개의 막대에 8개의 원반이 크기별로 쌓여있는데.. 이 원반을 다른 원기둥으로 모두 옮기는 것이 하노이탑퍼즐입니다..

원반은 한번에 한개씩 옮겨야 하고, 작은원반 위에 큰원반을 올려 놓을 수는 없습니다.

이 하노이탑은 최소의 이동횟수로 옮겨져야 하는데 원판이 2개면 3번, 4개면 15번이 됩니다.

그렇다면 원반이 6개이면 63번이 됩니다. 

원반을 옮기는 방법을 보면요...

보시면 알겠지만..

마치 수학공식처럼 규칙에 의해서 원반이 움직이게 됩니다.

해서 하노이탑을 집행력교구라고도 합니다.

이런식으로 6개의 원반도 동일한 규칙을 갖고 움직이게 됩니다.

공식으로 풀어보면요...

원판의 개수가 1개일때는 이동횟수 f(1)=1
원판의 개수가 2개일때는 이동횟수 f(2)= 2×f(1)+1 = 3
원판의 개수가 3개일때는 이동횟수 f(3)= 2×f(2)+1 = 7
원판의 개수가 4개일때는 이동횟수 f(4)= 2×f(3)+1 = 15
원판의 개수가 5개일때는 이동횟수 f(5)= 2×f(4)+1 = 31
원판의 개수가 6개일때는 이동횟수 f(6)= 2×f(5)+1 = 63

처음엔 이해가 되지 않겠지만 조금 하다보면 손이 먼저 움직이게 될 것입니다.

그럼....