원반 n개를 옮기려면 먼저 위쪽 n − 1개를 치우고, 가장 큰 원반을 한 번 옮긴 뒤, 그 n − 1개를 다시 위에 얹어야 합니다. 따라서 M(1) = 1일 때 M(n) = 2M(n − 1) + 1이고, 그 해는 2ⁿ − 1입니다. 원반 여덟 개에는 255수, 세 개에는 7수가 필요하며 앞의 두 링크가 그것입니다. 255는 메모리 크기를 읽는 사람이라면 누구나 아는 수입니다. 부호 없는 바이트가 담을 수 있는 최댓값이며, 정확히 이 이유 때문입니다.
뤼카의 버전은 황금 원반 예순네 개와, 그 탑을 다 옮기면 세상이 끝난다는 예언을 함께 들고 왔습니다. 초당 한 수라면 2⁶⁴ − 1 = 1.844674407371⋅10+19수(세 번째 링크)이고, 약 5850억 년, 우주 나이의 마흔 배가 넘습니다. 그런데 눈앞의 원반 여덟 개 짜리 퍼즐은 1분 반이면 끝납니다. 작은 경우를 사소하게 만드는 것과 같은 두 배가 큰 경우를 지질학적 규모로 만들며, 지수함수의 뜻은 전부 여기에 있습니다. 255와 1.844674407371⋅10+19는 예순 단계만큼 떨어진 같은 규칙입니다.
답
255
읽는 방법
작업대의 2⁸ − 1입니다. 두 번째 링크는 원반 세 개이고, 세 번째는 세상을 끝내는 원반 예순네 개의 셈입니다.
출처
Édouard Lucas marketed the Tower of Hanoi in 1883 as the towers of Brahma at Benares; the minimum for n disks is 2ⁿ − 1, forced by the recurrence M(n) = 2M(n − 1) + 1
계산기에서 풀어 보기
이 링크는 이 문제의 숫자가 이미 입력된 알맞은 계산기를 엽니다. 위 줄은 화면에 표시되어야 하는 내용입니다. 직접 확인하세요.