일반화된 몬티 홀 문제(monty hall problem) 2

25257번: Monty's Hall

 

d개의 문이 있고 정확히 1개의 문에 상품이 존재한다.

 

참가자는 s개의 문을 선택한다.

 

그러면 사회자는, 참가자가 선택하지 않은 문 중에서 상품이 없는 문 e개를 랜덤하게 열어준다.

 

이제 참가자에게 다시 한번 s개의 문을 선택할 기회를 준다.

 

기존의 선택을 바꾸지 않아도 좋다.

 

최적의 전략으로 게임에 임할때, 참가자가 상품을 획득할 확률은?

 

여기서 s+e < d이다.

 

----------------------------------------------------------------------------------------------------------------------------------------

 

전체 문 개수가 d개이고, 선택한 s개의 문 중에서 x개는 유지하고, s-x개는 d-s-e개의 문 중에서 새롭게 골라 연다고 하자.

 

x = 0,1,2,..,s이다.

 

이 x에 따라서 확률이 달라진다. 

 

그러한 확률은 P(x) = P(상품 획득 | 처음에 상품을 고른 경우)P(처음에 상품을 고른 경우) + P(상품 획득| 처음에 상품을 고르지 않음)P(처음에 상품을 고르지 않음)

 

1) 처음에 상품을 고른 경우

 

d개 중에 s개를 고르는 경우 dCs가지

 

상품 1개를 고르고, 나머지 문 d-1개 중 s-1개를 선택하는 경우 d-1Cs-1

 

따라서 확률 P(처음에 상품을 고른 경우) = d-1Cs-1/dCs = s/d

 

처음에 고른 문 s개 중 보물이 있다고 가정하면, x개를 유지할때 이 x개에 보물이 있는 경우는...?

 

P(상품을 획득 | 처음에 상품을 고른 경우) = s-1Cx-1/sCx = x/s

 

따라서, P(상품 획득 | 처음에 상품을 고른 경우)P(처음에 상품을 고른 경우) = x/d

 

 

2) 처음에 보물을 고르지 않은 경우

 

처음에 보물을 고를 확률이 s/d이므로, P(처음에 보물을 고르지 않은 경우) = 1-(s/d) = (d-s)/d

 

처음에 고른 문 s개에 보물이 없다고 가정하자.

 

사회자는 d-s개의 문 중에서 보물이 없는 문을 제외한 e개의 문을 여는데 닫혀있는 문은 d-e개이다.

 

처음에 고른 문 s개(닫혀있음)에는 보물이 없으므로 d-s-e개의 문 중에서 보물이 존재한다.

 

P(상품 획득 | 처음에 상품을 고르지 않은 경우)는, 처음에 고른 문 s개 중 x개의 문을 그대로 유지하고, s-x개의 문을 바꾼다고 하자.

 

s-x개의 문에 반드시 보물이 있어야하므로, d-s-e개의 문 중에서 s-x개의 문을 고를때 보물이 있어야한다.

 

d-s-e-1Cs-x-1/d-s-eCs-x = (s-x)/(d-s-e)

 

따라서, P(상품 획득 | 처음에 상품을 고르지 않은 경우)P(처음에 상품을 고르지 않은 경우) = (d-s)(s-x)/(d(d-s-e))

 

그러므로, 2가지 경우에 대하여

 

$$P(x) = \frac{x}{d} + \frac{(d-s)(s-x)}{d(d-s-e)}$$

 

 

3) 최적의 전략으로 게임

 

x값에 따라 달라지는 값이다.

 

즉, 처음에 선택한 s개의 문 중에서 몇개의 문을 바꾸느냐에 따라 확률이 달라진다.

 

최적의 전략으로 플레이하므로, P(x)를 최대화해야한다.

 

x에 대한 선형함수이므로, $$\frac{dP(x)}{dx} = \frac{1}{d} - \frac{d-s}{d(d-s-e)} = \frac{-e}{d(d-s-e)} < 0$$

 

모든 x에 대해 감소하는 함수이므로, x가 제일 작을때, P(x)는 최댓값이 된다.

 

즉, 바꾸지 않는 문의 수 x를 최소로 할때 확률이 최대화 된다.

 

그러니까 문을 바꿀수록 확률이 커진다.

 

따라서, x = 0일때, 모든 문을 바꾸면 

 

$$P(0) = \frac{s(d-s)}{d(d-s-e)}$$

 

가 최대이다.

 

???

 

근데 x개의 문은 남겨두고 s-x개의 문을 바꿀려는데, 

 

"""

P(상품 획득 | 처음에 상품을 고르지 않은 경우)는, 처음에 고른 문 s개 중 x개의 문을 그대로 유지하고, s-x개의 문을 바꾼다고 하자.

 

s-x개의 문에 반드시 보물이 있어야하므로, d-s-e개의 문 중에서 s-x개의 문을 고를때 보물이 있어야한다.

"""

 

d-s-e개의 문 중에서 s-x개의 문을 골라야하므로, d-s-e >= s-x

 

x >= s+s+e-d

 

그리고, x >= 0이므로, x >= max(0,s+s+e-d)

 

그러니까 s+s+e-d > 0이라면, x의 최솟값은 x = s+s+e-d이므로,

 

$$P(x) = \frac{s+s+e-d}{d} + \frac{(d-s)(d-e-s)}{d(d-s-e)} = \frac{s+e}{d}$$

 

결론적으로 s+s+e-d > 0이면, $\frac{s+e}{d}$

 

s+s+e-d <= 0이면, $\frac{s(d-s)}{d(d-s-e)}$

 

d,s,e = map(int,input().split())

if 2*s+e <= d:

    print(s*(d-s)/(d*(d-s-e)))

else:
    
    print((s+e)/d)