HMMT 二月 2010 · COMB 赛 · 第 5 题

英文解析

5. [ 5 ] John needs to pay 2010 dollars for his dinner. He has an unlimited supply of 2, 5, and 10 dollarnotes. In how many ways can he pay?
   Answer: 20503
   Let the number of 2, 5, and 10 dollar notes John can use be x , y , and z respectively. We wish tofind the number of nonnegative integer solutions to 2 x + 5 y + 10 z = 2010. Consider this equationmod 2. Because 2 x , 10 z , and 2010 are even, 5 y must also be even, so y must be even. Now considerthe equation mod 5. Because 5 y , 10 z , and 2010 are divisible by 5, 2 x must also be divisible by 5,
   so x must be divisible by 5. So both 2 x and 5 y are divisible by 10. So the equation is equivalent to
   ′ ′ ′ ′ ′ ′
   10 x + 10 y + 10 z = 2010, or x + y + z = 201 , with x , y , and z nonnegative integers. There is awell-known bijection between solutions of this equation and picking 2 of 203 balls in a row on the table
   ( )
   (explained in further detail below), so there are = 20503 ways.203
   ′ ′2
   The bijection between solutions of x + y + z = 201 and arrangements of 203 balls in a row is as follows.
   ′ ′
   Given a solution of the equation, we put x white balls in a row, then a black ball, then y white balls,
   then a black ball, then z white balls. This is like having 203 balls in a row on a table and picking twoof them to be black. To go from an arrangement of balls to a solution of the equation, we just read off
   ( )
   ′ ′203
   x , y , and z from the number of white balls in a row. There are ways to choose 2 of 203 balls to
   ( )2
   ′ ′203
   be black, so there are solutions to x + y + z = 201. 2