HMMT 二月 2022 · 冲刺赛 · 第 26 题

HMMT February 2022 — Guts Round — Problem 26

[14] 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 .

解析

[14] 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 . Proposed by: Gabriel Wu Answer: 100 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 R x 1 this card contributes is f ( x ) + f ( t ) dt . Thus, we can write the equation x 0 Z x f ( x ) = 1 + xf ( x ) + f ( t ) dt. 0 Differentiating both sides gives us ′ f ( x ) 2 ′ ′ f ( x ) = xf ( x ) + f ( x ) + f ( x ) = ⇒ = . f ( x ) 1 − x C e Integrating gives us ln f ( x ) = − 2 ln(1 − x ) + C = ⇒ f ( x ) = . Since f (0) = 1, we know that 2 (1 − x ) − 2 − 2 C = 0, so f ( x ) = (1 − x ) . Thus, we have f (0 . 9) = (1 − 0 . 9) = 100.