# SAT Math Counting Problem

• Sep 3rd 2010, 10:09 PM
altamash
SAT Math Counting Problem
John went to dinner and had a bill of 2010 dollars. He only has 1,2,5, and 10 dollar bills. How many different ways can he pay for dinner.
• Sep 4th 2010, 04:51 AM
undefined
Quote:

Originally Posted by altamash
John went to dinner and had a bill of 2010 dollars. He only has 1,2,5, and 10 dollar bills. How many different ways can he pay for dinner.

Here is one way.

How many ways can we spend 2, 5, and 10 dollar bills using at most 2010 dollars? The 1 dollar bills are used to make up any difference. Include 0 as valid way to spend 2,5,10.

Fix the number of 10 dollar bills as 0. Then we spend at most 2010 dollars with 2 and 5. Fix # of 5s at 0, then # ways is 2010/2+1. Fix # of 5's at 1 then # ways is floor(2005/2)+1. Write the sum.

Now fix number of 10 dollar bills as 1. We spend at most 2000 with 2 and 5. Fix # 5 at 0, get 2000/2+1. Etc. Write sum.

Compute sum of sums.
• Sep 4th 2010, 09:24 AM
Soroban
Hello, altamash!

I don't have a solution, just another approach.

Quote:

John went to dinner and had a bill of 2010 dollars.
He only has one-, two-, five-, and 10-dollar bills.
How many different ways can he pay for dinner?

$\displaystyle \text{Let: }\;\begin{Bmatrix} T &=& \text{number of tens} \\ F &=& \text{number of fives} \\ D &=& \text{number of "deuces"} \\ S &=& \text{number of singles} \end{Bmatrix}$

We have the equaton: . $\displaystyle 10T + 5F + 2D + S \:=\:2010$

. . and we want the number of nonnegative integral solutions.

I'll wait in the car . . .

By the way, what was the main course of John's dinner?
. . White truffles drenched in saffron sauce?
(Or maybe he went to Wendy's and is a big tipper?)
• Sep 5th 2010, 11:11 AM
altamash
lol soraban, i was wondering what he had for dinner also. The thing is the problem was originally just 2,5, and 10 dollar bills. That was easy because there were no combination of adding 2 and 5 together to make a mulitple of ten. so the solution was 20503. but with the introduction of 1 dollar bills you can add to the two dollar bills and the 5 dollar bills. This will lead to a huger combination, and i don't see a pattern.