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

英文解析

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?
    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 containat 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 ballsinumbered 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 packingi − 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 thereare a ways to place the rest of the balls. Therefore a = a + a . Since a = 2 and a = 3, thei − 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 toone 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