| [ QuizWit ] in KIDS 글 쓴 이(By): pomp (위풍당당) 날 짜 (Date): 1997년06월17일(화) 23시32분13초 KDT 제 목(Title): Re: 술탄의 딸들 - scalar 37명의 공주를 본 다음 local max보다 지참금이 더 많은 공주를 고르는 전략을 환상님의 표현대로 "37전략"이라고 이름 붙이죠. 다음처럼 풀면 됩니다. ------------------------------------------------------- 처음 n 명의 공주는 그냥 보내고, 그 다음 공주들 가운데 처음의 n 명보다 지참금이 많은 첫 사람을 고르면 된다. 지참금이 가장 많은 공주가 k 번 째에 있을 확률은 1/100이고, 이때 그 공주에게 청혼할 수 있으려면, 그 이전 k-1 명의 공주 가운데 가장 지참금이 많은 공주가 처음 n 명 가운데 있어야 하니까, 확률은 n/(k-1)이다. 따라서 전체 확률은, 1/100 * ( n/n + n/(n+1) + ... + n/99 ) 이 되고, 이 값은 n = 37일 때 최대값인 약 37%가 된다. ------------------------------------------------------ 공주의 수가 무한에 가까와지면 이 값은 1/e에 다가갑니다. (증명은 슬기님 포스팅을 참조) 결코 1/e에 끼워 맞추기 위해 37이란 숫자가 나온 게 아닙니다. 이것말고 다른 전략이 둘 올라 왔는데, 하나는 n 명의 공주에서 local maximum을 찾고, n+1번부터 100번까지의 공주 가운데, local max를 넘는 두 번째 공주를 고른다는 것이고, (37전략이랑 비슷하니까 이걸 37-2라고 합시다.) 또 하나는 n번째 maximum을 찾는다는 전략입니다. (이건 n-th max라고 합시다.) 100명에 대해 그 확률을 찾는 건 상당히 계산을 많이 해야 할 테니, 간단하게 4명에 대해 해 봅시다. 4!=24니까 4명의 공주를 늘어 세우는 게 24가지 방법이 있는데, 37전략에 따르면 2명의 공주를 그냥 보내게 되고, 이 전략이 성공하는 경우는 모두 12 가지 경우입니다. 37-2 전략을 써 보면, 1 명의 공주를 그냥 보내는 것은 8 가지 경우, 2 " " " " " 6 " " 3 " " " " " 생각할 필요없고, n-th max 전략을 써 보면, 1 번째 maximum을 고른다는 건 그냥 첫번째 공주를 택한다는 뜻이니까 의미없고, 2 " " 고르는 것은 11 가지 경우, 3 " " " " 7 가지 경우, 4 " " " " 그냥 마지막 공주를 택한다는 뜻이니까 역시 무의미. 비록 공주 수를 왕창 줄여 4 명에 대해서만 했지만, 100명에 대해서도 마찬가집니다. (정 의심이 되면 컴퓨터를 써서 직접 세어 보세요.) ... & circumstance |