HMMT 二月 2014 · COMB 赛 · 第 5 题

英文解析

5. Eli, Joy, Paul, and Sam want to form a company; the company will have 16 shares to split among the
   4 people. The following constraints are imposed:
   • Every person must get a positive integer number of shares, and all 16 shares must be given out.
   • No one person can have more shares than the other three people combined.
   Assuming that shares are indistinguishable, but people are distinguishable, in how many ways can theshares be given out?
   Answer: 315 We are finding the number of integer solutions to a + b + c + d = 16 with 1 ≤
   a, b, c, d ≤ 8. We count the number of solutions to a + b + c + d = 16 over positive integers, and subtractthe number of solutions in which at least one variable is larger than 8. If at least one variable is largerthan 8, exactly one of the variables is larger than 8. We have 4 choices for this variable. The numberof solutions to a + b + c + d = 16 over positive integers, where a > 8, is just the number of solutions
   ′ ′
   to a + b + c + d = 8 over positive integers, since we can substitute a = a − 8. Thus, by the stars and
   ( )
   n − 1
   bars formula (the number of positive integer solutions to x + · · · + x = n is ), the answer is
   1 mm − 1
   ( ) ( )( )
   16 − 1 4 (16 − 8) − 1 − = 35 · 13 − 4 · 35 = 315.
   4 − 1 1 4 − 1