exercise:6d2d2af699

The letters between Pascal and Fermat, which are often credited with having started probability theory, dealt mostly with the problem of points described in Exercise. Pascal and Fermat considered the problem of finding a fair division of stakes if the game must be called off when the first player has won [math]r[/math] games and the second player has won [math]s[/math] games, with [math]r \lt N[/math] and [math]s \lt N[/math]. Let [math]P(r,s)[/math] be the probability that player A wins the game if he has already won [math]r[/math] points and player B has won [math]s[/math] points. Then

• [math]P(r,N) = 0[/math] if [math]r \lt N[/math],
• [math]P(N,s) = 1[/math] if [math]s \lt N[/math],
• [math]P(r,s) = pP(r + 1,s) + qP(r,s + 1)[/math] if [math]r \lt N[/math] and [math]s \lt N[/math];

and (1), (2), and (3) determine [math]P(r,s)[/math] for [math]r \leq N[/math] and [math]s \leq N[/math]. Pascal used these facts to find [math]P(r,s)[/math] by working backward: He first obtained [math]P(N - 1,j)[/math] for [math]j = N - 1,N - 2, \ldots, 0[/math]; then, from these values, he obtained

[math]P(N - 2,j)[/math] for [math]j = N - 1, N - 2, \ldots, 0[/math] and, continuing backward, obtained all the values [math]P(r,s)[/math]. Write a program to compute [math]P(r,s)[/math] for given [math]N[/math], [math]a[/math], [math]b[/math], and [math]p[/math].

Follow Pascal and you will be able to run [math]N = 100[/math]; use recursion and you will not be able to run [math]N = 20[/math].