HMMT 二月 2012 · COMB 赛 · 第 10 题
HMMT February 2012 — COMB Round — Problem 10
题目详情
- Jacob starts with some complex number x other than 0 or 1. He repeatedly flips a fair coin. If the 0 th 1 n flip lands heads, he lets x = 1 − x , and if it lands tails he lets x = . Over all possible n n − 1 n x n − 1 choices of x , what are all possible values of the probability that x = x ? 0 2012 0 th 15 Annual Harvard-MIT Mathematics Tournament Saturday 11 February 2012 Combinatorics Test Name Team ID# School Team
Score:
解析
- Jacob starts with some complex number x other than 0 or 1. He repeatedly flips a fair coin. If the 0 1 th n flip lands heads, he lets x = 1 − x , and if it lands tails he lets x = . Over all possible n n − 1 n x n − 1 choices of x , what are all possible values of the probability that x = x ? 0 2012 0 2011 2 +1 1 Answer: 1, Let f ( x ) = 1 − x , g ( x ) = . Then for any x , f ( f ( x )) = x and g ( g ( x )) = x . 2011 3 · 2 x 1 x 1 Furthermore, f ( g ( x )) = 1 − , g ( f ( g ( x ))) = , f ( g ( f ( g ( x )))) = , g ( f ( g ( f ( g ( x ))))) = 1 − x = x x − 1 1 − x 1 1 x 1 f ( x ), so for all n , x is one of x, , 1 − , , , 1 − x , and we can understand the coin flipping n x x x − 1 1 − x procedure as moving either left or right with equal probability along this cycle of values. For most x , all six of these values are distinct. In this case, suppose that we move right R times and left 2012 − R times between x and x . For x = x , we need to have that R − 2012 + R ≡ 0 (mod 6), 0 2012 2012 0 ( ) ( ) ( ) 2012 2012 2012 or R ≡ 1 (mod 3). The number of possible ways to return to x is then a = + + · · · + . 0 1 4 2011 ( ) ( ) ( ) ( ) ( ) ( ) 2012 2012 2012 2012 2012 2012 2012 Let b = + + · · · + = + + · · · + . Then we have a + 2 b = 2 0 3 2010 2 5 2012 2012 2012 2 2012 (1+1) +(1+ ω ) +(1+ ω ) and that b = , where ω is a primitive third root of unity. It can be seen 3 2 2012 2 that 1 + ω is a primitive sixth root of unity and 1 + ω is its inverse, so (1 + ω ) = (1 + ω ) = ω , 2012 2012 2 2012 2 · 2 − 1 2012 2 +2 and similarly (1 + ω ) = ω . Therefore, b = , so a = 2 − 2 b = , and our desired 3 3 2012 2011 a 2 +2 2 +1 probability is then = = . 2012 2012 2011 2 3 · 2 3 · 2 For some x , however, the cycle of values can become degenerate. It could be the case that two adjacent 0 1 values are equal. Let y be a value that is equal to an adjacent value. Then y = or y = 1 − y , which y 1 1 1 gives y ∈ {− 1 , } . Therefore, this only occurs in the cycle of values − 1 , 2 , , , 2 , − 1. In this case, note 2 2 2 that after 2012 steps we will always end up an even number of steps away from our starting point, and each of the numbers occupies two spaces of opposite parity, so we would need to return to our Combinatorics Test original location, just as if all six numbers were distinct. Therefore in this case we again have that the 2011 2 +1 probability that x = x is . 2012 0 2011 3 · 2 It is also possible that two numbers two apart on the cycle are equal. For this to be the case, let y be √ √ 1 2 1 ± i 3 1+ i 3 the value such that f ( g ( y )) = y . Then 1 − = x , or x − 1 = x , so x = . Let ζ = . Then x 2 2 we get that the cycle of values is ζ, ζ, ζ, ζ, ζ, ζ , and since at the end we are always an even number of spaces away from our starting location, the probability that x = x is 1. 2012 0 Finally, we need to consider the possibility that two opposite numbers are equal. In this case we have x a y such that f ( g ( f ( y ))) = y , or = x , so x = 2. In this case we obtain the same cycle of numbers x − 1 2011 2 +1 in the case where two adjacent numbers are equal, and so we again obtain the probability . 2011 3 · 2 2011 2 +1 Therefore, the only possibilities are 1 , . 2011 3 · 2 Combinatorics Test