| [ QuizWit ] in KIDS 글 쓴 이(By): seulgi (슬기 ) 날 짜 (Date): 1997년06월10일(화) 02시40분20초 KDT 제 목(Title): Re: [문제] 술탄의 딸들 다음은 제 후배가 만든 풀이 입니다. 정의 : P(n,r)은 n명의 공주중에서 처음 r명을 그냥 보내고 다음부터는 이 r명과 비교하여 고를때 가장 지참금이 많은 공주와 만날 확률이다. 이때 r이 {1/(r+1)+...+1/(n-1)} < 1 < {1/r+...+1/((n-1)} 을 만족시킬때 P(n,r)이 최대가 된다. 즉 n-1 부터 거꾸로 역수로 더해가며 처음으로 1이 넘을때의 숫자를 r로 잡으면 P(n,r)이 최대가 된다. 풀이 : 먼저 P(n,r)의 값은 다음과 같이 구할수 있다. 가장 지참금이 많은 공주가 r번째 내에 있으면 고를수 있는 확률은 0 가장 지참금이 많은 공주가 r+1번째에 있으면서 그녀를 고를수 있는 확률은 (1/n)*(r/r) 가장 지참금이 많은 공주가 r+2번째에 있으면서 그녀를 고를수 있는 확률은 (1/n)*(r/(r+1)) ... 마지막으로 가장 지참금이 많은 공주가 n번째에 있으면서 그녀를 고를수 있는 (1/n)*(r/(n-1)) 따라서 P(n,r)=(1/n)*(r/r)+...+(1/n)*(r/(n-1)) 이다. 이제 P(n,r-1) < P(n,r) 과 P(n,r)>P(n,r+1) 을 동시에 만족시키는 r을 찾으면 된다. 위에서 구한 P(n,r)을 위의 식에 대입하여 계산하면, r이 {1/(r+1)+...+1/(n-1)} < 1 < {1/r+...+1/((n-1)} 을 만족시킬때 P(n,r)이 최대가 된다. 이제 n에 100을 대입하고 계산하면 되겠지요? 여담 : 만약 n이 무한대로 발산하면 확률이 최대가 되도록 하는 r의 값은 n/e (여기서의 e는 자연로그의 밑)로 근사하게 된답니다. 그리고 이러한 전략으로 지참금이 가장 많은 공주를 고를수 있는 확률은 1/e 에 수렴한답니다. @ 참 답을 안적었군요 37명입니다. 한편 100/exp(1)을 계산하면 36.78...이랍니다. 또 P(100,37)의 근사값을 구해보면 0.3710... 입니다. |