HMMT 二月 2012 · COMB 赛 · 第 10 题

英文解析

10. Jacob starts with some complex number x other than 0 or 1. He repeatedly flips a fair coin. If theth 10
    n flip lands heads, he lets x = 1 − x , and if it lands tails he lets x = . Over all possiblen n − 1 nn − 1 xchoices 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 flippingnx x x − 1 1 − xprocedure 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 = + + · · · + .
    1 4 20110
    ( ) ( ) ( ) ( ) ( ) ( )
    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
    2 2012 23
    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 adjacentvalues are equal. Let y be a value that is equal to an adjacent value. Then y = or y = 1 − y , which 10
    1 1 1 ygives 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 Testoriginal 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 ζ = . Thenx 2 2
    we get that the cycle of values is ζ, ζ, ζ, ζ, ζ, ζ , and since at the end we are always an even number ofspaces 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 havexa y such that f ( g ( f ( y ))) = y , or = x , so x = 2. In this case we obtain the same cycle of numbersx − 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