하노이의 탑에는 이런 전설이 전해져요. 인도의 어느 사원에 금 원판 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개인 것도 그래서예요.
