HMMT 二月 2020 · COMB 赛 · 第 6 题
HMMT February 2020 — COMB Round — Problem 6
题目详情
- Alice writes 1001 letters on a blackboard, each one chosen independently and uniformly at random from the set S = { a, b, c } . A move consists of erasing two distinct letters from the board and replacing them with the third letter in S . What is the probability that Alice can perform a sequence of moves which results in one letter remaining on the blackboard?
解析
- Alice writes 1001 letters on a blackboard, each one chosen independently and uniformly at random from the set S = { a, b, c } . A move consists of erasing two distinct letters from the board and replacing them with the third letter in S . What is the probability that Alice can perform a sequence of moves which results in one letter remaining on the blackboard? Proposed by: Daniel Zhu − 999 3 − 3 Answer: 4 Solution: Let n , n , and n be the number of a ’s, b ’s, and c ’s on the board, respectively The key a b c observation is that each move always changes the parity of all three of n , n , and n . Since the final a b c configuration must have n , n , and n equal to 1, 0, 0 in some order, Alice cannot leave one letter on a b c the board if n , n , and n start with the same parity (because then they will always have the same a b c parity). Alice also cannot leave one letter on the board if all the letters are initially the same (because she will have no moves to make). We claim that in all other cases, Alice can make a sequence of moves leaving one letter on the board. The proof is inductive: the base cases n + n + n ≤ 2 are easy to verify, as the possible tuples a b c are (1 , 0 , 0), (1 , 1 , 0), and permutations. If n + n + n ≥ 3, assume without loss of generality that a b c n ≥ n ≥ n . Then n ≥ 1 (because otherwise all the letters are a ) and n ≥ 2 (because otherwise a b c b a ( n , n , n ) = (1 , 1 , 1), which all have the same parity). Then Alice will replace a and b by c , reducing a b c to a smaller case. We begin by computing the probability that n , n , and n start with the same parity. Suppose m a b c letters are chosen at random in the same way (so that we are in the case m = 1001). Let x be the m 1 probability that n , n , and n all have the same parity. We have the recurrence x = (1 − x ) a b c m +1 m 3 because when when choosing the ( m + 1)th letter, the n can only attain the same parity if they i did not before, and the appropriate letter is drawn. Clearly x = 1, which enables us to compute 0 1 − m x = (1 + 3 · ( − 3) ) . Then x is the probability that n , n , and n have the same parity. m 1001 a b c 4 − 1000 The probability that all the letters are initially the same is 3 , as this occurs exactly when all the subsequent letters match the first. Thus our final answer is 1 3 1 − 1000 − 1001 1 − 3 − (1 + 3 · ( − 3) ) = − . 999 4 4 4 · 3