Problem 1200

Solution:

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 $2x + 5y + 10z = 2010$.

Consider this equation modulo $2$. Because $2x$, $10z$, and $2010$ are even, $5y$ must also be even, so $y$ must be even.

Now consider the equation modulo $5$. Because $5y$, $10z$, and $2010$ are divisible by $5$, $2x$ must also be divisible by $5$, so $x$ must be divisible by $5$.

So both $2x$ and $5y$ are divisible by $10$. So the equation is equivalent to $10x' + 10y' + 10z = 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 (explained in further detail below), so there are $\binom{203}{2} = 20503$ ways.

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 $x'$, $y'$, and $z$ from the number of white balls in a row. There are $\binom{203}{2}$ ways to choose 2 of 203 balls to be black, so there are $\binom{203}{2}$ solutions to $x' + y' + z = 201$.