프로젝트 오일러 100번

If a box contains twenty-one colored discs, composed of fifteen blue discs and six red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, \(\rm P(BB)=\dfrac{15}{21} \times \dfrac{14}{20} = \dfrac{1}{2}\)

The next such arrangement, for which there is exactly \(50%\) chance of taking two blue discs at random, is a box containing eighty-five blue discs and thirty-five red discs.

By finding the first arrangement to contain over \(10^{12} = 1,000,000,000,000\) discs in total, determine the number of blue discs that the box would contain. 

---

상자안에 파란색 디스크 15개와 빨간색 디스크 6개가 있다. 이 21개의 디스크 중 임의로 2개의 디스크를 추출할 때, 두 개의 디스크가 모두 파란색일 확률은 \(\rm P(BB)=\dfrac{15}{21} \times \dfrac{14}{20} = \dfrac{1}{2}\) 와 같다. 

상자안의 디스크 개수를 늘려 또 다시 둘 다 파란색 디스크가 나올 확률이 \(50%\) 가 되게 만들려면 차란색 디스크 85개와 빨간색 디스크 35개가 있어야 한다.

상자안의 전체 디스크의 개수가 \(10^{12}\) 개 이상 들어 있을 때, 추출한 두 개의 디스크가 모두 파란색일 확률이 \(50%\) 가 되려면 파란색 디스크의 개수가 최소 몇 개 있어야 하는가? 

전체 디스크의 갯수를 \(n\) 개, 이 중 파란색 디스크의 갯수를 \(d\) 라고 하면, 다음을 만족시켜야 한다.

\[{\rm P(BB)} =\; \dfrac{_d {\rm C}_2}{_n {\rm C}_2} = \dfrac{d(d-1)}{n(n-1)} = \dfrac{1}{2}\]

위의 식으로부터 \(n\)과 \(d\) 의 관계식을 도출하면 \[2d(d-1)=n(n-1)\] 

완전제곱식으로 만들면 \[2 \left ( d - \dfrac{1}{2} \right ) ^2 - \dfrac{1}{2} = \left ( n - \dfrac{1}{2} \right ) ^2 - \dfrac{1}{4}\]

양변에 \(4\)를 곱하여 정리하면 \[8 \left ( d - \dfrac{1}{2} \right )^2 = 4 \left (n - \dfrac{1}{2} \right )^2 +1\]

\[2 (2d-1)^2 = (2n-1)^2 +1\]

\(D=2d-1, \; N=2n-1\) 이라고 하면 

\[2D^2=N^2+1\]을 얻는다.

이 때, \(n, \; d\) 는 모두 정수이므로 \(n > 10^{12}\) 인 정수일 때, 위 식을 만족하는 최소 정수 \(d\) 를 찾으면 된다. 따라서 66번 문제에서 봤던 펠방정식의 풀이법을 적용하면 쉽게 답을 구할 수 있다.

\[ 2 = \dfrac{N^2 +1}{D^2}\]

\[\sqrt{2} = \dfrac{\sqrt{N^2+1}}{D} \approx \dfrac{N}{D}\]

위 식을 만족하는 자연수 \(D, \; N\) 은 결국 \(\sqrt{2}\) 의 근삿값을 나타내는 유리수의 분자와 분모가 된다고 생각할 수 있다. 이 근삿값은 이미 64번 문제에서 봤던 방법으로 연분수 전개를 통해 구할 수 있다.

\[ \begin{split} \sqrt{2} &= 1+\sqrt{2} -1 = 1 + \dfrac{1}{\dfrac{1}{\sqrt{2}-1}} = 1 + \dfrac{1}{\sqrt{2}+1} \\ &= 1+\dfrac{1}{2+\sqrt{2}-1}=1+\dfrac{1}{2+\dfrac{1}{\dfrac{1}{\sqrt{2}-1}}} = 1+\dfrac{1}{2+\dfrac{1}{\sqrt{2}+1}} \\ &= 1+\dfrac{1}{2+\dfrac{1}{2+\dfrac{1}{\sqrt{2}+1}}} = \cdots \end{split} \]

이 되므로, 이를 단계별로 계산하여 \(\sqrt{2}\) 의 근삿값을 찾아내면

\( \sqrt{2} \approx 1\)

\(\sqrt{2} \approx 1+ \dfrac{1}{2} = \dfrac{3}{2}\)

\(\sqrt{2} \approx 1+\dfrac{1}{2+\dfrac{1}{2}} = 1+\dfrac{2}{5} = \dfrac{7}{5}\)

\(\;\; \;\;\;  \;\; \vdots\)

이렇게 구한 근삿값을 나열해 보면

\[1, \;\; \dfrac{3}{2},\;\; \dfrac{7}{5}, \;\; \cdots\]

가 된다. 이 근삿값들을 \(\dfrac{N}{D}\)와 같다고 생각하여 조건을 만족시키는 최소의 정수 \(D\)를 찾으면 문제를 해결할 수 있다. 물론 이렇게 구한 \(D, \; N\) 으로 부터 \(d, \; n\) 을 구해내야 한다.

 

참고로 \(n=1,070,379,110,497\) 개 일 때 \(d=756,872,327,473\) 개가 조건을 만족시키는 답이 된다.