Subscribe via feed.


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.

This post is under “MathsChallenge” and has 10 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

10 Responds so far- Add one»

  1. 1. Wizard of Oz Said:

    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.

  2. 2. slavy Said:

    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!

  3. 3. ragknot Said:

    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.

  4. 4. Chris Said:

    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.

  5. 5. ragknot Said:

    I get 20503 also

  6. 6. slavy Said:

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

  7. 7. Chris Said:

    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 * 109997. That’s somewhat better than the 69! that my old calculator maxed out at.

  8. 8. ragknot Said:

    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

  9. 9. slavy Said:

    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…

  10. 10. Wizard of Oz Said:

    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.

Post a reply

PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0