Maths Olympiad Prep

Track / Stage 6 / 263 of 400 #1263 of 1964

Problem 1263

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. Fractions can be typed as 3/2, and spacing doesn't matter.

Next problem →

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 reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.