wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Change
        
(Message started by: THUDandBLUNDER on Jan 1^st, 2005, 11:56am)

Title: Change
Post by THUDandBLUNDER on Jan 1^st, 2005, 11:56am

In how many different ways can we make change for 50 cents?

Title: Re: Change
Post by Grimbal on Jan 1^st, 2005, 2:33pm

1. what are the available coins?
2. are solutions like give 1 euro and return 50 cents ok? (assuming they are cents of an euro)

Title: Re: Change
Post by THUDandBLUNDER on Jan 1^st, 2005, 4:09pm

Using only the US coins of 1, 5, 10, 25, and 50 cents.

Title: Re: Change
Post by Barukh on Jan 2^nd, 2005, 2:11am

I assume PCs are not allowed? Otherwise, look here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1102675745).

Title: Re: Change
Post by THUDandBLUNDER on Jan 2^nd, 2005, 8:39am

on 01/02/05 at 02:11:17, Barukh wrote:

I assume PCs are not allowed? Otherwise, look here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1102675745).

Yes, perhaps I should have put this in CS.
Although it's not a very interesting problem, the answer is slightly interesting.

Title: Re: Change
Post by Grimbal on Jan 3^rd, 2005, 2:50am

It happens to be ::[hide]50[/hide]::

Title: Re: Change
Post by THUDandBLUNDER on Jan 3^rd, 2005, 5:23am

I found it here (http://www.siam.org/journals/problems/downloadfiles/02-005.pdf).

Title: Re: Change
Post by Sir Col on Jan 3^rd, 2005, 6:43am

As the numbers here are well chosen, it can be solved analytically...

Let the number of 1,5,10,25,50 cent coins be represented by a,b,c,d,e respectively.

We shall consider the two cases, where e=0 or e=1.

e=1 is trivial as a=b=c=d=0 (1 solution).

If e=0, 0[le]d[le]2, and we shall consider each of the three cases.

If d=2 we get the trivial solution, a=b=c=e=0 (1 solution).

If d=0 the 50 cents must be made up of 1,5,10, and we can see that 0[le]c[le]5.
If c=0 the 50 cents must be made up of 1 and 5, therefore 0[le]b[le]10 and there are 11 solutions, as the number of 1 cent coins (a) is fixed for each of these values of b. In the same way,
c=1, 40 cents remaining, so 0[le]b[le]8 (9 solutions)
c=2, 30 cents remaining, so 0[le]b[le]6 (7 solutions)
c=3, 20 cents remaining, so 0[le]b[le]4 (5 solutions)
c=4, 10 cents remaining, so 0[le]b[le]2 (3 solutions)
c=5, 0 cents remaining, so b=0 (1 solution)

If d=1 the remaining 25 cents must be made up of 1,5,10 and 0[le]c[le]2.
c=0, 25 cents remaining, so 0[le]b[le]5 (6 solutions)
c=1, 15 cents remaining, so 0[le]b[le]3 (4 solutions)
c=2, 5 cents remaining, so 0[le]b[le]1 (2 solutions)

Hence the total number of solutions is 1+1+9+7+5+3+1+6+4+2=50.

In general, how many ways can n cents be made up of 1 and 5 cent coins? [easy]

I've not been able to find the number of ways that n cents can be made from 1, 5, and 10 cent coins; that is, a single formula and not a sum. But it can be done for the three smallest British denominations of coins...

Find the number of ways of making up n pence from 1, 2, and 5 pence coins. [hard]

I wonder how far this can be generalised.

[e]Edited because I made an oversight in my generalisation, and the second extension question has been rephrased.[/e]

Title: Re: Change
Post by Barukh on Jan 3^rd, 2005, 6:44am

on 01/03/05 at 05:23:55, THUDandBLUNDER wrote:

I found it here (http://www.siam.org/journals/problems/downloadfiles/02-005.pdf).

Amazing! ;D