Maths Olympiad Prep

Library / /640 of 1394

Combinatorics Difficulty 5.2 AIME, harder Find the answer United States

Problem:

Diana is playing a card game against a computer. She starts with a deck consisting of a single card labeled 0.90.9. Each turn, Diana draws a random card from her deck, while the computer generates a card with a random real number drawn uniformly from the interval [0,1][0,1]. If the number on Diana's card is larger, she keeps her current card and also adds the computer's card to her deck. Otherwise, the computer takes Diana's card. After kk turns, Diana's deck is empty. Compute the expected value of kk.

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

Solution

Solution:

By linearity of expectation, we can treat the number of turns each card contributes to the total independently. Let f(x)f(x) be the expected number of turns a card of value xx contributes (we want f(0.9)f(0.9)). If we have a card of value xx, we lose it after 11 turn with probability 1x1-x. If we don't lose it after the first turn, which happens with probability xx, then given this, the expected number of turns this card contributes is f(x)+1x0xf(t)dtf(x) + \frac{1}{x} \int_{0}^{x} f(t) dt. Thus, we can write the equation
f(x)=1+xf(x)+0xf(t)dt f(x) = 1 + x f(x) + \int_{0}^{x} f(t) dt
Differentiating both sides gives us
f(x)=xf(x)+f(x)+f(x)f(x)f(x)=21x f'(x) = x f'(x) + f(x) + f(x) \Longrightarrow \frac{f'(x)}{f(x)} = \frac{2}{1-x}
Integrating gives us lnf(x)=2ln(1x)+Cf(x)=eC(1x)2\ln f(x) = -2 \ln (1-x) + C \Longrightarrow f(x) = \frac{e^{C}}{(1-x)^{2}}. Since f(0)=1f(0) = 1, we know that C=0C = 0, so f(x)=(1x)2f(x) = (1-x)^{-2}. Thus, we have f(0.9)=(10.9)2=100f(0.9) = (1-0.9)^{-2} = 100.

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.