21! = 510909??171709440000

 숫자 뒤에 붙는 !(느낌표)는 계승(factorial)으로서, 그 정의는

 n! = n*(n-1)*(n-2)*...*3*2*1

와 같이 주어진다. 가령 n=5라 하면, 5! = 5*4*3*2*1 = 120 이 된다.

 

 

 이제 본격적으로 문제.

 

누군가가 21!을 계산하였는데 중간의 일곱번째와 여덟번째, 두 자리가 보이지 않는 상태이다.

                       21! = 510909□□171709440000

 

계산기를 사용하지 말고, 빈 칸의 두 숫자를 맞추어보아라. 

 

출처 : 원본은 Cut-The Knot에서 발견한 문제이나, 입맛에 맞게 더 어렵게 꼬았다.

(http://www.cut-the-knot.org/Generalization/div9.shtml)

 

해답 

 빈 칸은 42가 된다.

 

 더글라스 애덤스의 소설 '은하수를 여행하는 히치하이커를 위한 안내서'에 나온 내용으로는, 사실 이 수는 삶, 우주, 그리고 모든 것에 대한 궁극적인 질문에 대한 해답이다. 물론 소설 한정으로.

물론 이걸 노리고 문제를 만든 것은 아니다.

 

 

 해설

  모두 계산하지 않고서 어떻게 빈 칸을 맞출 수 있을까?

 

여기서 사용할 아이디어는 바로 9배수 판정법과 11배수 판정법이다.

 

a = a_n10ⁿ + a_n-110^n-1 + ... + a₁10¹ + a₀  일 때,

 

-9배수 판정법

각 자리수의 합 a_n + a_n-1 + ... + a₁ + a₀ 이 9로 나누어지면 a도 9로 나누어지고, 그 역도 성립한다.

 

-11배수 판정법

각 자리수의 교대합 (-1)ⁿa_n + (-1)^n-1a_n-1 + ... -a₁ + a₀ 이 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가 된다.