HMMT 二月 2014 · COMB 赛 · 第 5 题

HMMT February 2014 — COMB Round — Problem 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 the shares be given out?

解析

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 the shares 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 subtract the number of solutions in which at least one variable is larger than 8. If at least one variable is larger than 8, exactly one of the variables is larger than 8. We have 4 choices for this variable. The number of 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 m m − 1 ( ) ( )( ) 16 − 1 4 (16 − 8) − 1 − = 35 · 13 − 4 · 35 = 315. 4 − 1 1 4 − 1