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

英文解析

24. [ 14 ] In how many ways may thirteen beads be placed on a circular necklace if each bead is either blueor yellow and no two yellow beads may be placed in adjacent positions? (Beads of the same color areconsidered to be identical, and two arrangements are considered to be the same if and only if each can be obtained from the other by rotation).
    Answer: 41
    Let t be the number of arrangements of n beads in a row such that bead i and i + 1 are not bothnyellow for 1 ≤ i < n . Let a and b be the number of arrangements satisfying the additional conditionn nthat beads n and 1 are not both yellow, and that beads n and 1 are both yellow, respectively. Clearlyt = a + b .
    n n n
    First consider t . If bead n is blue, there are t ways to choose the remaining colors. If bead n isn n − 1
    yellow, then bead n − 1 must be blue, and there are t ways to choose the remaining colors. Hencen − 2
    t = t + t .
    n n − 1 n − 2
    Next consider b . In this case beads 1 and n are both yellow, so beads 2 and n − 1 must be blue; thenremaining colors can be chosen in t ways. Hencen − 4
    b = t .
    n n − 4
    From t = 1 and t = 2 we see that t = F and b = F and so a = F − F , where F
    0 1 n n +2 n n − 2 n n +2 n − 2 ndenotes the n th Fibonacci number.
    Next, since 13 is prime, a circular arrangement corresponds to exactly 13 straight-line arrangements,
    except for when all beads are the same color. The all-blue’s arrangement satisfies our condition, whilethe all-yellow does not. Hence our answer isa − 1 F − F + 12 610 − 89 + 12
    13 15 11 + 1 = = = 41 .
    13 13 13