네가미 세이야 지음 서혜영 옮김 출판사 해나무

1. 하노이탑

동판에 막대가 세 개 있고, 크기가 서로 다른 4 개의 원판이 한 막대에 꽂혀 있다. 이 때, 다음과 같은 규칙으로 원판을 다른 막대로 모두 옮기는 놀이를 생각해 봅시다.

(1) 한 번에 한 개의 원판만을 옮긴다.

(2) 크기가 큰 원판은 반드시 크기가 작은 원판 아래쪽에

있어야 한다.

(출처 : '하노이 탑 문제' - 네이버 지식iN)


2.

"그렇다면 64단짜리 하노이의 탑의 답은 원판을 몇 번 이동해야 나올지 알고 있겠지?"
"녜 부념ㅇ 2^64입니다. 아니 2^64 - 1번 이었나?"
"어느 쪽이든 큰 차이는 없어. 2^64이라는 값에 비한다면 1따위는 오차범위일 테니까"
"그렇군요"
"어디 2^64이 어느 정도의 수인지 전자계산기로 계산해 볼까?"
들고 있던 전자계산기를 두드리자, 다음과 같은 답이 나왔다.
1.84467440737X10^19

이걸 보는 것 만으로는 2^64의 크기를 실감할 수 없다. 그렇다면 전설의 하노이의 스님들이 하고 있듯이 하루에 하나씩 움직인다고 치고 몇 년이 걸릴지 계산해보자. 윤년 같은 것은 신경쓰지 말고 1년을 365일로 계산하면 ,
5.05390248595X10^16년
이 되는데, 여전히 현실감이 없는 수치다. 그래서 1초에 하나씩 움직이는 것으로 해보면
2^64 / (365 X 24 X 60 X 60) = 584942417355 년
이 된다. 나아가 컴퓨터 상으로 가상적으로 조작한다는 가정 아래 하나를 1/100초에 움직인다고 쳐서 다시 100으로 나누면

5849424173.55년

이 된다.
"58억년!"
"으음, 지구가 탄생한 지 46억년 됐다고들 하니까, 그것봐도 시간이 더 걸린다는 얘기네, 뭐 우주의 나이보다는 짧긴 하지만 말야"

3.
A. 64단의 하노이탑을 다 이동하는 데는 2^64 -1 만큼의 이동 횟수가 필요하다.
B. 하노이 탑이 n번 이동(정확하게 정답대로) 되었을 때 각 기동의 원판은 어떤 상태일까?

이것이 이 소설의 수학적 구조입니다. 답도 소설 마지막 부분에 상세히 나옵니다.