Advanced book on Mathematics Olympiad

Combinatorics and Probability 773

908.Denote byP (n)the probability that a bag containingndistinct pairs of tiles will be
emptied,n≥2. ThenP (n)=Q(n)P (n− 1 )whereQ(n)is the probability that two of
the first three tiles selected make a pair. The latter one is

Q(n)=

number of ways to select three tiles, two of which match

number of ways to select three tiles

=

n( 2 n− 2 )

( 2 n

3

) =

3

2 n− 1

.

The recurrence

P (n)=

3

2 n− 1

P(n− 1 )

yields

P (n)=

3 n−^2

( 2 n− 1 )( 2 n− 3 )··· 5

P( 2 ).

Clearly,P( 2 )=1, and hence the answer to the problem is

P( 6 )=

34

11 · 9 · 7 · 5

=

9

385

≈ 0. 023.

(American Invitational Mathematics Examination, 1994)

909.Because there are two extractions each of with must contain a certain ball, the total
number of cases is

(n− 1

m− 1

) 2

. The favorable cases are those for which the balls extracted
the second time differ from those extracted first (except of course the chosen ball). For
the first extraction there are

(n− 1

m− 1

)

cases, while for the second there are

(n−m

m− 1

)

, giving a

total number of cases

(n− 1

m− 1

)(n−m

m− 1

)

. Taking the ratio, we obtain the desired probability as

P=

(n− 1

m− 1

)(n−m

m− 1

)

(n− 1

m− 1

) 2 =

(n−m

m− 1

)

(n− 1

m− 1

).

(Gazeta Matematic ̆a(Mathematics Gazette, Bucharest), proposed by C. Marinescu)

910.First, observe that since at least one ball is removed during each stage, the process
will eventually terminate, leaving no ball or one ball in the bag. Because red balls are
removed 2 at a time and since we start with an odd number of red balls, the number of
red balls in the bag at any time is odd. Hence the process will always leave red balls
in the bag, and so it must terminate with exactly one red ball. The probability we are
computing is therefore 1.
(Mathematics and Informatics Quarterly, proposed by D. Macks)