2의 29승은 아홉자리 숫자로, 서로다른 9개의 숫자로 이루어져있다고 한다. 0~9중 쓰이지 않은 숫자는 무엇일까?
Peter Winkler의 Mathematical Mind-Bender에서 가지고 왔습니다.
(원출처 : E. Berlekamp, J.P. Buhler(1990-2007). "Puzzle Column." Emissary)
2^29 = 536870912 이므로 답은 4.
계산기 없이 이 퍼즐을 푸는 방법은 바로 9배수 판정법 원리에 있다.
9배수 판정법:
각 자리의 숫자를 더한 수가 9배수라면 원래 수도 9배수이다.
예시) 3456의 각 자리 숫자를 더하면 3+4+5+6=18, 9배수이다. 실제로 3456=9×384이다.
퍼즐을 풀기 위해서는 결과를 조금 확장해야한다.
정리
각 자리의 숫자를 더한 수를 9로 나눈 나머지는 원래수를 9로 나눈 나머지와 같다.
예시) 8547의 각 자리 숫자를 더하면 8+5+4+7=24, 9로 나눈 나머지는 6이다. 또한 8547를 9로 나눈 나머지도 6이다.(8547=9×949+6)
0부터 9가지 모두 더하면 9배수인 45가 되기 때문에 x가 쓰이지 않은 숫자라면 9로 나눈 나머지는 9-x가 된다.
예시)
124567890 ≡ 1+2+4+5+6+7+8+9+0 = 45-3 ≡ -3 ≡ 6 (mod 9)
124567890 = 9×13840876+6
그렇기때문에, 2의 29승을 9로 나눈 나머지만 구하면 해결된다.
2^29 = 2^(2+3×9) = (2^2)×(2^3)^9 = 4×(8^9) ≡ 4×((-1)^9) = -4 ≡ 5 (mod 9)
따라서 쓰이지 않은 숫자는 4라고 이야기할 수 있다.
