고율님 블로그에서 보고 따라해 봤다.

11명 중에 한 사람을 선정하기 위해서 주사위를 굴리기로 했다.
주사위를 유한한 횟수 이내로 굴려 균등한 확률로 11명 중의 한 명을 선정할 수 있는 방법을 서술하시오. (단, 주사위는 정 6면체이다.)
*읽기전에 알아둘 것 : 이 논리는 틀렸습니다!
$(a+b)^2 = a^2+b^2+2ab$

기본 아이디어는 이항전개다.

각 면에 써 있는 숫자를 n이라고 놓고, k번 던진 다음에 나오는 숫자를 계산해 보면
$\left(\sum^6_{i=1}e^n \right)^k$
으로 쓸 수 있고, 이 식에서 각 항마다 있는 계수는 정해진 합에 대해서 그 합이 나오는 경우의 수가 몇개인지 알려준다. 그럼, 적당히 큰 k를 고르고, 그중에 계수가 11을 넘는 합 하나를 가져오자. 합 자체는 얼마가 되든 상관 없다. 그냥 a라고 하자. 그리고 그 계수를 m이라고 하자. m은 이항전개에서 해당 항이 나오는 횟수가 몇번인지 알려준다. 따라서, 이항전개에서 그 항은 11번 이상 나온다.

이 말은 바꿔 말하면, 주사위를 k번 던질 때 전체 가능한 경우의 수 중에서 합이 a가 되는 경우가 m번 있다는 뜻이다. 그럼, 이제 합이 a가 되는 경우 각각을 11명의 사람들에게 배정한다. 경우의 수가 11을 넘어갈 수도 있지만, 나머지는 무시해 버려도 된다. 순서 따져서 각각이 구별 가능하기만 하면 된다.

이제 주사위를 k번 던지는데, 합이 a가 되지 않으면 무시하고, 합이 a가 되면 그렇게 된 경우가 11명의 사람이 배정받게 된 경우 중 어느 것에 해당하는지 따져본다. 아무도 배정받지 않았다면 다시 던진다.

이것이 가능한 이유는 전체 경우의 수 각각이 발생할 확률은 똑같기 때문에, 우리가 원하는 만큼만 골라내고 나머지는 다 버려도 문제가 없다는 것이다.

또한, 합이 a가 나올 확률은 0이 아니므로 반드시 유한한 횟수 안에 끝난다. (물론 계속 합이 a가 나오질 않아서 조금 더 길어질 수는 있으나, 확률이 0이 아니기 때문에 무한히 시행하다보면 실제로 무한까지 가기 전에 유한 횟수 내에 끝나는 것이 보장된다.)
by snowall 2008. 8. 26. 08:55