HMMT 二月 2011 · 冲刺赛 · 第 30 题
HMMT February 2011 — Guts Round — Problem 30
题目详情
- [ 16 ] How many ways are there to color the vertices of a 2 n -gon with three colors such that no vertex has the same color as its either of its two neighbors or the vertex directly across from it?
解析
- [ 16 ] How many ways are there to color the vertices of a 2 n -gon with three colors such that no vertex has 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 choose one 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 colors 3 are connected by an edge if they can be the colors for d and d for any 1 ≤ i ≤ n − 1. 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 1 6.) Then d must be either ( R, G ), ( B, G ), or ( R, B ). Now, we simply need to count the number of n paths of length n − 1 within this graph from ( R, G ) to one of these three points. Suppose we are making a random walk of n − 1 steps, where at each move we pick one of the three 1 possible edges with probability . We will calculate the probability that the walk ends at one of ( R, G ), 3 ( B, G ), or ( R, B ). Let a and b be the probability that, after i steps, we are at ( R, G ) and ( B, G ), respectively. By i i symmetry, b is also the probability that we are at ( R, B ) after i steps. i 1 Observe that after each move, the probability of arriving at either ( R, G ) or ( G, R ) will always be . 3 1 Therefore, the probability of being at ( G, R ) after i steps is − a . Similarly, the probability of being i 3 1 1 at ( G, B ) is − b and the probability of being at ( B, R ) is − b . i i 3 3 Guts Round a i 1 − a i 3 b b i i 1 1 − b − b i i 3 3 Now, for i ≥ 1 we have the recurrences (( ) ( ) ( )) 1 1 1 1 a = − a + − b + − b i +1 i i i 3 3 3 3 1 1 2 = − a − b i i 3 3 3 (( ) ( ) ) 1 1 1 b = − a + − b + b i +1 i i i 3 3 3 2 1 = − a i 9 3 So then 1 1 2 a = − a − b i +2 i +1 i +1 3 3 3 ( ) 1 1 2 2 1 a = − a − − a i +2 i +1 i 3 3 3 9 3 5 1 2 a = − a + a i +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 solve i 1 2 6 3 3 3 for A and B and get ( ) ( ) i i 1 1 1 1 2 a = + + − i 6 6 3 3 3 Guts Round The answer to the problem is then n − 1 n − 1 6 · 3 ( a + 2 b ) = 6 · 3 ( a + 1 − a − 3 a ) n − 1 n − 1 n − 1 n − 1 n n − 1 = 6 · 3 (1 − 3 a ) n ( ( ( ) ( ) )) n 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 .