HMMT 二月 2010 · COMB 赛 · 第 5 题
HMMT February 2010 — COMB Round — Problem 5
题目详情
- [ 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?
解析
- [ 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