하노이의 탑은 오래된 전설이 있는 놀이처럼 보이지만, 만들어진 것은 19세기 말이에요. 생각해 낸 사람은 프랑스의 수학자 에두아르 뤼카(1842~1891년)였어요.
1883년, 가명으로 나온 퍼즐
하노이의 탑은 1883년 프랑스에서 판매되었어요. 상자에 적힌 만든 사람의 이름은 “N. 클라우스 드 시암 교수”. 이것은 뤼카의 장난기로, “Claus de Siam(클라우스 드 시암)“의 글자를 재배열하면 “Lucas d’Amiens(아미앵의 뤼카)“가 돼요. 아미앵은 뤼카가 태어난 도시예요.
뤼카는 피보나치 수와 비슷한 “뤼카 수”와, 큰 수가 소수인지 확인하는 방법의 연구로 알려진 수학자예요. 수학을 즐기기 위한 놀이에도 열심이어서, 하노이의 탑 말고도 여러 가지 퍼즐과 수 놀이를 소개했어요.
금 원판 64개의 전설
하노이의 탑에는 다음과 같은 전설이 곁들여져 퍼졌어요.
인도의 베나레스에 있는 사원에는 다이아몬드 바늘이 3개 서 있고, 그중 1개에 금 원판 64개가 쌓여 있다. 승려들은 밤낮없이 쉬지 않고 규칙에 따라 원판을 계속 옮기고 있다. 모든 원판을 다 옮기는 날, 세상은 끝난다.
이 전설은 오래전부터의 이야기가 아니라 퍼즐을 내놓을 무렵에 만들어진 것으로 여겨져요. 그래도 원판 64개를 옮기는 데 걸리는 시간을 계산해 보면 전설이 조금도 과장이 아니라는 것을 알 수 있어요(원판 64개를 옮기면 몇 년이 걸릴까?).
왜 “하노이”일까
하노이는 베트남의 수도이지만, 퍼즐 자체와 베트남의 관계는 알려져 있지 않아요. 내놓았던 당시는 프랑스가 베트남 북부로 진출하던 시기였어요. 먼 이국의 울림이 있는 이름으로 붙였다고 여겨져요. 전설의 무대가 인도라서 “브라흐마의 탑”이라고 부르기도 해요.
기둥 4개의 변형
기둥을 4개로 늘리면 어떻게 될까요? 영국의 퍼즐 작가 헨리 듀드니는 1907년의 책에서 이 문제를 “리브의 퍼즐”로 소개했어요. 기둥이 1개 늘 뿐인데 수가 확 줄어요.
그런데 기둥이 4개일 때의 가장 적은 수를 구하는 방법은 오랫동안 증명되지 않았어요. 흔히 쓰는 풀이(프레임-스튜어트 알고리즘)가 정말 최소인지는 2014년에 와서야 밝혀졌어요. 기둥 3개라면 식 하나로 끝나는데, 4개가 되면 100년 넘는 난제가 된 거예요. 자세한 내용은 기둥이 4개인 하노이의 탑에서 소개해요.
작은 기둥과 원판뿐인 놀이에 수학의 깊은 문제가 숨어 있어요. 하노이의 탑이 140년 넘게 계속 사랑받는 데는 그런 이유도 있는지 몰라요.
