HMMT 二月 2011 · 冲刺赛 · 第 30 题

英文解析

30. [ 16 ] How many ways are there to color the vertices of a 2 n -gon with three colors such that no vertexhas the same color as its either of its two neighbors or the vertex directly across from it?
    n n +1
    Answer: 3 + ( − 2) − 1
    Let the 2 n -gon have vertices A , A , ..., A , in that order. Consider the diagonals d = ( A , A ),
    1 2 2 n 1 1 n +1
    d = ( A , A ), · · · , d = ( A , A ). Suppose the three colors are red (R), green (G), and blue (B).
    2 2 n +2 n n 2 n
    Each diagonal can either be colored ( R, G ), ( G, R ), ( G, B ), ( B, G ), ( B, R ), or ( R, B ). We first chooseone of the six colorings for d , which then constrains the possible colorings for d , which constrains the
    1 2
    possible colorings for d , and so on. This graph shows the possible configurations; two pairs of colorsare connected by an edge if they can be the colors for d and d for any 1 ≤ i ≤ n − 1.3
    i i +1
    ( R, G )
    ( G, R )
    ( B, G ) ( R, B )
    ( G, B ) ( B, R )
    Suppose without loss of generality that d is colored ( R, G ). (At the end, we multiply our answer by
    6.) Then d must be either ( R, G ), ( B, G ), or ( R, B ). Now, we simply need to count the number of 1
    paths of length n − 1 within this graph from ( R, G ) to one of these three points.n
    Suppose we are making a random walk of n − 1 steps, where at each move we pick one of the threepossible edges with probability . We will calculate the probability that the walk ends at one of ( R, G ),1
    ( B, G ), or ( R, B ).3
    Let a and b be the probability that, after i steps, we are at ( R, G ) and ( B, G ), respectively. Byi isymmetry, b is also the probability that we are at ( R, B ) after i steps.
    1 i
    Observe that after each move, the probability of arriving at either ( R, G ) or ( G, R ) will always be .
    Therefore, the probability of being at ( G, R ) after i steps is − a . Similarly, the probability of being 13
    3 i
    1 1
    at ( G, B ) is − b and the probability of being at ( B, R ) is − b .
    i i
    3 3
    Guts Rounda
    1 i − aib b 3
    i i
    1 1 − b − bi i
    3 3
    Now, for i ≥ 1 we have the recurrences
    (( ) ( ) ( ))
    1 1 1 1
    a = − a + − b + − bi +1 i i i
    3 3 3 3
    1 1 2 = − a − bi i
    3 3 3
    (( ) ( ) )
    1 1 1
    b = − a + − b + bi +1 i i i
    3 3 3
    2 1 = − ai
    9 3
    So then
    1 1 2
    a = − a − bi +2 i +1 i +1
    3 3 3
    ( )
    1 1 2 2 1
    a = − a − − ai +2 i +1 i
    3 3 3 9 3
    5 1 2
    a = − a + ai +2 i +1 i
    27 3 9
    ( ) ( ) ( )
    1 1 1 2 1
    a − = − a − + a −
    i +2 i +1 i
    6 3 6 9 6
    2 1 2 1 2
    This recurrence has a characteristic polynomial x + x − , which has roots and − . We can write
    3 9 3 3
    1 1 i 2 i 1
    a = + A ( ) + B ( − ) for some constants A and B for i ≥ 1. Since a = 0 and a = , we can solvei 1 2
    6 3 3 3
    for A and B and get
    ( ) ( )
    i i
    1 1 1 1 2
    a = + + −
    6 6 3 3 3 i
    Guts Round
    The answer to the problem is thenn − 1 n − 1
    6 · 3 ( a + 2 b ) = 6 · 3 ( a + 1 − a − 3 a )
    n − 1 n − 1 n − 1 n − 1 nn − 1 = 6 · 3 (1 − 3 a )
    ( ( ( ) ( ) ))nn n
    1 1 1 1 2
    n − 1 = 6 · 3 1 − 3 + + −
    6 6 3 3 3
    ( ( ) ( ) )
    n n
    1 1 1 2
    n − 1 = 6 · 3 − − −
    2 2 3 3
    n n +1 = 3 + ( − 2) − 1 .