➌ 이번에는 2번 기둥에 있는 원반 두 개를 3번 기둥으로 옮깁니다. 비어 있는 1번 기둥을 보조 기둥으로 활용하여 2번 기둥에 있는 원반 두 개를 3번 기둥으로 옮기는 문제입니다. 2 → 1, 2 → 3, 1 → 3 순서로 이동합니다(실제로 원반은 세 번 이동합니다).

 

그림 6-11 2번 기둥의 원반 두 개를 3번으로 이동(2 → 1, 2 → 3, 1 → 3)

 

정리하면 원반을 한 개씩 전부 일곱 번 옮기면 문제가 해결됩니다(3 + 1+ 3 = 7).

 

이렇게 원반 세 개를 옮기는 과정을 살펴보고 나니 일반적인 경우에 대해서도 어느 정도 감이 생깁니다. 원반이 n개일 때 역시 다음과 같이 생각할 수 있습니다.