무승부가 아닌, 이번엔 패자 1명(혹은 승자 1명)이 결정되기까지 필요한 가위바위보 수는? 단 가위바위보는 패자[승자] 끼리 가위바위보를 한다.
이는 예전에 출제한 quiz 64 문제를 일반화 해 본 것이다. 퀴즈 문제가 패자였으니 여기서도 패자로 가보자.
이 문제에서는 두 사람이 가위바위보를 할 때, 세 사람이 가위바위보를 할 때 패자 1명이 결정되기 까지 필요한 가위바위보의 수를 물었다.
3명까지는 쉽게 계산 가능한데 n 으로 일반화를 하면 어떻게 해야 할까?
쉽게 일반화가 안 되서 인터넷 검색을 해 보았다.
크게 세 자료가 유용했다. [참고문헌]
일단 n 명이 가위바위보를 했을 때 승부가 날 확률은, 전체 확률 1 에서 n 명이 가위바위보를 했을 때 승부가 나지 않을 확률을 뺀 값이다.
이미 이전 포스팅에서 n 명이 가위 바위보를 했을 때 승부가 나지 않을 확률에 대해 다루었었다.
[관련 글-[수학] 가위바위보와 무승부 ] 전체 경우의 수는 3^n, 승부가 날 경우의 수는 3(2^{n} -2) 이다.
자 이제는 n 명의 경우에서 m 명이 남아 있을 확률을 구하려고 한다. 편의상 이를 P_{n,m} 이라 하자.
m 명이 살아남으려면 일단 가위바위보 게임이 승부가 나야 한다. 가위바위보 게임에서 승자가 나올 수 있는 경우의 수는 세가지 뿐이다. [가위, 바위, 보 중 2가지만 등장 3 choose 2 =3 ]
m 명이 살아남게 하려면,m 명이 바위[가위, 보] 를 고르면 나머지 n-m 명이 가위[보, 바위] 를 고르게 하면 된다. 전체의 경우의 수는 3^n 가지가 될테니 확률 T_{n, m} 을 써보면
자 여기서 n=m 일 때는 이 식이 성립하지 않는다. 왜냐하면 모든 사람이 살아남을 확률은 가위, 바위 로만 이루어지는게 아닌, 비기는 경우를 고려하는 것이기 때문이다. [위에는 승자가 반드시 존재하는 가정 하의 확률이다. ]
비기는 경우의 수는 전체 경우의 수 3^n 에서 승부가 날 경우의 수인 3(2^n -2) 임을 빼주는 것이 된다. 즉
앞의 경우와 합치면 [글씨가 너무 안 좋아서 tex 으로 바꾸었다. ]
자 이제 멈출 확률을 구해보자.
n 명의 선수로 시작해서, k 번째에 게임이 끝날 확률을 구해보자. 재귀적인 방법으로 이를 구할 수 있다. 특별이 이 확률을 S(n,k) 라 하자 [S=Stop]
처음부터 일반화를 하면 힘드니까 S(n,k) 을 구하려고 해보자. [n명 중 k경기 만에 1명이 결정 될 확률]
먼저 첫번째 게임을 하자. 이 때 m 명이 살아남는 다고 하면 그 다음엔 그 m 명이 k-1 번의 경기로 한명을 결정해야 한다.
즉
자 이제 기대값을 구해보자.
앞에서 구한 P(n,m) 값을 대입하면
저 점화식을 generating function 을 이용하여 일반항을 구할 수 있다. 관심있는 독자는 아래 참고문헌의 논문을 확인하면 된다.
저자의 소속이 반대가 된 듯한데 ㅋㅋㅋㅋ
해당 논문은 generating function 을 구하고, Markov chain 을 이용하여 E_n 의 behaviour 를 기술한 논문이다. 참 재미있는 논문이다.