고대 인도 베나레스의 한 사원에는 세상의 중심을 나타내는 돔이 있고 그 안에 다이아몬드 기둥 3개가 세워져 있다. 기둥 중 하나에는 순금으로 된 64개의 원판이 크기가 큰 것부터 아래에 놓이도록 차례로 쌓여 있다. 승려들은 원판을 다른 기둥으로 한 번에 한 개씩 옮기는데, 절대로 작은 원판 위에 큰 원판을 올려 놓아서는 안 된다. 64개의 원판이 다른 한 기둥으로 모두 옮겨지면 세상이 종말을 맞이한다고 여겼다.
위 글은 프랑스의 수학자 루카스가 발표한 하노이의 탑 퍼즐이다. 루카스는 규칙에 맞게 원판을 옮기는 것은 매우 오래 걸리는 일임을 말하고자 했다. 실제로 모든 원판을 다른 기둥으로 옮기는 데는 1초에 원판 한 개씩 옮겨도 5,800억년이 넘게 걸린다.
하노이의 탑은 직접 해 보는 것이 중요하다. 인터넷에서 쉽게 구입할 수 있고, 스마트폰 애플리케이션으로 해 봐도 좋다. 원판의 개수가 적은 것부터 직접 옮겨봐서 규칙을 찾아보면 원판이 1개가 있으면 1번만 옮기면 된다. 원판이 2개이면 위에 있는 원판을 가운데로 옮겨놓고, 큰 원판으로 오른쪽으로 옮긴 후 작은 원판을 오른쪽으로 옮기면 총 3번을 옮겨야 한다. 원판 3개, 4개일 때는 각각 7번, 15번에 모두 옮길 수 있다.
실제 옮겨보고 알아낸 횟수를 차례로 적어보면 원판이 1에서 하나씩 늘 때 각각 1, 3, 7, 15번이다. 옮기는 횟수가 2, 4, 8씩 늘어 2의 거듭제곱만큼 증가하는 규칙을 발견할 수 있다. 수에 관한 관찰력이 뛰어나다면 원판의 수가 n일 때 2의 n제곱-1번만큼 옮겨야 한다는 것을 알 수 있다.
그런데 개수를 바꾸어가며 하노이의 탑을 반복하다 보면 같은 생각을 반복하고 있다는 것을 발견하게 된다. 4개의 원판을 옮길 때는 "3개를 모두 가운데에 옮겨놓아야 4번째 원판을 오른쪽으로 옮길 텐데", 5개의 원판을 옮길 때는 "4개를 모두 가운데에 옮겨놓아야 5번째 원판을 오른쪽으로 옮길 텐데"하고 생각하는 것. 즉 n개의 원판을 오른쪽에 옮기기 위해서는 (n-1)개의 원판을 가운데로 옮겨 놓아야 한다. 그리고 다시 (n-1)개의 원판을 오른쪽으로 옮기게 된다. 따라서, n개를 옮기는 횟수=(n-1)개를 옮기는 횟수×2+1이 된다.
원판 하나 하나의 움직임에도 규칙이 있다. 가장 큰 원판은 오른쪽 기둥으로 1번만 움직인다. 바로 위 원판은 가운데로 옮겼다가 오른쪽으로 옮기기 때문에 2번을 움직인다. 그 위 원판은 바로 아래의 원판이 움직일 때마다 2번씩 움직이기 때문에 4번을 움직인다. 그래서 원판을 모두 옮기는 횟수를 원판 각각을 중심으로 생각하면 다음과 같다.
n개를 옮기는 횟수=1+2+4+⋯+2의 (n-1)제곱
하노이의 탑은 원판을 옮겨 보는 것만으로도 논리력을 기를 수 있고, 횟수 간 관계에 여러 가지 규칙이 있는 퍼즐이다.
천종현 소마사고력수학연구소장
기사 URL이 복사되었습니다.
댓글0