안녕하세요? ryanhan 입니다.
저번 포스팅에서는 행렬곱을 이용하여
여러 명이 가위바위보를 할 때 1등이 정해지는데 걸리는 평균 횟수를
구하는 방법을 소개해보았습니다.
그 방법에서는 행렬의 거듭제곱을 해야 하는데요,
거듭제곱을 하던 도중, 점화식을 이용한 풀이가 더 간단해서
점화식을 이용해서 구하는 방법을 소개해 보겠습니다.
우선 두 명을 기준으로 생각해보면, 둘 중에 한명이 이길 확률은
전체 경우의 수: 9 (3x3)
한명이 이기는 경우의 수: 2(둘 중에 누가)x3(무엇으로)=6
이므로 2/3이 됩니다.
즉, 2/3의 확률로 한 번만에 일 등이 결정 되는 것 이고
1/3의 확률로 비겨서 다시 가위바위보를 해야 하는 상황이 됩니다.
이제 2명이서 가위바위보해서 1명이 결정되는 평균 횟수를
F(2)이라 하겠습니다.
2명이서 가위바위보를 한 판 했다고 하겠습니다.
1/3 확률로 다시 2명이 가위바위보를 하게 됩니다.
1등이 정해지려면 다시 평균횟수 F(2)만큼 가위바위보를 해야 합니다.
또, 2/3 확률로 한 판 만에 1등이 정해집니다.
즉, F(2) = 1/3( 1+F(2) ) + 2/3 * (1) 이라는 식으로 쓸 수 있고,
계산을 해보면, F(2)=1.5가 됩니다.
이제 세 명으로 확장해 보겠습니다.
가위바위보를 한 판 했을 때,
한 명이 남을 확률은 1/3
두 명이 남을 확률은 1/3
세 명이 남을 확률은 1/3 입니다.
세 명이 가위바위보 했을 때 평균 횟수를 F(3)라 하면,
F(3) = 1/3 (1) + 1/3 (1+F(2)) + 1/3(1+F(3))가 됩니다!
계산을 해보면 F(3)= 9/4 로 평균적으로 2.25회 걸립니다!
N명이 가위바위보해서 m명이 남을 확률은
또한 m명이 남았을 때부터 걸리는 평균 횟수는 F(m)입니다.
위와 같은 점화식을 세울 수 있게 됩니다!!
F(4)를 구해보면, F(4)= 45/14 로,
네 명이서 가위바위보를 하면 보통 3.21번 걸린다는걸 알 수 있습니다!
다만, 아직 저 점화식의 일반항을 구하지는 못했습니다.
혹시, 관심이 있으신 분은 도전해보시는 것도 좋겠습니다!!
감사합니다.
ryanhan이었습니다.
(고양이가 puma자세로 누워있네요. ㅋㅋ)
