PUMaC 2019 · 组合（A 组） · 第 5 题

PUMaC 2019 — Combinatorics (Division A) — Problem 5

A candy store has 100 pieces of candy to give away. When you get to the store, there are five people in front of you, numbered from 1 to 5. The i th person in line considers the set of positive integers congruent to i modulo 5 which are at most the number of pieces of candy remaining. If this set is empty, then they take no candy. Otherwise they pick an element of this set and take that many pieces of candy. For example, the first person in line will pick an integer from the set { 1 , 6 , ..., 96 } and take that many pieces of candy. How many ways can the first five people take their share of candy so that after they are done there are at least 35 pieces of candy remaining?

解析

A candy store has 100 pieces of candy to give away. When you get to the store, there are five people in front of you, numbered from 1 to 5. The i th person in line considers the set of positive integers congruent to i modulo 5 which are at most the number of pieces of candy remaining. If this set is empty, then they take no candy. Otherwise they pick an element of this set and take that many pieces of candy. For example, the first person in line will pick an integer from the set { 1 , 6 , ..., 96 } and take that many pieces of candy. How many ways can the first five people take their share of candy so that after they are done there are at least 35 pieces of candy remaining? Proposed by Alan Chung. Answer: 3003 . Solution: We write the product of the generating functions for each person in line. The polynomial is as follows: 6 2 7 5 10 ( x + x + ... )( x + x + ... ) ... ( x + x + ... ) 15 5 10 5 = x (1 + x + x + ... ) n The coefficient of x in this polynomial represents the number of ways for the five people to take a total of n candies. The answer will be the sum of the coefficients of the terms of degree 15 thru 65. Thus, the answer is ( ) ( ) 14 ∑ i 15 = = 3003 . 4 5 i =4