하노이 타워
한쪽에 쌓인 원판들을 한 장씩 기둥에서 기둥으로 옮겨 최종적으로는 다른 기둥에 옮기는 것입니다.
단, 작은 원판 위에 큰 원판을 쌓을 수는 없습니다.
마우스로 드래그하여 원판을 옮겨 보세요.
하노이 타워 이야기
인도에 범천의 탑이라는 것이 있다고 합니다.
인도의 신인 범천이 우주 창조시에 만든 것이라는 말이 전해져 내려옵니다.
거기에는 세 개의 다이어몬드 기둥과 중심에 구멍이 있는 64장의 순금 원판이 있습니다.
원판은 모두 크기가 다르며 작은 쪽이 위가 되도록 기둥에 꿰어 있습니다. 처음 원판은 모두 한 기둥에 꿰어 있습니다.
여기에서 승려들의 일은 이 원판을 한번에 한 장씩 기둥에서 기둥으로 옮겨 최종적으로는 모두 세 기둥으로 옮기는 것입니다. 단, 작은 원판 위에큰 원판을 쌓을 수는 없습니다.
승려들은 밤낮으로 계속 움직였지만 아직 완성하지 못했습니다. 완성했을 때는 탑은 붕괴되고, 세계는 종말이 온다는 것입니다.
이상은 프랑스의 수학자 Edouard Lucas가 만든 이야기입니다.
원판의 최소 이동 횟수
n 장의 원판을 이동하기 위한 최소한의 이동 횟수 an는 다음과 같습니다.
64장 짜리 범천의 탑인 경우,
회의 이동이 필요합니다. 이것으로는 1회의 이동을 1초라고 해도 범천의 탑이 완성되어 우주의 종말이 오기까지 약 5880억년 정도 걸립니다.