HMMT 二月 2011 · 冲刺赛 · 第 24 题
HMMT February 2011 — Guts Round — Problem 24
题目详情
- [ 14 ] In how many ways may thirteen beads be placed on a circular necklace if each bead is either blue or yellow and no two yellow beads may be placed in adjacent positions? (Beads of the same color are considered 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). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 14 HARVARD-MIT MATHEMATICS TOURNAMENT, 12 FEBRUARY 2011 — GUTS ROUND
解析
- [ 14 ] In how many ways may thirteen beads be placed on a circular necklace if each bead is either blue or yellow and no two yellow beads may be placed in adjacent positions? (Beads of the same color are considered 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 both n yellow for 1 ≤ i < n . Let a and b be the number of arrangements satisfying the additional condition n n that beads n and 1 are not both yellow, and that beads n and 1 are both yellow, respectively. Clearly t = 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 is n n − 1 yellow, then bead n − 1 must be blue, and there are t ways to choose the remaining colors. Hence n − 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; the n remaining colors can be chosen in t ways. Hence n − 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 n denotes 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, while the all-yellow does not. Hence our answer is a − 1 F − F + 12 610 − 89 + 12 13 15 11
- 1 = = = 41 . 13 13 13