프로젝트 오일러 78번

Let \(p(n)\) represent the number of different ways in which \(n\) coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so \(p(5)=7\).

OOOOO

OOOO   O

OOO   OO

OOO   O   O

OO   OO   O

OO   O   O   O

O   O   O   O   O

Find the least value of \(n\) for which \(p(n)\) is divisible by one million.

---

\(n\) 개의 동전을 각기 다른 방법으로 그룹 짓는 방법의 수를 \(p(n)\) 이라 하자. 예를 들어 5개의 동전에 대해서는 위 그림과 같이 7개의 서로다른 그룹핑 방법이 있다. 따라서 \(p(5)=7\) 이 된다.

\(p(n)\) 이 \(10^6\) 으로 나누어 떨어지게 되는 \(n\) 의 최솟값을 구하시오. 

 

이 문제 역시 76번과 동일한다. 다만 경우의 수가 \(10^6\) 으로 나누어 떨어져야 한다니 엄청나게 큰 수가 나올 것임은 분명하다. 사실 이 문제는 76번과 동일한 방법으로 \(n\)을 늘려가면서 구하면 답을 얻어낼 수 있다. 다만 시간이 많이 걸린다는 것이 단점이다. 따라서 이 문제를 좀 더 수학적으로 접근한다면 빠른 시간안에 답을 찾아낼 수 있다. 이래서 프로그래머는 수학을 잘 해야 한다는 얘기가 나오는가보다.

이 문제를 풀기 위해서 필요한 수학적 내용들을 알기 쉽게 차례대로 정리해 보자.

 

\(\left ( 1 + x+x^2+x^3+\cdots \right ) \left ( 1 +x^2 +x^4 + x^6+\cdots \right ) \left ( 1 + x^3 + x^6 +x^9+ \cdots \right ) \cdots \) 의 전개식에서 \(x^n\) 의 계수는 위 문제에서 말하는 \(p(n)\) 이 된다.

 

예를 들어, \(x^4\) 의 계수를 생각해보자.

\(x^4 \times 1 \times 1 \times 1\) 은 \(1+1+1+1=4\) 로 생각할 수 있고,

\(x^2 \times x^2 \times 1 \times 1\) 은 \(1+1+2=4\) 로

\(x \times 1 \times x^3 \times 1\)은 \(1+3=4\) 로

\(1 \times x^4 \times 1 \times 1\) 은 \(2+2=4\)로

\(1 \times 1 \times 1 \times x^4\) 은 \(4=4\) 로 생각할 수 있다.

(위의 내용이 잘 이해가 가지 않는다면 공비가 \(x\)인 첫번째 괄호안의 전개식은 \(1\)씩 더해지는 것으로, 공비가 \(x^2\)인 두 번째 괄호안의 전개식은 \(2\) 씩 더해지는 것으로, 공비가 \(3\) 인 세 번째 괄호안의 전개식은 \(3\) 씩 더해지는 것으로 생각하면 이해할 수 있다. 물론 그 이후에도 계속 이런 방식으로 생각하면 된다.)

따라서 다음의 식이 성립한다.

\[ \begin{split} \sum \limits_{n=0}^{\infty} p(n)x^n &= \left ( 1+x+x^2+\cdots \right ) \left ( 1+x^2+x^4\cdots \right ) \left ( 1+x^3 +x^6 \cdots \right ) \cdots \\ &= \dfrac{1}{1-x} \cdot \dfrac{1}{1-x^2} \cdot \dfrac{1}{1-x^3} \cdots  \\ &= \prod \limits_{k=1}^{\infty} \dfrac{1}{1-x^k} \end{split} \]

(제1행에서 제2행으로 넘어갈때는 무한등비급수의 합공식을 사용한 것임)

 

이제 우리는 \( \left (1-x \right ) \left ( 1-x^2 \right ) \left ( 1-x^3 \right ) \cdots\) 가 어떻게 전개되는지 알아보면 된다.

주의 깊게 볼 것은 상수 1의 부호만 + 이고 나머지 \(x^n\) 의 부호는 - 라는 것이다.

 

상수항은 볼 것도 없이 1이 되고,

 

\(x\) 항의 경우 \( 1 \times (-x)\) 밖에 안되므로 \(-x\) 가 된다.

 

\(x^2\) 항 역시 \(1 \times \left (-x^2 \right )\) 밖에 안되므로 \(-x^2\) 이 된다.

이때, 왜 \(x \times x\) 는 고려하지 않느냐는 의문을 갖겠지만, 식을 보면 \(x\) 항은 하나 밖에 존재하지 않기 때문에 \(x \times x\) 가 되는 것은 불가능하다.

 

\(x^3\) 항은 \(1 \times \left (-x^3 \right ) \) 도 되지만 \( (-x) \times \left ( -x^2 \right )\) 도 되므로 \(-x^3 + x^3 =0\) 이 되어 사라진다.

여기서부터 신경써서 봐야 할 것이 있다.

\(3\) 을 서로 다른 음이 아닌 정수들의 합으로 나타내는 방법은 두 가지 밖에 없다. \(1+2\) 혹은 그냥 \(3\) 이 된다. 위에서 언급했던 대로 \(x^n\) 의 앞에는 - 부호가 붙어 있기 때문에 \(1+2\) 처럼 짝수 개의 서로 다른 음이 아닌 정수의 합으로 \(3\) 을 나타내면 \(x^3\) 의 부호는 + 가 되고, \(3\) 처럼 서로다른 (이 경우는 아니지만) 홀수 개의 음이 아닌 정수들의 합으로 \(3\)을 나타내면 \(x^3\) 의 부호는 -가 된다.

 

그렇다면 \(x^4\)의 부호는 금방 알아낼 수 있다. 서로 다른 음이 아닌 정수들을 이용하여 \(4\) 를 나타내는 방법은 \(1+3, \;4\) 두 가지 밖에는 없다. \(1+3\) 은 짝수 개의 음이 아닌 정수들의 합으로 \(4\)를 나타냈으므로 부호가 +, \(4\) 는 홀수 개의 정수로 \(4\) 를 나타냈으므로 부호는 - 가 된다. 따라서 \(x^4\) 항도 사라지게 된다. 이때도 \(x^2 \times x^2\) 으로 \(x^4\) 을 나타내는 것은 불가능함을 알아야 한다.

 

 \(x^5\) 의 경우는 \(1+4,\; 2+3,\; 5\) 로 표현이 가능하고 이 중 짝수 개의 서로 다른 음이 아닌 실수로 나타낸 것이 \(2\)개, 홀수 개의 서로 다른 음이 아닌 실수로 나타낸 것이 \(1\) 개이기 때문에 \(x^5 + x^5 - x^5\) 이 되어 \(x^5\) 이 된다. 이것을 Ferrers diagram을 이용하여 생각해 보자.

 

○○○○○

○○○○ ○

○○○ ○○

 

왼쪽 다이어그램은 \(5\) 를 중간 다이어 그램은 \(1+4\)를 오른쪽 다이어그램은 \(2+3\) 을 나타낸다.

이 중 왼쪽과 중간 다이어 그램을 보면 왼쪽 다이어그램에서 가장 오른쪽 동그라미 하나를 아랬줄로 내리면 중간 다이어그램이 되는데, 이것은 \(5\) 를 홀 수개의 수와 짝수 개의 수로 표현할 수 있음을 나타내므로 둘의 부호가 - 와 + 가 되어 서로 상쇄된다. 따라서 남는 것은 오른쪽 다이어그램이 되고, 오른쪽 다어이그램은 \(2+3\)으로 \(5\) 를 나타냈으므로 짝수 개가 되어 전개식에서 \(x^5\)항은 \(+x^5\) 이 되는 것이다.

 

\(x^6\) 의 경우도 Ferrers diagram으로 나타내면  

 

○○○○○○

○○○○○ ○

○○○○ ○○

○○○ ○○ ○

 

 가 된다. 이 중 왼쪽 두 개와 오른쪽 두 개의 다이어그램이 서로 짝꿍이 되어 상쇄시키므로 전개식에서 \(x^6\) 은 등장하지 않게 된다.

 

\(x^7\) 의 경우는

 

○○○○○○○

○○○○○○ ○

○○○○○ ○○

○○○○ ○○ ○

○○○○ ○○○

 

\(7\)과 \(1+6\) 이 짝꿍, \(2+5\)와 \(1+2+4\)가 짝꿍이 되어 상쇄되므로 남는 것은 \(3+4\) 가 된다. 따라서 \(x^7\) 의 부호는 + 가 된다.

 

이제 이 과정을 좀 더 확장해서 생각해 보자.

\(n=20\) 인 경우 \(20=7+6+4+3\) 인 경우를 Ferrers diagram으로 나타내면 다음과 같다.

 

 

이때, 오른쪽 위에서부터 \(45^o\) 남서쪽 방향으로 내려올 수 있는 것이 어디까지인가 살펴보면, 그림에서 빨간색으로 표현되었듯이 위에서 부터 두 줄까지이다. 이때, 맨 아랫줄에 놓여 있는 동그라미 개수를 \(m\) 이라고 하면 위의 경우에 \(m=3\) 이 됨을 알 수 있고, 대각선으로 내려올 수 있는 빨간공의 개수를 \(s\) 라고 하면 이 경우 \(s=2\)임을 알 수 있다. \(m>s\) 이면 이 두 개의 빨간색 동그라미를 떼어 낸 후, 맨 아랫줄에 붙일 수가 있는데, 그 그림은 다음과 같다.

 

 

이것이 나타내는 의미는 \(7+6+4+3\)의 네 개(짝수 개)의 숫자로 \(20\)을 표현했던 것을 \(6+5+4+3+2\)의 다섯 개(홀수 개)의 숫자로 표현할 수 있다는 것이다. 아랫쪽 그림에서 마지막 행을 다시 제1행과 제2행의 마지막에 하나씩 붙이면 다시 첫 번째 그림을 얻게 된다. 즉, 이렇게 둘은 서로 짝꿍이 되어 \(x^20\) 항을 상쇄시킨다.

 

이런 짝꿍들을 찾아낼 수 없는 경우가 두 가지가 있는데,

첫 번째는 \(m=s\) 인 경우이다.   

 

위 그림은 \(m=s=3\) 인 경우를 보여준다. 이 경우는 아랫쪽에 빨간 공들을 위쪽 행의 마지막에 가져다 붙이는 것이 불가능하고, 혹여 \(3\) 개 중 \(2\) 개만 가져다 붙인다고 하면

 

 

가 되는데, 이 경우 행의 개수의 변화가 없기 때문에 부호가 서로를 상쇄시키지 못하게 된다. 따라서 짝꿍이 될 수 없다.

\(m=s\) 인 경우는 \[n=m+(m+1)+(m+2)+\cdots+(2m-1)=\dfrac{m(3m-1)}{2}\] 이 되고 \(x^n\)의 부호는 \((-1)^m\) 이 되는 것을 알 수 있다.

 

두 번째는 \(m=s+1\) 인 경우이다.

 

 

위 그림은 \(m=4,\; s=3\) 인 경우이다. 오른쪽 대각선에 해당하는 빨간 동그라미들을 맨 아래줄에 추가하면 마지막 두 줄이 모두 동그라미가 \(3\) 개가 되어 서로 다른 정수 조건에 위배된다. 따라서 이 경우도 짝꿍을 찾을 수가 없게 된다.

\(m=s+1\) 인 경우는 \[n=m+(m+1)+(m+2)+\cdots+(2m-2)=\dfrac{(m-1)(3m-2)}{2}\] 가 되고 \(x^n\) 의 부호는 \((-1)^s=(-1)^{m-1}\) 이 된다. 이때 \(s=m-1=-k\)라고 한다면 \(n=\dfrac{(m-1)(3m-2)}{2}=\dfrac{k(3k-1)}{2}\) 가 되고, \(x^n\) 의 부호는 \((-1)^k\)이 된다.

 

위의 내용을 정리해보면 결국 남는 것은 \(m\) 이 자연수일 때, \(n=\dfrac{m(3m-1)}{2}\), 그리고 \(n=\dfrac{k(3k-1)}{2}\; (단, k=1-m)\) 이 된다. 나머지는 짝꿍들 때문에 다 상쇄된다.

 

따라서 \(m=1\) 일 때,

\(\dfrac{m(3m-1)}{2}=1\) 이므로 \((-1)^1 x^1=-x\)와

\(k=1-m=0\) 에서 \(\dfrac{k(3k-1)}{2}=0\) 이므로 \((-1)^0 x^0=1\) 이 남는다.  

 

\(m=2\) 일 때,

\(\dfrac{m(3m-1)}{2}=5\) 이므로 \((-1)^2 x^5=x^5\)와

\(k=1-m=-1\) 에서 \(\dfrac{k(3k-1)}{2}=2\) 이므로 \((-1)^{-1} x^2=-x^2\) 이 남는다.  

 

\(m=3\) 일 때,

\(\dfrac{m(3m-1)}{2}=12\) 이므로 \((-1)^3 x^{12}=-x^{12}\)와

\(k=1-m=-2\) 에서 \(\dfrac{k(3k-1)}{2}=7\) 이므로 \((-1)^{-2} x^7=-x^7\) 이 남는다.  

 

\(m=4\) 일 때,

\(\dfrac{m(3m-1)}{2}=22\) 이므로 \((-1)^4 x^{22}=x^{22}\)와

\(k=1-m=-3\) 에서 \(\dfrac{k(3k-1)}{2}=15\) 이므로 \((-1)^{-3} x^{15}=-x^{15}\) 이 남는다.  

\(\vdots\)

 

따라서 다음이 성립한다.

\[(1-x)\left (1-x^2 \right ) \left ( 1-x^3 \right ) \cdots = 1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+x^{26}- \cdots\]

 

결국 우리가 얻는 식은 다음과 같다.

\[\sum \limits_{n=0}^{\infty} p(n) x^n = \prod \limits_{n=1}^{\infty} \left (1-x^n \right )^{-1}\]

\[\left ( \sum \limits_{n=0}^{\infty} p(n) x^n \right ) \cdot  \left ( \prod \limits_{n=1}^{\infty} \left ( 1-x^n \right ) \right )=1\]

이 때, \( \prod \limits_{n=1}^{\infty} \left (1-x^n \right ) = \sum \limits_{n=0}^{\infty} a_n x^n\) 이라고 하면

\[\left ( \sum \limits_{n=0}^{\infty} p(n) x^n \right ) \cdot  \left ( \sum \limits_{n=0}^{\infty} a_n x^n \right )=1\]

\[\left (p(0)+p(1)x+p(2)x^2+p(3)x^3+\cdots \right ) \cdot \left ( 1-x-x^2+x^5+x^7-\cdots \right ) =1\]

이 된다.

따라서 \(p(0)=1\) 이 되고 \( p(n)=\sum \limits_{i=1}^{n} p(n-i)a^i=0\; (n \ge 1)\) 에서 \[\begin{split} p(n)&= \sum \limits_{i=1}^{n} p(n-i)a^i \\ &= p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+\cdots \end{split}\] 가 된다.

 

78번 문제는 위의 \(p(n)\) 을 이용하면 빠르게 답을 구할 수 있다.