## $2010

Posted by Chris on December 10, 2011 – 11:49 am

How many ways can you make $2010 dollars, using only $2, $5 and $10 notes?

e.g. 5 *$2 + 2*$5 + 1990*$10 or 201*$10.

Posted by Chris on December 10, 2011 – 11:49 am

How many ways can you make $2010 dollars, using only $2, $5 and $10 notes?

e.g. 5 *$2 + 2*$5 + 1990*$10 or 201*$10.

December 10th, 2011 at 3:58 pm

For each $10 we can have one 10, two 5’s or five 2’s.

So for the first $10 there are three possibilities.

For the first $20 we can have two 10’s, four 5’s, ten 2’s, a 10 and two 5’s, a 10 and five 2’s, or two 5’s and five 2’s, i.e six possibilities for the first $20.

Similarly we find twelve possibilities for the first $30, and so on.

So, for $2010 we have 201 x 202 = 40602 possible combinations.

December 10th, 2011 at 4:16 pm

I’ll go with 20503 Wiz, the “similarity” part of your post is wrong, and thus the inductive conjecture. There are only 10 possibilities for the first 30$, not 12!

December 10th, 2011 at 7:14 pm

Well, Who’s dollars? English? American? Spanish?

Just kidding, I figure one dollar a year since year zero.

…….

Or did you mean Pounds for Britain?

I got to get back to work, or I will miss my dollar for today.

December 10th, 2011 at 8:46 pm

Hi Ragknot. You’re right – the question was set for the year 2010.

—

Of course, Slavy has the right answer. I’m curious as to how he worked it out.

I posted the problem because I liked the solution. I’ll post it soon.

December 11th, 2011 at 12:26 am

I get 20503 also

December 11th, 2011 at 2:08 am

Hi Chris. I’ll fulfill your request and post my solution – those, who are still thinking on the problem should better not read the following.

Since 2010 is divisible by 5, and so are 10 and 5, it follows that the number of $2 bills is divisible by 5, i.e., we have 5x notes, with x an integer. Analogously, using mod 2 arithmetic we conclude that the $5 notes are 2y, with y an integer. denote by z the $10 notes. Then 5x*2+2y*5+z*10=2010, or x+y+z=201. Hence, the problem is equivalent to the different integer representations of 201 as a sum of 3 summands. The latter is classical combinatorics – combinations with repetitions, but I prefer to bring it down to standard combinations. The pair (x+1, x+y+2) satisfies 0 < x+1 < x+y+2 <= 203, and apart from that the two numbers can be arbitrary. Moreover, this pair uniquely defines the triple (x,y,z), so it suffices to only count the different (ordered) pairs. The number is simply C(203,2).

December 11th, 2011 at 5:31 am

Hi Slavy. Except for how you got the last bit, that’s precisely the solution the source site gave, including the use of modulo arithmetic (rather than common-sense) to determine that there must be a multiple of five $2 notes and a multiple of two $5 notes.

The source site made an analogy using 201 white balls and 2 black balls that act as boundaries, dividing the 201 white balls in up to three groups. Then the problem is how many ways can you arrange the two black balls in the 203 balls, and that is C(203,2) = 20503.

I’m still struggling with it but think it’s an excellent argument. I don’t remember having ever seen it before.

Nobody challenged the existence of the US $2 notes – that’s just as well, as they really do exist, but are fairly rare; so much so that some shops don’t know that they are legal tender.

Aside: The 64 bit Windows calculator can handle uo to 3248! ≈ 1.9736342530860425312047080034031 * 10

^{9997}. That’s somewhat better than the 69! that my old calculator maxed out at.December 11th, 2011 at 6:08 am

Sub test()

Dim Times, Twos, Fives, Tens As Integer

For Twos = 0 To 2010 / 2

For Fives = 0 To 2010 / 5

If Twos * 2 + Fives * 5 > 2010 Then Exit For

Tens = (2010 – (Twos * 2 + Fives * 5)) / 10

If Twos * 2 + Fives * 5 + Tens * 10 = 2010 Then

Times = Times + 1

Debug.Print Times, Twos, Fives, Tens

End If

Next Fives, Twos

End Sub

December 11th, 2011 at 8:34 am

Hi Chris. As I mentioned in my previous post, the trick with the two black balls (resp. with adding 1 and 2 to the elements) is very basic and helps you derive the formula for combinations with repetitions: i.e., if you have N different objects and you want to pick k of them, but whenever you pick an object, another one identical to the first one takes its place, then you have (N+k-1 choose k) different outcomes. The same here – you have a fixed sum x+y+z, so you need to determine only the first two numbers to get the whole triple. Each of them is between 0 and 201, i.e. you have N=202 and k=2, and they can coincide, so “repetitions” are allowed…

December 12th, 2011 at 1:42 pm

Persisting with my “inductive” approach in post # 1, and with thanks to Slavy for correcting my error for the number of possibilities in the first $30, it would seem that for n lots of $10 then (n+1)(n+2)/2 looks a good fit for the number of possible combinations.

So, for n = 201 we get 202 x 203 / 2 = 20503.

This is a lot simpler than resorting to modulo arithmetic or combina-whatsits.

To me, “inductive” seems a fancy term for the fine old tradition of retro-fitting your theory to fit the facts. Still, I concede that Slavy’s a priori approach is purer than my a posteriori approach (double entendre intended).

All right, that’s enough from me, I think.