HMMT 十一月 2009 · GEN2 赛 · 第 8 题

HMMT November 2009 — GEN2 Round — Problem 8

[ 5 ] A single burger is not enough to satisfy a guy’s hunger. The five guys go to Five Guys’ Restaurant, which has 20 different meals on the menu. Each meal costs a different integer dollar amount between $1 and$ 20. The five guys have $20 to split between them, and they want to use all the money to order five different meals. How many sets of five meals can the guys choose?

解析

[ 5 ] A single burger is not enough to satisfy a guy’s hunger. The five guys go to Five Guys’ Restaurant, which has 20 different meals on the menu. Each meal costs a different integer dollar amount between $1 and$ 20. The five guys have $20 to split between them, and they want to use all the money to order five different meals. How many sets of five meals can the guys choose? Answer: 7 Suppose the meals, sorted in descending order, cost 5 + x , 4 + x , . . . , 1 + x . To satisfy 1 2 5 the conditions in the problem, the x must be a non-increasing sequence of non-negative integers which i sums to 5. Therefore, there is exactly one order for each partition of 5: order the elements of the partition from largest to smallest and use these parts as the x . For example, the partition 3 + 2 i corresponds to the order 5 + 3 , 4 + 2 , 3 , 2 , 1. There are thus 7 orders, corresponding to the 7 partitions of 5 below. 1 + 1 + 1 + 1 + 1 , 1 + 1 + 1 + 2 , 1 + 2 + 2 , 1 + 1 + 3 , 2 + 3 , 1 + 4 , 5 These partitions yield the following seven orders: (2 , 3 , 4 , 5 , 6) , (1 , 3 , 4 , 5 , 7) , (1 , 2 , 4 , 6 , 7) , (1 , 2 , 3 , 5 , 7) , (1 , 2 , 3 , 6 , 8) , (1 , 2 , 3 , 5 , 9) , (1 , 2 , 3 , 4 , 10)