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 randomfrom the set S = { a, b, c } . A move consists of erasing two distinct letters from the board and replacingthem with the third letter in S . What is the probability that Alice can perform a sequence of moveswhich results in one letter remaining on the blackboard?
解析
英文解析
- Alice writes 1001 letters on a blackboard, each one chosen independently and uniformly at randomfrom the set S = { a, b, c } . A move consists of erasing two distinct letters from the board and replacingthem with the third letter in S . What is the probability that Alice can perform a sequence of moveswhich results in one letter remaining on the blackboard?
Proposed by: Daniel Zhu − 999
3 − 3
Answer:
Solution: Let n , n , and n be the number of a ’s, b ’s, and c ’s on the board, respectively The key 4
a b cobservation is that each move always changes the parity of all three of n , n , and n . Since the finala b cconfiguration must have n , n , and n equal to 1, 0, 0 in some order, Alice cannot leave one letter on a b cthe board if n , n , and n start with the same parity (because then they will always have the samea b cparity). Alice also cannot leave one letter on the board if all the letters are initially the same (becauseshe 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 tuplesa b care (1 , 0 , 0), (1 , 1 , 0), and permutations. If n + n + n ≥ 3, assume without loss of generality thata b cn ≥ n ≥ n . Then n ≥ 1 (because otherwise all the letters are a ) and n ≥ 2 (because otherwisea 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 , reducinga b cto a smaller case.
We begin by computing the probability that n , n , and n start with the same parity. Suppose ma b cletters are chosen at random in the same way (so that we are in the case m = 1001). Let x be themprobability that n , n , and n all have the same parity. We have the recurrence x = (1 − x )1
a b c m +1 mbecause when when choosing the ( m + 1)th letter, the n can only attain the same parity if they 3
did not before, and the appropriate letter is drawn. Clearly x = 1, which enables us to computei − m 10
x = (1 + 3 · ( − 3) ) . Then x is the probability that n , n , and n have the same parity.
m 1001 a b c − 10004
The probability that all the letters are initially the same is 3 , as this occurs exactly when all thesubsequent letters match the first. Thus our final answer is
1 3 1 − 1000 − 1001
1 − 3 − (1 + 3 · ( − 3) ) = − .
4 4 4 · 3999