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

英文解析

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 orderfive 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 whichisums to 5. Therefore, there is exactly one order for each partition of 5: order the elements of thepartition from largest to smallest and use these parts as the x . For example, the partition 3 + 2
   corresponds to the order 5 + 3 , 4 + 2 , 3 , 2 , 1. There are thus 7 orders, corresponding to the 7 partitionsiof 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)