퀴즈 399 선택 문제

---

무작위로 10개의 웹 사이트에 들어가 각 페이지에 나오는 단어를 세어본다고 하자.

처음부터 페이지를 훑어보다가 가장 많은 단어 수로 되어 있을 법한 페이지를 만나면 멈춘다고 하자.

이런 방식으로 한 웹페이지를 선택하고 이게 실제로 가장 많은 단어 수의 웹 페이지가 될 확률은 얼마나 될까?

풀이

1/e

이 문제는 정확히 결혼문제, 비서문제와 같은 문제이다.

몇년 전에 내가 썻던 포스팅을 첨부하며 마친다.

[수학]결혼문제
[수학, 알고리즘] Stable Marriage problem// 안정적 결혼 문제 // GS 알고리즘

퀴즈 400 뒤섞인 물건

---

3 사람이 자신의 핸드폰을 맡겨 두고 시험장에 들어갔다.

시험이 끝난 후 시험감독관이 핸드폰을 돌려주는데 [무작위로 준다고 하자]

이 3사람 중 적어도 한 명이 자기 모자를 되돌려 받을 확률은 얼마일까?

p.s 이 문제를 n 개로 일반화하면 재미있는 수학 상수가 등장한다. 또한 이 문제는 바로 직전 퀴즈문제 399와도 관련이 있다.

이 상수 관련된 최근 글

풀이

400번 문제는 완전순열 문제를 응용해서 풀면 된다. c.f 완전순열 포스팅 참조

완전순열의 표기법은 여러가지가 있는데, 위키피디아의 표기법을 따라가보자

이 완전순열의 일반항과 e 와의 관계는 다음과 같다.

자 이제 바로 문제를 풀어보자.

먼저 모자 3개의 경우부터 생각해보자. 모자 3개를 섞는 방법은 3!=6 가지이다. !3=2 이니까 실제 경우의 수는 6-2=4 이고 확률은 4/6 =2/3 이다.

즉 여사건을 이용하면 쉽게 풀린다. n 개의 모자를 섞는 경우의 수는 n! 그리고 모두 자신의 모자를 받지 못할 경우의 수가 !n 이니까 이 경우의 확률은 n 이 크면 클 수록 1/e 에 가까워진다.

이를 1에서 빼면 대략 0.64 정도가 나온다.

상수 e 의 아름다움이 조금이라도 전해졌기를