프로젝트 오일러 121번

A bag contains one red disc and one blue disc. In a game of chance a player takes a disc at random and its color is noted. After each turn the disc is returned to the bag, an extra red disc is added, and another disc is taken at random.

The player pays £1 to play and wins if they have taken more blue discs than red discs at the end of the game.

If the game is played for four turns, the probability of a player winning is exactly 11/120, and so the maximum prize fund the banker should allocate for winning in this game would be £10 before they would expect to incur a loss. Note that any payout will be a whole number of pounds and also includes the original £1 paid to play the game, so in the example given the player actually wins £9.

Find the maximum prize fund that should be allocated to a single game in which fifteen turns are played.

---

가방에 파란색 디스크 하나와 빨간색 디스크 하나가 들어 있다. 한 번의 시행에서 임의로 디스크 하나를 선택한 후, 그 디스크가 어떤 색이었는지 기록해 둔다. 매 시행이 끝나면 뽑았던 디스크는 다시 가방속에 넣고, 빨간색 디스크를 하나를 더 추가하여 가방에 넣는다. 다음 시행에서는 다시 임의로 디스크 하나를 선택하여 그 색깔을 기록한다. 게임 참가자는 참가비 1파운드를 내고, 정해진 횟수 만큼의 시행이 끝나면 시행에서 나온 파란색 디스크의 수가 빨간색 디스크의 수보다 많으면 게임에서 이기게 된다. 

만약 한 게임이 네 번의 시행으로 구성된다면 게임 참가자가 이길 확률은 \(\dfrac{11}{120}\)이 되고, 게임 주최자가 준비해야할 상금은 10파운드가 된다. (게임 주최자는 본인이 손해를 보지 않는 범위에서 상금의 최댓값을 결정한다.) 상금은 음이 아닌 정수이어야 하고 (물론 단위는 파운드 : £) 참가자가 게임에서 이겼을 경우 실제로 받게되는 상금은 9파운드가 된다. (왜냐하면 참가비를 1파운드를 냈으므로)

한 게임이 15번의 시행으로 구성된다면 게임 주최자가 준비해야할 상금의 최댓값을 구하시오.     

문제에서 \(n\) 번째 시행에서는 빨간 디스크가 \(n\) 개, 파란 디스크가 1개로 총 \(n+1\) 개의 디스크가 가방에 담겨 있게 된다. 따라서 \(n\) 번째 시행에서 빨간 디스크를 꺼낼 확률은 \(\dfrac{n}{n+1}\) 이고, 파란 디스크를 꺼낼 확률은 \(\dfrac{1}{n+1}\) 이 된다.  

15번의 시행에서 파란 디스크를 꺼낸 횟수가 빨간 디스크를 꺼낸 횟수보다 많아야 게임에서 이기므로, 파란 디스크를 꺼낸 횟수가 8~15회 이면 이기게 된다. 

이 문제는 1부터 15까지의 수 중, 8개를 combination 으로 추출하여 해당 시행에서는 파란 디스크를 뽑았다고 생각해야 한다. 따라서 combination에 의해 추출된 시행에 대해서는 확률 \(\dfrac{1}{n+1}\) 을 곱해주고, 해당하지 않는 시행에 대해서는 확률 \(\dfrac{n}{n+1}\) 을 곱해준다. 예를 들어, 1, 3, 4, 5, 8, 11, 12, 14 회에 파란 구슬이 뽑혔다고 생각한다면 확률은 \[\dfrac{1}{2} \times \dfrac{2}{3} \times \dfrac{1}{4} \times \dfrac{1}{5} \times \dfrac{1}{6} \times \dfrac{6}{7} \times \dfrac{7}{8} \times \dfrac{1}{9} \times \dfrac{1}{10} \times \dfrac{1}{11} \times \dfrac{11}{12} \times \dfrac{1}{13} \times \dfrac{13}{14} \times \dfrac{1}{15} \times \dfrac{15}{16}\] 가 된다. 이 과정을 15개 중 8개를 뽑는 모든 조합에 대해서 모두 수행하여 각 결과를 모두 더해주면 된다.

위의 과정을 9부터 15까지에 대해서 모두 해주면 게임에서 이길 수 있는 확률을 구할 수 있다. 이때, 분모의 경우는 항상 \(16!\) 이 되므로 분모에 대해서는 신경쓰지 않고 분자만 계산하면 된다. 

위의 방법을 통하여 게임에서 이길 확률을 구해보면 \(\dfrac{9219406943}{16!}\) 이 된다. 자 이제 게임에서 이길 때 받는 상금이 \(x\) 파운드 라고 한다면 게임 주최측에서 보는 기댓값은 다음과 같다. 

\[\dfrac{9219406943}{16!} \times (x-1) + \dfrac{16!-9219406943}{16!} \times 1\]

게임에 참여한 사람이 이길 경우 주최측은 상금 \(x\) 파운드에서 게임 참가비 1파운드를 제외한 \(x-1\) 파운드의 지출이 발생하고, 질 경우 주최측은 게임 참가비 1파운드의 수입이 발생한다. 따라서 위와 같이 기댓값이 계산되고, 이 기댓값이 양수를 유지하도록 상금의 최솟값을 결정해야 한다. 

결국 우리가 구해야 하는 답은 \(16! - 9219406943\) 를 \(9219406943\) 로 나눈 몫에 1을 더한 값이 된다.