도박꾼의 파산 문제 해설

원문은 [1]. 일본어라 구글번역[2] 돌려서 봤는데 수학이라 그런지 일본어라 그런지 이해하기는 충분하다.

문제풀이의 아이디어는

1) 일단 답이 만족해야 하는 성질을 제시하고

2) 어떤 식을 답으로 제안하여 1을 만족함을 보이고

3) 1의 해가 유일함을 보여서 2에서 제안한 식이 답임을 보인다.

\(P(N, N)=1, P(0, N)=0\)임은 자명하다. (내맘대로 fixed point라고 하겠다)
그리고, $$\begin{equation}P(m,N) = pP(m+1,N) + qP(m-1,N) \end{equation}$$이다. 왜냐하면,

처음 던졌을 때 이겼다면(\(p\)) 현재 가진 돈은 \(m+1\)원이므로 \(P(m+1, N)\)을 만족하면 된다.

처음 던졌을 때 졌다면(\(q\)) 현재 가진 돈은 \(m-1\)원이고 \(P(m-1, N\))을 만족하면 된다.

따라서 (1)이 성립한다.

답이 아래와 같다고 치면$$\large \begin{equation} P(m,N) = \frac{1-(q/p)^m}{1-(q/p)^N} \end{equation}$$ 위의 세 조건을 모두 만족한다. 계산해보면 된다.

한편,

P(1,2)를 생각해 보면, P(0,2)와 P(2,2)로 결정되고, 계산하면 나온다. 따라서 P(m, 2)의 가능한 모든 수를 구했다. (m=0,1,2)

P(1,3)을 생각해보면, P(0,3)과 P(2,3)으로 결정되고, P(2,3)은 다시 P(1,3)과 P(3,3)으로 결정된다. 즉, 연립방정식을 얻는다.

모든 수에 대해 아래와 같은 식이다. (검은 점이 fixed point)

따라서 해가 존재하고 유일하다. 그러므로 위에서 구한 해(equation(2))가 답이다.

blog comments powered by Disqus