HMMT 二月 2021 · COMB 赛 · 第 5 题
HMMT February 2021 — COMB Round — Problem 5
题目详情
- Teresa the bunny has a fair 8-sided die. Seven of its sides have fixed labels 1 , 2 , . . . , 7, and the label on the eighth side can be changed and begins as 1. She rolls it several times, until each of 1 , 2 , . . . , 7 appears at least once. After each roll, if k is the smallest positive integer that she has not rolled so a far, she relabels the eighth side with k . The probability that 7 is the last number she rolls is , where b a and b are relatively prime positive integers. Compute 100 a + b .
解析
- Teresa the bunny has a fair 8-sided die. Seven of its sides have fixed labels 1 , 2 , . . . , 7, and the label on the eighth side can be changed and begins as 1. She rolls it several times, until each of 1 , 2 , . . . , 7 appears at least once. After each roll, if k is the smallest positive integer that she has not rolled so a far, she relabels the eighth side with k . The probability that 7 is the last number she rolls is , where b a and b are relatively prime positive integers. Compute 100 a + b . Proposed by: Milan Haiman Answer: 104 1 Solution 1: Let n = 7 and p = . 4 Let q be the probability that n is the last number rolled, if k numbers less than n have already been k rolled. We want q and we know q = 1. 0 n − 1 We have the relation [ ] k k + 1 q = (1 − p ) q + 1 − (1 − p ) q . k k k +1 n − 1 n − 1 This rearranges to [ ] [ ] k k + 1 1 − (1 − p ) q = 1 − (1 − p ) q . k k +1 n − 1 n − 1 This means that the expression on the LHS does not depend on k , so [1 − 0] · q = [1 − (1 − p )] · q = p. 0 n − 1 Solution 2: For a given sequence of Teresa’s rolls, let x be the i th distinct number rolled. We want i to compute the probability that x = 7. 7 For a given index i , we say that x is correct if x is the least positive integer not in { x , . . . , x } . i i 1 i − 1 Note that the probability of a given sequence x , . . . , x depends only on the number of correct x , 1 7 i since the probability of rolling the correct number on a given roll is higher by a factor of 2. ′ ′ Now, suppose x = 7. Consider x = x + 1 for 1 < i ≤ 7, and x = 1. Note that this operation on 7 i − 1 1 i sequences x , . . . , x pairs sequences ending in 7 with sequences starting with 1. Additionally, we have 1 7 ′ ′ that x and x are both correct, and that x is correct if and only if x is correct. Thus x , . . . , x 7 i − 1 1 7 1 i ′ ′ and x , . . . , x have the same probability. 1 7 So, we conclude that the probability of x = 7 is the same as the probability of x = 1. But this is 7 1 1 just . 4