Problems and Solutions #011

Problem #011

$1$부터 $5$까지의 숫자가 적힌 리스트가 있다고 하자. 이 리스트에서 두개의 숫자 $a$, $b$를 뽑아 $a$와 $b$는 리스트에서 지운 후, 대신에 $ab+a+b$를 계산하여 리스트에 다시 포함시킨다. 예를 들어 두개의 숫자 $3$과 $4$를 뽑았다면, 리스트에서 $3$과 $4$를 지우고 대신에 $3 \cdot 4 + 3 + 4 = 19$를 포함시켜 리스트에는 숫자 $1$, $2$, $5$, $19$만이 남게 된다. 이러한 과정을 $4$번 반복하면 리스트에는 최종적으로 단 하나에 숫자만이 남게 되는데, 이 때 이 숫자는 숫자를 뽑는 순서와 상관 없이 언제나 $719$가 된다. 이를 증명하여라.

만약에 리스트에 $1$부터 $100$까지의 숫자가 있었다면, 최종적으로 남는 숫자는 무엇이 될까?

리스트에서 뽑은 두개의 숫자를 $a$, $b$라 하자. 그러면 다음의 식이 성립한다.

\[ (a+1)(b+1) = ab + a + b + 1 \]

즉, $a$, $b$를 $ab + a + b$로 바꾸더라도, 리스트에 적힌 숫자들에 각각 $1$을 더하여 모두 곱해준 값은 변하지 않는다. 따라서 최종적으로 남은 숫자를 $N$이라 하면,

\[ N + 1 = (1+1)(2+1)(3+1)(4+1)(5+1) = 720 \]

따라서 $N$은 언제나 $719$가 됨을 알 수 있다.

이제 위 사실을 $1$부터 $100$까지의 숫자가 적힌 리스트에 적용해보자. 최종적으로 남은 숫자를 $N$이라 하면, 이 숫자는 언제나

\[ N = \prod_{n=1}^{100}(n+1) - 1= 101! - 1 \]

이 된다.

좀 더 일반적으로 $a_1$부터 $a_k$까지 $k$개의 숫자가 적힌 리스트가 있을때, 문제에 서술되어 있는 과정을 $(k-1)$회 반복하여 최종적으로 남는 숫자 $N$의 값은

\[ N = \prod_{n=1}^{k}(a_n+1) - 1 \]

로 주어진다.