HMMT 二月 2010 · GEN1 赛 · 第 6 题
HMMT February 2010 — GEN1 Round — Problem 6
题目详情
- [ 5 ] John needs to pay 2010 dollars for his dinner. He has an unlimited supply of 2, 5, and 10 dollar notes. In how many ways can he pay? 2010 2009
解析
- [ 5 ] John needs to pay 2010 dollars for his dinner. He has an unlimited supply of 2, 5, and 10 dollar notes. 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 to find the number of nonnegative integer solutions to 2 x + 5 y + 10 z = 2010. Consider this equation mod 2. Because 2 x , 10 z , and 2010 are even, 5 y must also be even, so y must be even. Now consider the 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 a well-known bijection between solutions of this equation and picking 2 of 203 balls in a row on the table ( ) 203 (explained in further detail below), so there are = 20503 ways. 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 two of 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 2010 2009