하노이의 탑에는 이런 전설이 전해져요. 인도의 어느 사원에 금 원판 64개를 쌓은 탑이 있고, 승려들이 규칙대로 원판을 계속 옮기고 있다. 전부 다 옮기는 날, 세상은 끝난다――.

그렇다면 원판 64개를 옮기는 데는 정말 얼마나 걸릴까요?

최소 2⁶⁴−1번

원판이 n개일 때 최소 수는 2ⁿ−1번이에요(이유는 최소 수 기사에서 설명해요). 원판 64개라면,

2⁶⁴−1 = 18,446,744,073,709,551,615번

이에요. 한국어 단위로는 약 1845경 번이에요. 1조의 약 1845만 배예요.

1초에 1수씩 움직이면

승려가 쉬지 않고, 1초에 1수씩, 한 번도 틀리지 않고 움직였다고 해 봐요. 1년을 약 3155만 초(365.25일)로 놓고 나누면,

18,446,744,073,709,551,615초 ÷ 31,557,600초 ≒ 5845억 년

이 걸려요.

비교할 것햇수
원판 64개를 1초에 1수씩 옮기기약 5845억 년
우주가 생긴 뒤 지금까지약 138억 년
지구가 생긴 뒤 지금까지약 46억 년

우주 나이의 약 42배예요. 전설이 사실이라도 세상의 끝을 걱정할 필요는 없을 것 같아요.

컴퓨터라면 어떨까

사람 손이 아니라 1초에 10억 수를 계산할 수 있는 컴퓨터로 순서를 따라간다고 해 봐요. 그래도,

18,446,744,073,709,551,615 ÷ 1,000,000,000 ≒ 184억 초 ≒ 약 585년

이 걸려요. 한 수 한 수의 순서는 아주 단순한데, 원판이 늘어나면 수는 배로 배로 늘어나요. 이것이 “지수함수적으로 늘어난다”는 말의 알기 쉬운 예예요.

손으로 놀 수 있는 건 몇 개까지?

1초에 1수씩 움직이면, 최소 수 그대로라도 다음과 같은 시간이 걸려요.

원판 개수최소 수1초에 1수씩이면
7개127번약 2분
10개1,023번약 17분
15개32,767번약 9시간
20개1,048,575번약 12일

잠깐 쉬는 사이에 놀기에는 7개 안팎이 딱 좋은 길이예요. 앱 “하노이의 탑”의 기본이 7개인 것도 그래서예요.