하노이 탑 거듭제곱으로 풀다

  지구에서 달까지의 거리는 약 380,000km입니다. 종이 한장을 42번 접으면 달까지 도달할 수 있습니다. 이것은 오로지 수학적으로 가능하다는 말씀을 먼저 드립니다.

종이를 준비하고 정확히 반으로 접어 봅시다. 종이 한장 두께가 0.1mm, 반으로 접으면 종이가 2장이 되니 0.2mm가 됩니다. 다시 종이를 반으로 접는다면 이번에는 종이가 4장이 되어 0.4mm가 되겠지요. 또 반으로 접으면 0.8mm가 됩니다. 또 반으로 접으면 네 번째인데 종이의 두께는 1.6mm가 됩니다. 다섯번 째 접으면 3.2mm가 됩니다. 여섯번 째로 접으려고 하니 이젠 종이가 잘 접혀지지 않습니다. 그럼 종이를 접지 못하니 머리속으로 수학적으로 계산해야 합니다.

 한번 접으면 2장, 두 번 접으면 4장(2*2), 세번 접으면 8장(2*2*2), 네번 접으면 16장(2*2*2*2), 다섯번 접으면 32장(2*2*2*2*2), 여섯 번 접으면 64장(2*2*2*2*2*2), 일곱 번 접으면 128장(2*2*2*2*2*2*2), 여덟 번은 256장, 9번은 512장, 10번은 1024장, 11번은 2048장, 12번은 4096장, 13번은 8192장, 14번은 16,384장, 20번은 1,048,576장, 29번은 536,870,912장, 40번은 1,099,511,627,776장, 41번은 2,199,023,255,552장, 42번 접으면 4,398,046,511,104장이 됩니다. 

  종이 1장의 두께를 0.1m로 계산하면 42번 접었을 때 439,804,651,110.4mm가 됩니다. 이를 센티미터로 고치면 43,980,465,111.04cm가 됩니다. 이를 다시 미터로 고치면 439,804,651.1104m가 됩니다. 다시 킬로미터로 고치면 439,804.6511104km가 됩니다. 소숫점 이하 모두 지워버리면 439,804km가 됩니다. 

 즉 종이를 42번 접으면 그 종이는 지구에서 달까지 도달할 수 있다는 얘기가 됩니다.

  지구에서 태양까지의 거리는 약 150,000,000km입니다. 태양까지 가려면 몇 번을 접으면 될까요?

 43번 접으면 879,608km, 47번 접으면 14,073,728km, 50번 접으면 112,589,824km가 되네요. 아직 태양까지 가려면 약간 부족합니다. 그럼 한 번 더 접어보겠습니다. 51번 접었더니 225,179,648km입니다. 태양을 훨씬 지나친 거리입니다. 

 이것이 거듭제곱입니다. 2를 51번 접는다는 것은 2를 51번 곱하는 것입니다. 즉 2의 51승입니다. 이 거듭제곱의 원리를 처음 이야기 한 사람은 네덜란드 수학자 스테빈 입니다. 그후 데카르트가 거듭제곱의 표기 방식을 만듭니다. 지수를 밑 윗부분에 작게 쓰는 것을 만들었는데 이 방식은 지금까지 쓰여지고 있습니다.

  동양에서도 거듭제곱과 관련된 이야기가 있습니다. 고대 인도 브라만교 대사원에는 전설속의 하노이 탑이 존재했다고 합니다. 하노이 탑은 기둥이 세 개가 있고, 한 기둥에는 크기가 다른 둥근 원판 64개가 있었다고 합니다. 크기가 큰것은 아래에 있고, 작은 것은 위에 쌓여 있었습니다. 이 기둥을 다른 기둥에 옮기려면 조건이 있는데 원판을 한 번에 한 개씩 옮겨야 하고, 반드시 큰 원판 위에 작은 원판이 와야 한다는 것입니다. 작은 원판 위에 큰 원판을 올려 놓을 수 없습니다. 한 개의 원판을 옮기는 데 1초의 시간이 걸린다면 한 개의 탑에 있는 모든 원판을 다른 기둥에 옮기려면 얼마의 시간이 걸릴까요? 이 원판을 다 옮기고 나면 세상의 종말이 온다는 전설이 있는데 그 시간을 거듭제곱을 이용하여 풀 수 있습니다. 

  하노이 탑을 수학적으로 만든 사람은 프랑스의 수학자 루카스인데요. 우선 원판을 1개만 놓고 이동해 봅시다. 그럼 몇 번을 이동하면 될까요? 당연히 1번만 이동하면 됩니다. 그럼 원판이 2개가 있을 때는 몇 번 걸릴까요? 3번 걸립니다. 원판이 3개인 경우는 7번이 걸립니다. 원판이 4개인 경우는 15번이 걸립니다. 여기서 규칙성을 발견해 봅시다. 원판이 2개일 경우는 (2의 제곱)-1=3번이 됩니다. 원판이 3개인 경우는 (2의 세제곱)-1=7번입니다. 원판이 4개인 경우는 (2의 네제곱)-1=15번이 됩니다. 그럼 하노이 탑 64개의 원판을 모두 옮기려면 (2의 64제곱)-1이 됩니다. 계산하면 약 1,845경번을 옮겨야 다른 기둥에 모두 원판을 옮길 수 있습니다. 그럼 1번 옮기는데 걸리는 시간이 1초라면 약 1,845경 초가 되겠습니다. 이것을 계산하면 약 5,850억년이 지나야만 하노이 탑을 모두 옮길 수 있습니다. 어마어마한 시간이 걸리네요. 지구의 나이가 약 45억년이므로 세상의 종말이 오려면 아직도 한참 남았으니 걱정하지 않아도 됩니다.