Maths Olympiad Prep

Library / /52 of 62

Combinatorics Difficulty 6.2 National Olympiad Find the answer United States

Problem:

Alice and Bob take turns removing balls from a bag containing 10 black balls and 10 white balls, with Alice going first. Alice always removes a black ball if there is one, while Bob removes one of the remaining balls uniformly at random. Once all balls have been removed, the expected number of black balls which Bob has can be expressed as ab\frac{a}{b}, where aa and bb are relatively prime positive integers. Compute 100a+b100 a+b.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Suppose aa is the number of black balls and bb is the number of white balls, and let Ea,bE_{a, b} denote the expected number of black balls Bob has once all the balls are removed with Alice going first. Then we want to find E10,10E_{10,10}. It is evident that if E0,b=0E_{0, b}=0. Also, since Bob chooses a black ball with probability a1a+b1\frac{a-1}{a+b-1}, if a>0a>0 we have
Ea,b=a1a+b1(Ea2,b+1)+ba+b1Ea1,b1=(a1)(Ea2,b+1)+bEa1,b1a+b1 \begin{aligned} E_{a, b} & =\frac{a-1}{a+b-1}\left(E_{a-2, b}+1\right)+\frac{b}{a+b-1} E_{a-1, b-1} \\ & =\frac{(a-1)\left(E_{a-2, b}+1\right)+b E_{a-1, b-1}}{a+b-1} \end{aligned}

We claim that Ea,b=a(a1)2(a+b1)E_{a, b}=\frac{a(a-1)}{2(a+b-1)}, which will yield an answer of 4519\frac{45}{19}. To prove this, we use induction. In the base case of a=0a=0 we find a(a1)2(a+b1)=0\frac{a(a-1)}{2(a+b-1)}=0, as desired. Also, for a>0a>0 we have that by the inductive hypothesis
Ea,b=(a1)((a2)(a3)+2(a+b3))+b(a1)(a2)2(a+b1)(a+b3)=(a1)(a2)(a+b3)+2(a1)(a+b3)2(a+b1)(a+b3)=a(a1)2(a+b1) \begin{aligned} E_{a, b} & =\frac{(a-1)((a-2)(a-3)+2(a+b-3))+b(a-1)(a-2)}{2(a+b-1)(a+b-3)} \\ & =\frac{(a-1)(a-2)(a+b-3)+2(a-1)(a+b-3)}{2(a+b-1)(a+b-3)} \\ & =\frac{a(a-1)}{2(a+b-1)} \end{aligned}
as desired.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.