Thread: 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.

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.

Hello, altamash!

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

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?

We have the equaton: .

. . 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?)

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.