원래 인터넷에 있는 내용인데 설명을 추가한 버전이다.

문제

여자는 남자 100명이 순차적으로 프로포즈할 때 몇 번째까지 튕겨야 하는가?

가정

위 문제를 수학적으로 살펴보기 위해 몇 가지 가정을 하자.

  1. 순차적으로 프로포즈 한다.

  2. 첫번째 프로포즈 허락하면 나머지 99명은 못본다

  3. 99번 거절하면 100번째와 결혼해야 한다.

  4. 100명의 남자의 분포는 랜덤이다. 즉, 어떤 남자가 백마탄 남자인지 모른다.

  5. 여자는 \(r\)번째까지는 무조건 튕기고 그 다음부터 나오는 남자부터는 지금까지 본 남자 중에 가장 괜찮다면 결혼한다. 10번까지 튕기기로 했다면 11번째 남자가 기존 10명보다만 괜찮다면 프로포즈에 OK한다.

풀이

회귀분석에서 회귀계수의 최대가능도추정량(MLE)를 구하는 방법과 상당히 유사하다.

사건 정의

  • \(B\): 여자가 백마탄 왕자를 정확히 선택한다.

  • \(A_1\): 백마탄 왕자가 1번째로 프로포즈한다.

  • \(A_2\): 백마탄 왕자가 2번째로 프로포즈한다.

\(\cdots\)

  • \(A_{100}\): 백마탄 왕자가 100번째로 프로포즈한다.

구하려는 값

  1. \(P(B)\) 즉, 여자가 백마탄 왕자를 정확히 선택할 확률

  2. 이 확률을 최대로 하는 \(r\)의 값: 몇 번째까지 튕겨야 백마탄 왕자를 만날 확률이 높을까?

\(P(B)\) 구하기

\(P(B)\)를 조건부 확률로 표현하면

\[P(B)=P(A_1) \times P(B|A_1) + P(A_2) \times P(B|A_2) + ... + P(A_{100}) \times P(B|A_{100}) = \sum_{k=1}^{100} P(A_k) \times P(B|A_k)\] 인데, \(r\)번째까지는 튕기기로 했으므로 \[P(B|A_1)=P(B|A_2)=...=P(B|A_r)=0\] 임은 자명하다. 또한 남자의 분포는 랜덤이므로 \[P(A_1)=P(A_2)=...=P(A_{100})=\frac{1}{100}\] 로 모두 같다. 이제 나머지 값들을 살펴보면 우선

\[P(B|A_{r+1})= 1\] 임이 확실하다. \(r+1\)번째 백마탄 왕자가 프로포즈 하였다는 것은 당연히 그 이전에 r명의 남자보다 낫다는 뜻이므로 프로포즈를 OK하게 된다.

이를 토대로 \(P(B|A_{r+2})\)를 구해보자. 이제부터는 생각을 좀 해야 한다.

  • 만약 \(r+2\)번째 남자가 백마탄 왕자인데 \(r+1\)번째 남자가 기존 \(r\)명보다 괜찮아서 \(r+1\)번째 남자의 프로포즈를 Ok한다면, 여자입장에서 실패이다.

  • 따라서 \(r+1\)번째 남자가 기존 \(r\)명의 남자보다 떨어지는 남자여야 할 것이다.

  • 이를 다시 말한다면 \(r+1\)번째까지의 남자 중 제일 괜찮은 남자가 \(r+1\)번째 남자만 아니면 된다. why? \(r\)번째까지는 무조건 튕길거니까\(\dots\)

  • 이 확률은 \(\frac{r}{r+1}\) 이며 결과적으로

\[P(B|A_{r+2})=\frac{r}{r+1}\]

이제부터는 비슷하다. \(P(B|A_{r+3})\)의 경우, 앞의 \(r+2\)명의 남자 중 \(r+1\)번 째와 \(r+2\)번 째가 그 전보다 괜찮은 남자이면 안된다. 즉, \(r+2\)명 중 제일 괜찮은 남자가 \(1 \sim r\)번째에 있으면 된다. 따라서

\[P(B|A_{r+3})=\frac{r}{r+2}\]

나머지도 마찬가지로 계산하면 \(P(B|A_{r+4})\)부터 순서대로 \(\frac{r}{r+1} \cdots \frac{r}{99}, \frac{r}{100}\)이 되며 지금까지의 결과를 종합하면 \(P(B)\)는 다음과 같다.

\[P(B)= \frac{1}{100} \times (1 + \frac{r}{r+1} + \frac{r}{r+2} + \cdots + \frac{r}{99} + \frac{r}{100} = \frac{1}{100} \sum_{x=r}^{100}\frac{r}{x}\]

\(P(B)\)를 최대로 하는 \(r\)의 값

시그마로 계산하면 복잡하므로 적분을 활용하여 근사값을 구하자.

\[P(B) = \frac{1}{100} \sum_{x=r}^{100}\frac{r}{x} \simeq \frac{r}{100} \int_{r}^{100} \frac{1}{x} dx = \frac{r}{100} \times (\text{ln}100 - \text{ln}r )\]

이 된다. 이것은 \(r\)의 함수이고 두번 미분하면 (-)인 위로 볼록한 함수이므로, 미분해서 \(0\)이 되는 \(r\)의 값이 \(P(B)\)를 최대로 하는 \(r\)의 값이다.실제로 \(P(B)\)를 \(r\)에 대해 미분하면

\[\frac{1}{100} \times (\text{ln}100 - \text{ln}r -1)\]

이고 이를 \(0\)으로 만드는 \(\text{ln}r\)은 대략 \(3.605\) 이다. 즉,

\[r=36.787\cdots\] 이다.

결론

  1. 남자가 100번 대시한다면 36번 정도 튕기는 것이 백마탄 왕자를 만나는데 유리하다.

  2. 10번정도로 예시를 줄이면 \(3 \sim 4\)번만 튕겨라?

Copyright ©2016 Jinseob Kim