와 같이 주어진다. 가령 n=5라 하면, 5! = 5*4*3*2*1 = 120 이 된다.
이제 본격적으로 문제.
누군가가 21!을 계산하였는데 중간의 일곱번째와 여덟번째, 두 자리가 보이지 않는 상태이다.
21! = 510909□□171709440000
출처 : 원본은 Cut-The Knot에서 발견한 문제이나, 입맛에 맞게 더 어렵게 꼬았다.
빈 칸은 42가 된다.
더글라스 애덤스의 소설 '은하수를 여행하는 히치하이커를 위한 안내서'에 나온 내용으로는, 사실 이 수는 삶, 우주, 그리고 모든 것에 대한 궁극적인 질문에 대한 해답이다. 물론 소설 한정으로.
물론 이걸 노리고 문제를 만든 것은 아니다.
모두 계산하지 않고서 어떻게 빈 칸을 맞출 수 있을까?
여기서 사용할 아이디어는 바로 9배수 판정법과 11배수 판정법이다.
a = an10n + an-110n-1 + ... + a1101 + a0 일 때,
-9배수 판정법
각 자리수의 합 an + an-1 + ... + a1 + a0 이 9로 나누어지면 a도 9로 나누어지고, 그 역도 성립한다.
-11배수 판정법
각 자리수의 교대합 (-1)nan + (-1)n-1an-1 + ... -a1 + a0 이 11로 나누어지면 a도 11로 나누어지고, 그 역도 성립한다.
출처 : http://www.cut-the-knot.org/Generalization/div11.shtml
이제 첫번째 빈 칸에 들어갈 수를 x, 두번째 빈 칸에 들어갈 수를 y라고 하자.
즉, 21! = 510909xy171709440000
계승의 정의에 의해 21!은 9도 곱해져있고, 11도 곱해져 있으므로, 9배수 판정법과 11배수 판정법을 모두 쓸 수 있다.
그러면, 5+1+...+x+y+...+0 = 57+x+y 는 9의 배수
또한, -5+1-...-x+y-...+0 = 35-x+y 는 11의 배수이다.
모듈러 산술로 나타내면,
57+x+y ≡ 0 (mod 9) -> x+y ≡ 6 (mod 9)
35-x+y ≡ 0 (mod 11) -> x-y ≡ 2 (mod 11)
가 된다.
이 쯤이면 대강 짐작할 수 있다. 모듈러 산술을 무시하면, 더해서 6이고 빼서 2인 두 숫자는 4와 2이다.
이 짐작이 정확하다는 것을 보이자.
x와 y 모두 0에서 9 사이에 있는 정수이므로 두 수의 차 x-y의 절대값은 커봐와 9를 넘지 못한다.
따라서 x-y는 mod 11로 2일 뿐 아니라 실제로 2가 된다.
x-y = 2. y를 옮기면, x = y+2
이를 첫 식에 대입하면, x+y ≡ y+2+y ≡ 2y+2 ≡ 6 (mod 9)
2와 9는 서로소이므로 양변을 2로 나눌 수 있다. 그러면, y+1 ≡3 (mod 9)
위 식을 만족하는 한 자리수 y는 2밖에 없다. ∴ y = 2.
∴ x = y+2 = 2+2 = 4
고로 가려진 두 숫자는 순서대로 42가 된다.
