HMMT 二月 2015 · COMB 赛 · 第 22 题

HMMT February 2015 Saturday 21 February 2015 Combinatorics

1. Evan’s analog clock displays the time 12:13; the number of seconds is not shown. After 10 seconds elapse, it is still 12:13. What is the expected number of seconds until 12:14?
2. Victor has a drawer with 6 socks of 3 different types: 2 complex socks, 2 synthetic socks, and 2 trigonometric socks. He repeatedly draws 2 socks at a time from the drawer at random, and stops if the socks are of the same type. However, Victor is “synthetic-complex type-blind”, so he also stops if he sees a synthetic and a complex sock. What is the probability that Victor stops with 2 socks of the same type? Assume Victor returns both socks to the drawer after each step.
3. Starting with the number 0, Casey performs an infinite sequence of moves as follows: he chooses a 1 number from { 1 , 2 } at random (each with probability ) and adds it to the current number. Let p m 2 be the probability that Casey ever reaches the number m . Find p − p . 20 15
4. Alice Czarina is bored and is playing a game with a pile of rocks. The pile initially contains 2015 rocks. At each round, if the pile has N rocks, she removes k of them, where 1 ≤ k ≤ N , with each possible k having equal probability. Alice Czarina continues until there are no more rocks in the pile. Let p be the probability that the number of rocks left in the pile after each round is a multiple of 5. If p is of c a b the form 5 · 31 · , where a, b are integers and c, d are positive integers relatively prime to 5 · 31, find d a + b .
5. For positive integers x , let g ( x ) be the number of blocks of consecutive 1’s in the binary expansion of x . For example, g (19) = 2 because 19 = 10011 has a block of one 1 at the beginning and a block 2 of two 1’s at the end, and g (7) = 1 because 7 = 111 only has a single block of three 1’s. Compute 2 g (1) + g (2) + g (3) + · · · + g (256).
6. Count the number of functions f : Z → { ‘green’ , ‘blue’ } such that f ( x ) = f ( x + 22) for all integers x and there does not exist an integer y with f ( y ) = f ( y + 2) = ‘green’. 1
7. 2015 people sit down at a restaurant. Each person orders a soup with probability . Independently, 2 1 each person orders a salad with probability . What is the probability that the number of people who 2 ordered a soup is exactly one more than the number of people who ordered a salad?
8. Let S be the set of all 3-digit numbers with all digits in the set { 1 , 2 , 3 , 4 , 5 , 6 , 7 } (so in particular, all three digits are nonzero ). For how many elements abc of S is it true that at least one of the (not necessarily distinct) “digit cycles” abc, bca, cab is divisible by 7? (Here, abc denotes the number whose base 10 digits are a , b , and c in that order.)
9. Calvin has a bag containing 50 red balls, 50 blue balls, and 30 yellow balls. Given that after pulling out 65 balls at random (without replacement), he has pulled out 5 more red balls than blue balls, what is the probability that the next ball he pulls out is red?
10. A group of friends, numbered 1 , 2 , 3 , . . . , 16, take turns picking random numbers. Person 1 picks a number uniformly (at random) in [0 , 1], then person 2 picks a number uniformly (at random) in [0 , 2], and so on, with person k picking a number uniformly (at random) in [0 , k ]. What is the probability that the 16 numbers picked are strictly increasing?