Advanced book on Mathematics Olympiad

782 Combinatorics and Probability

P(k)=pP (k+ 1 )+qP(k− 1 )+rP (k).

Taking into account thatp+q+r=1, we obtain the recurrence relation

pP (k+ 1 )−(p+q)P(k)+qP(k− 1 )= 0.

The characteristic equation of this recurrence ispλ^2 −(p+q)λ+q=0. There are two
cases. The simpler isp=q. Then the equation has the double rootλ=1, in which
case the general term is a linear function ink. SinceP( 0 )=0 andP(N)=1, it follows
thatP (m)=mN=n+mm.Ifp =q, then the distinct roots of the equation areλ 1 =1 and
λ 2 =qp, and the general term must be of the formP(k)=c 1 +c 2 (pq)k. Using the known
values fork=0 andN, we compute

c 1 =−c 2 =

1

1 −(qp)N

.

Hence the required probability is

m

m+n

ifp=q and

1 −(qp)m

1 −(qp)m+n

ifp =q.

(K.S. Williams, K. Hardy,The Red Book of Mathematical Problems, Dover, Mineola,
NY, 1996)

926.Seeking a recurrence relation, we denote byE(m, n)this expected length. What
happens, then, after one toss? Half the time you win, and then the parameters become
m+1,n−1; the other half of the time you lose, and the parameters becomem− 1 ,n+1.
Hence the recurrence

E(m, n)= 1 +

1

2

E(m− 1 ,n+ 1 )+

1

2

E(m+ 1 ,n− 1 ),

the 1 indicating the first toss. Of course, this assumesm, n >0. The boundary conditions
are thatE( 0 ,n)=0 andE(m, 0 )=0, and these, together with the recurrence formula,
do determine uniquely the functionE(m, n).
ViewE(m, n)as a function of one variable, sayn, along the linem+n=constant.
Solving the inhomogeneous second-order recurrence, we obtainE(m, n)=mn. Alter-
nately, the recursive formula says that the second difference is the constant(− 2 ), and
soE(m, n)is a quadratic function. Vanishing at the endpoints forces it to becmn, and
direct evaluation shows thatc=1.
(D.J. Newman,A Problem Seminar, Springer-Verlag)

927.Letxandybe the two numbers. The set of all possible outcomes is the unit square

D={(x, y)| 0 ≤x≤ 1 , 0 ≤y≤ 1 }.