CombinatoricsDifficulty 5.2AIME, harderFind the answerUnited States
Problem:
Diana is playing a card game against a computer. She starts with a deck consisting of a single card labeled 0.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]. 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 k turns, Diana's deck is empty. Compute the expected value of k.
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) be the expected number of turns a card of value x contributes (we want f(0.9)). If we have a card of value x, we lose it after 1 turn with probability 1−x. If we don't lose it after the first turn, which happens with probability x, then given this, the expected number of turns this card contributes is f(x)+x1∫0xf(t)dt. Thus, we can write the equation f(x)=1+xf(x)+∫0xf(t)dt Differentiating both sides gives us f′(x)=xf′(x)+f(x)+f(x)⟹f(x)f′(x)=1−x2 Integrating gives us lnf(x)=−2ln(1−x)+C⟹f(x)=(1−x)2eC. Since f(0)=1, we know that C=0, so f(x)=(1−x)−2. Thus, we have f(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.