Advanced book on Mathematics Olympiad

6.3 Probability 315

Example.In a selection test, each of three candidates receives a problem sheet withn
problems from algebra and geometry. The three problem sheets contain, respectively,
one, two, and three algebra problems. The candidates choose randomly a problem from
the sheet and answer it at the blackboard. What is the probability that

(a) all candidates answer geometry problems;
(b) all candidates answer algebra problems;
(c) at least one candidate answers an algebra problem?

Solution.We apply the Poisson scheme. Define the polynomial

P(x)=

(

1

n

x+

n− 1

n

)(

2

n

x+

n− 2

n

)(

3

n

x+

n− 3

n

)

=

1

n^3

[ 6 x^3 +( 11 n− 18 )x^2 +( 6 n^2 − 22 n+ 18 )x+(n− 1 )(n− 2 )(n− 3 )]

=P 3 x^3 +P 2 x^2 +P 1 x+P 0.

The answer to question (a) is the free termP 0 =(n−^1 )(nn− 32 )(n−^3 ). The answer to (b) is the

coefficient ofx^3 , namely,P 3 =n^63. The answer to (c) isP= 1 −P 0 =^6 n

(^2) − 11 n+ 6
n^3. 
And now another problem posed to Pascal and Fermat by the Chevalier de Méré.
Example.Two players repeatedly play a game in which the first wins with probability
pand the second wins with probabilityq = 1 −p. They agree to stop when one of
them wins a certain number of games. They are forced to interrupt their game when the
first player hasamore games to win and the second player hasbmore games to win.
How should they divide the stakes correctly? Use the answer to prove the combinatorial
identities
pa
∑b−^1
k= 0

(

a− 1 +k

a− 1

)

qk+qb

∑a−^1

k= 0

(

b− 1 +k

b− 1

)

pk= 1 ,

pa

∑b−^1

k= 0

(

a− 1 +k

a− 1

)

qk=

(a+b− 1 )!

a!(b− 1 )!

paqb−^1

[

1 +

∑b−^1

k= 1

(b− 1 )···(b−k)

(a+ 1 )···(a+k)

(

p

q

)k]

.

Solution.CallPthe probability that the first player wins thearemaining games before
the second player wins thebgames he needs, andQ= 1 −P, the probability that the
second player winsbgames before the first winsa. The players should divide the stakes
in the ratioPQ.
We proceed with the computation ofP. The first player could have won theagames
in several mutually exclusive ways: in exactlyagames, in exactlya+1 games,...,in
exactlya+b−1 games. In all cases the last game should be won by the first player.