바뀌는 가위바위보 확률 계산

학교 선생님이 가끔 하던 특이한 방식의 가위바위보 게임의 확률을 계산해 보겠다. 방식은 다음과 같다.

1. $P$와 $Q$는 일어서서 서로의 등을 맞대며 손을 들고 서 있다. 2. 둘은 비기지 않고 승패의 결과가 나올 때까지 가위바위보를 계속한다(둘은 상대가 무엇을 냈는지 모르며, $J$가 승패의 결과가 나오면 그만하라고 하고, 비기면 다시 하라고 한다. 무한 번 비기지는 않는다) 3. $J$가 $P$한테 물어본다. “지금 가위바위보 낸 거 바꾸고 싶으면 바꾸고, 안 바꾸고 싶으면 바꾸지 마”. 이 만약 바꾸지 않는다면, $J$가 결과를 알려준다. 만약 바꾼다면 $J$는 $Q$한테 물어본다. “지금 가위바위보 낸 거 바꾸고 싶으면 바꾸고, 안 바꾸고 싶으면 바꾸지 마”. $Q$가 만약 바꾸지 않는다면, $J$가 결과를 알려준다. 만약 바꾼다면 $P$한테 기회가 다시 넘어가고 이 과정을 계속 반복한다. 즉, 누구 한 명이 먼저 바꾸기를 종료하면, 결과가 나온다. 만약 승패가 갈리면 게임은 종료되고 승자가 정해지며, 비긴다면 1번 과정부터 다시 해서 반복한다.

이런 느낌으로 가위바위보를 한다. 그리고 몇 개 문제를 만들어 봤다.

(1) $Q$은 확률로 가위바위보를 바꿀지 말지 정하고 바꾼다면 확률로 자신이 냈던 것 제외 둘 중 하나를 선택해 정하는 기계를 만들어서 게임에서 이용하기로 했다. 하지만 $P$는 이러한 $Q$를 이기기 위해 가장 높은 확률로 $Q$를 이기는 방법을 찾아냈다. 이때, 이 최종적으로 $Q$를 이길 확률은? (2) 반대로 $P$가 확률로 가위바위보를 바꿀지 말지 정하고 바꾼다면 확률로 자신이 냈던 것 제외 둘 중 하나를 선택해 정하는 기계를 만들어서 게임에서 이용한다. $Q$는 이러한 $P$를 이기기 위해 가장 높은 확률로 $P$를 이기는 방법을 찾아냈다. $P$가 $Q$를 이길 확률은? (3) 만약 $P$와 $Q$가 최선의 선택만을 한다면 이 게임은 어떻게 진행될까?

 

그리디 알고리즘(Greedy Algorithm) 문제이다. 제일 중요한 포인트는 둘이 비기지 않고 승패의 결과가 나올 때까지 가위바위보를 계속한다는 것이다. $\mathrm{WLOG}$ $P$가 가위를 내고 승패가 결정되었다고 하자. 만일 $P$가 종료하면 $\displaystyle \frac{1}{2}$확률로 이긴다. 그러나 상대는 바위 또는 보이므로 보로 바꾸면 절대 지지 않으므로 더 유리하다. 상대가 여기서 종료하면 $\displaystyle \frac{1}{2}$확률로 이기고 확률로 비긴다. 이와 같은 과정을 정리한다. 가위바위보를 간단하게 $A, B, C$라고 하자.($A>B, B>C, C>A$). $W$는 $WIN$. $L$은 $LOSE$. $D$는 $DRAW$이다. $P:X \to Y$는 $P$가 가위바위보를 원래 $X$였는데 $Y$로 바꿨다는 의미이다.

---

(1)

이렇게 정리해서 먼저 $\displaystyle \sum_{i=1}^{\infty}W_{i}$를 계산하자. 홀수번째 항만 모으면 $\displaystyle \frac{1}{2^{2}} + \frac{3}{2^{6}} + \frac{11}{2^{10}} + \dots$. 그러면 분모는 $\displaystyle 2^{4n-2}$이고 분자는 규칙성으로 $f(n+1)=4f(n)-1,f(1)=1$임을 알 수 있다. $\displaystyle g(n)=f(n)-\frac{1}{3}$라고 하면 $g(1)=\displaystyle 1-\frac{1}{3}=\frac{2}{3}$이므로 $\displaystyle g(n)=\frac{2}{3} \times 4^{n-1}$. 즉, $$f(n)= \frac{2}{3} \times 4^{n-1}+\frac{1}{3}$$이다. 즉, 홀수 $W$의 일반항은 $$\displaystyle \frac{ \displaystyle \frac{ 2 \times 4^{n-1} + 1}{3}}{2^{4n-2}} = \frac{2 \times 4^{n-1} + 1}{3 \times 2^{4n-2}}$$이다. 홀수 $W$의 합은 $$\quad \frac{4}{3} \sum_{n=1}^{\infty} \frac{2 \times 4^{n-1} + 1}{4^{2n}} = \frac{2}{3} \sum_{n=1}^{\infty} \frac{1}{4^n} + \frac{4}{3} \sum_{n=1}^{\infty} \frac{1}{16^n} = \frac{2}{9} + \frac{4}{45} = \frac{14}{45}$$이고, 짝수항은 홀수 항의 $\displaystyle \frac{1}{2}$이므로 총합은 $$ \displaystyle \sum_{i=1}^{\infty}W_{i}= \frac{14}{45} \times \frac{3}{2}=\frac{7}{15}$$이다. 같은 방법으로 나머지도 구하면 $$\sum_{i=1}^{\infty} D_i = \frac{6}{15}, \quad \sum_{i=1}^{\infty} L_i = \frac{2}{15}$$이다. 지금까지 단판에서의 확률을 구했으므로 최종 확률을 구하면 된다. 최종 확률은 $$\sum_{i=1}^{\infty} W_i + \sum_{i=1}^{\infty} W_i \times \sum_{i=1}^{\infty} \left( \sum_{j=1}^{\infty} D_j \right)^{i}$$이므로 $$\frac{7}{15} \times \frac{5}{3}=\frac{7}{9}$$이다.

---

(2)

거의 똑같다. 맨 처음에 $D$가 $L$로 바뀐 거 제외하면 다 같으므로 거의 다 생략한다. 그래서 계산하면 $$\sum_{i=1}^{\infty} W_i = \frac{7}{15}, \quad \sum_{i=1}^{\infty} D_i = \frac{6}{15}-\frac{1}{4}=\frac{3}{20}, \quad \sum_{i=1}^{\infty} L_i = \frac{2}{15}+\frac{1}{4}=\frac{23}{60} $$ 따라서 최종 확률은 $$\frac{7}{15} \times \frac{20}{17}=\frac{28}{51}$$이다. 따라서, 상대적으로 $P$보다 $Q$가 게임에서 유리함을 알 수 있다.

---

(3) 따라서 각 상황에서 게임을 종료하는 것보다 항상 바꾸는 것이 유리하므로 둘은 절대 종료하려 하지 않는다. 즉, 게임은 끝나지 않는다.