Maths Olympiad Prep

Track / Stage 6 / 208 of 400 #1208 of 1964

Problem 1208

National olympiad, first round
Combinatorics Difficulty 6.4 Find the answer

Tom is searching for the 66 books he needs in a random pile of 3030 books. What is the expected number of books must he examine before finding all 66 books he needs?

A number or a short expression. Spacing and $ signs are ignored.

Official solution

1. Understanding the Problem:
Tom needs to find 6 specific books out of a total of 30 books. We need to determine the expected number of books he must examine before finding all 6 books.

2. Modeling the Problem:
We can model this problem using the concept of expected value in probability. The books are randomly distributed, and we need to find the expected number of books examined to find all 6 specific books.

3. Using the Coupon Collector's Problem:
This problem is analogous to the Coupon Collector's Problem, where we need to collect all 6 different coupons (books in this case). The expected number of trials to collect all n n coupons is given by:
E(n)=n(11+12+13++1n) E(n) = n \left( \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \right)
For our problem, n=6 n = 6 .

4. Calculating the Expected Value:
E(6)=6(11+12+13+14+15+16) E(6) = 6 \left( \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} \right)
We need to compute the harmonic series sum for the first 6 terms:
H6=1+12+13+14+15+16 H_6 = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6}

5. Summing the Harmonic Series:
H6=1+0.5+0.3333+0.25+0.2+0.16672.45 H_6 = 1 + 0.5 + 0.3333 + 0.25 + 0.2 + 0.1667 \approx 2.45

6. Multiplying by the Number of Books:
E(6)=6×2.45=14.7 E(6) = 6 \times 2.45 = 14.7

7. Conclusion:
The expected number of books Tom must examine before finding all 6 books he needs is approximately 14.7.

The final answer is 14.7\boxed{14.7}

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.