PUMaC 2021 · 组合（A 组） · 第 5 题
PUMaC 2021 — Combinatorics (Division A) — Problem 5
题目详情
- A Princeton slot machine has 100 pictures, each equally likely to occur. One is a picture of a tiger. Alice and Bob independently use the slot machine, and each repeatedly makes independent plays. Alice keeps playing until she sees a tiger, at which point she stops. Similarly, Bob keeps playing until he sees a tiger. Given that Bob played twice longer than Alice, let the a expected number of plays for Alice be with a, b relatively prime positive integers. Find the b remainder when a + b is divided by 1000.
解析
- A Princeton slot machine has 100 pictures, each equally likely to occur. One is a picture of a tiger. Alice and Bob independently use the slot machine, and each repeatedly makes independent plays. Alice keeps playing until she sees a tiger, at which point she stops. Similarly, Bob keeps playing until he sees a tiger. Given that Bob played twice longer than Alice, let the a expected number of plays for Alice be with a, b relatively prime positive integers. Find the b remainder when a + b is divided by 1000. Proposed by: Sunay Joshi Answer: 701 For simplicity, let M = 100. Let the random variables N and N denote the number of plays A B for Alice and Bob, respectively. We want to find the conditional expectation E = E ( N | N = A B 2 N ). By the Tower Law, we have A ∞ ∞ X X E = E ( N | N = 2 N ) = E ( N | N = k, N = 2 N ) P ( N = k | N = 2 N ) = kP ( N = k | N = 2 N ) . A B A A A B A A B A A B A k =1 k =1 By definition, P ( N = k, N = 2 k ) P ( N = k, N = 2 k ) A B A B P P ( N = k | N = 2 N ) = = . A B A P ( N = 2 N ) P ( N = ℓ, N = 2 ℓ ) B A A B ℓ ≥ 1 k − 1 2 k − 1 M − 1 1 M − 1 1 As P ( N = k ) = and P ( N = 2 k ) = , we find P ( N = k, N = A B A B M M M M 3 k M − 1 1 2 k ) = . Thus our denominator becomes 2 M ( M − 1) 3 ℓ X X M − 1 1 P ( N = ℓ, N = 2 ℓ ) = A B 2 M ( M − 1) ℓ ≥ 1 ℓ ≥ 1 2 3 M − 1 3 1 ( M − 1) 1 M = · = . 3 2 3 3 2 M − 1 ( M − 1) M − ( M − 1) ( M − 1) 1 − M Thus our conditional probability is given as 3 k M − 1 1 2 M ( M − 1) P ( N = k | N = 2 N ) = A B A 3 ( M − 1) 1 3 3 2 M − ( M − 1) ( M − 1) 3 k 3 3 M − ( M − 1) M − 1 = . 3 ( M − 1) M Therefore our expected value reduces to ∞ 3 k 3 3 3 3 X X M − ( M − 1) M − 1 M − ( M − 1) k E = k · = kr , 3 3 ( M − 1) M ( M − 1) k ≥ 1 k =1 3 M − 1 1 2 where r = . By differentiating the geometric series = 1+ r + r + . . . and multiplying M 1 − r P ∞ r k by r , we see that kr = , hence the desired expectation is 2 k =1 (1 − r ) 3 3 3 M − ( M − 1) r M E = = . 3 2 3 3 ( M − 1) (1 − r ) M − ( M − 1) a 1000000 For M = 100, the reduced fraction is = . Thus a + b ≡ 701 (mod 1000), our answer. b 29701