HMMT 二月 2011 · 冲刺赛 · 第 14 题
HMMT February 2011 — Guts Round — Problem 14
题目详情
- [ 8 ] Danny has a set of 15 pool balls, numbered 1 , 2 , . . . , 15. In how many ways can he put the balls in 8 indistinguishable bins such that the sum of the numbers of the balls in each bin is 14, 15, or 16? 3 2
解析
- [ 8 ] Danny has a set of 15 pool balls, numbered 1 , 2 , . . . , 15. In how many ways can he put the balls in 8 indistinguishable bins such that the sum of the numbers of the balls in each bin is 14, 15, or 16? Answer: 122 Clearly, the balls numbered 15 , 14 , . . . , 9 , 8 must be placed in separate bins, so we number the bins 15 , 14 , . . . , 9 , 8. Note that bins 15 and 14 may contain only one ball while all other bins must contain at least two balls. We have two cases to examine. Case 1: Only one bin contains exactly one ball. Let a denote the number of ways to place the balls i numbered 1 , 2 , . . . , i − 1 into the bins numbered 15 , 14 , . . . , 15 − i + 1. We can place either i − 1 or i − 2 into the bin numbered 15 − i + 1. If we place i − 1 in there, then there are a ways to finish packing i − 1 the rest. If we place i − 2 in this bin, then i − 1 must be placed in the bin numbered 15 − i + 2, so there are a ways to place the rest of the balls. Therefore a = a + a . Since a = 2 and a = 3, the i − 2 i i − 1 i − 2 1 2 sequence { a } is the Fibonacci sequence, and a = 34. i 7 Case 2: Both bins 14 and 15 contain only one ball. A pair of balls from 1-7 must be put together to one of the bins numbered 8 through 13. This pair has sum at most 8, so we can count for all the cases. Balls Number of packings 1, 2 16 1, 3 10 1, 4 12 1, 5 12 1, 6 10 1, 7 8 2, 3 6 2, 4 4 2, 5 4 2, 6 3 3, 4 2 3, 5 1 Therefore, there are 88 possibilities in this case, and the total number of possibilities is 122. 3 2