Problem:
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?
Problem:
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?
Solution:
Let the number of 2, 5, and 10 dollar notes John can use be , , and respectively. We wish to find the number of nonnegative integer solutions to .
Consider this equation modulo . Because , , and are even, must also be even, so must be even.
Now consider the equation modulo . Because , , and are divisible by , must also be divisible by , so must be divisible by .
So both and are divisible by . So the equation is equivalent to , or , with , , and 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 (explained in further detail below), so there are ways.
The bijection between solutions of and arrangements of 203 balls in a row is as follows. Given a solution of the equation, we put white balls in a row, then a black ball, then white balls, then a black ball, then 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 , , and from the number of white balls in a row. There are ways to choose 2 of 203 balls to be black, so there are solutions to .