HMMT 二月 2023 · 冲刺赛 · 第 22 题

HMMT February 2023 — Guts Round — Problem 22

[18] Let a , a , a , . . . be an infinite sequence where each term is independently and uniformly random 0 1 2 b i in the set { 1 , 2 , 3 , 4 } . Define an infinite sequence b , b , b , . . . recursively by b = 1 and b = a . 0 1 2 0 i +1 i Compute the expected value of the smallest positive integer k such that b ≡ 1 (mod 5). k

解析

[18] Let a , a , a , . . . be an infinite sequence where each term is independently and uniformly random 0 1 2 b i in the set { 1 , 2 , 3 , 4 } . Define an infinite sequence b , b , b , . . . recursively by b = 1 and b = a . 0 1 2 0 i +1 i Compute the expected value of the smallest positive integer k such that b ≡ 1 (mod 5). k Proposed by: Raymond Feng 35 Answer: 16 Solution: Do casework on what a is. 0 If a = 1 then k = 1. 0 If a = 4 then k = 2. 0 If a = 3 then 0 • if a = 1, then k = 2 1 • if a = 2 or 4, then k = 3 1 • if a = 3, then you make no progress. 1 so in expectation it requires E = (2 + 3 + ( E + 1) + 3) / 4 = ⇒ E = 3. If a = 2 then 0 • if a = 1 or 4, then k = 2 1 • if a = 2, then k = 3 1 • if a = 3, then it can be checked that if a = 1 we get k = 3, if a = 2 or 4 then k = 4, and 1 2 2 if a = 3 then we make no progress. Thus, this case is equivalent to the case of a = 3 except 2 0 shifted over by one, so it is 3 + 1 = 4 in expectation. So this case is (2 + 3 + 4 + 2) / 4 in expectation. This means the answer is (1 + (11 / 4) + 3 + 2) / 4 = 35 / 16.