하노이의 탑 (Tower of Hanoi)

하노이의 탑 출처-위키백과

하노이의 탑 (Tower of Hanoi)은 퍼즐 게임의 일종입니다. 기둥 3개와 이 기둥에 꽂을 수 있는 크기가 다양한 원판이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다.

두 가지 조건을 만족시키면서 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓으면 게임이 끝나게 됩니다.

 

조건1. 한 번에 하나의 원판만 옮길 수 있습니다.

조건2. 큰 원판이 작은 원판 위에 있어서는 안됩니다.

 

하노이의 탑은 1883년 프랑스 수학자 루카스(Lucas)가 고안한 것으로, 기둥에 꽂혀 있는 64개의 원판을 다른 기둥으로 옮기면 세상의 종말이 온다는 인도의 전설에서 유래되었습니다.

원판의 수가 64개로 쉽게 보이지만 전부 옮기려면 간단한 문제가 아닙니다.

원판의 수에 따라 이동 횟수를 알아볼까요?

하노이의 원판 64개를 옮기려면 적어도 약 1844경 6744조 737억 955만 1615번을 움직여야 해요. 원판 1개를 옮기는 데 1초가 걸린다고 하면 이 원판을 모두 옮기는 데 약 5849억 년이 걸려요.

전설에 따르면 세상의 종말이 오기까지는 아직 엄청난 시간이 남아있는 셈입니다.

 

출처-최고수준 수학3-1