PUMaC 2008 · 组合（B 组） · 第 8 题

8. In how many ways can Alice, Bob, Charlie, David, and Eve split 16 marbles among themselves so that no two of them have the same number of marbles? ( ANS: 1200: Suppose we have a valid 5-tuple a < b < c < d < e . Let A = a , B = b − a − 1, C = c − b − 1, D = d − c − 1 and E = e − d − 1. Now we have A, B, C, D ≥ 0 and 3 Combinatorics A + B + C + D + E = 6 We can just enumerate the solutions: for 16: 10001 01010 01002 00200 00111 00103 00030 00022 00014 00006 yielding that there are 10 ∗ 5! solutions. CB: AP)

xxxx xx x x In how many ways can you fill in the xs with the numbers 1-8 so that for each x, the numbers below and to the right are higher. ( ANS: 90 ABCD EF G H Clearly A = 1. Now either B or E is 2, so we may assume B = 2 and then double the number we get. We now have three cases: 12 CD 3 F G H 4 Combinatorics 12 CD 4 F G H 12 CD 5 F G H ( E cannot be 6 or higher since F, G, H are all larger than E .) For the first case, there are 5 ( ) 4 choices for F among 4 , 5 , 6 , 7 , 8, and then ways to split the remaining numbers between C, D 2 and G, H . Thus we get 5 · 6 = 30 possibilities. ( ) 4 For the second case, there are ways of choosing F, G, H among 5 , 6 , 7 , 8, and then three 3=4 ways of choosing F among F, G, H , making for 4 · 3 = 12 possibilities (after choosing F, G, H , the rest is forced). For the last case, there are three choices for F among 6 , 7 , 8, and once F is chosen, the rest is forced. Thus we get 3 possibilities. In total, we have 30 + 12 + 3 = 45 possibilities. Doubling this, we get 90 as claimed. CB: AP)