Maths question help - permutations?

[RyanJ]

Hi there!

 

I have this question and despite my best efforts I have failed to answer it.

 

Given an unlimited supply of 50p, £1 and £2 coins, in how many different ways is it possible to make a sum of £100.

a) 1,326

b) 2,500

c) 5,050

d) 10,000

 

I've guessed that is it 5,050 I have no idea how to solve this - any help appreciated!

 

Cheers,

 

Ryan Jones

[BobbyJoeCool]

I'd guess A)

 

you can do it with all .50, all 1, or all 2... and then any combination of those... so you're probably not going to end up with a number that ends in 0...

[BigMoosie]

I get an answer of 2601 using this algorithm, is there something wrong with my logic?

 

var a, b, c, total=0;
for (a=0; a<=200; a++)
for (b=0; b<=100; b++)
	for (c=0; c<=50; c++)
		if (a/2 + b + 2*c == 100) total++;
alert(total);

[builgate]

Let $2 and $1 be the determining factor and let $0.50 to mark up the sum to $100.

 

When $2 x 50, $1 x 0 and $ 0.50 x 0~~~~~this is one way

 

When $2 x 49, $1 can be x1 or x2 or x0 and let $0.50 to mark up to the sum

Then this will be 3 way. $ 1 x0 would mean than no one dollar is used, only two dollar and 50p will be used.

 

When $2 x 48, $1 can be x1 or x2 or x3 or x4 or x0. Therefore, there are 5 ways

..............................

..............................

when $2 x 1, $1 can be x0 or x1 or .... or x 98, a total of 99 ways

when $2 x 0, $1 can be x0 or x1 or .... or x 98 or x 99 or x 100, a total of 101 ways

 

As you can see , this is an arithmatic progression. To find possible way to make a sum of $ 100, apply arithmatic summation.

 

It will be 1+3+5+...+101=2601

 

I don't get answer from the option. Maybe there is some mistake in my calculation? Please kindly point out.

[BigMoosie]

I think 2601 is actually the correct answer:

 

There will be 51 possible values of £2, each time leaving a left over of 0,2,4,6...98,100.

 

Each of these values will be made up of a some £1 and an even number of 50p coins. For each value there is value+1 ways of making it up. So we have to solve:

 

1 + 3 + 5 + .... + 99 + 101

 

The arithmetic series can be totalled with this formula:

 

[math]S_n = \tfrac{n}{2}(a + l)[/math]

 

Where n is the number of values, a is the first value and l is the last. So:

 

[math]S_n = \frac{51 * (1+101)}{2}[/math]

 

Which equals 2601.

[BigMoosie]

Builgate, didn't see your post until now.

[Dave]

I've got a possible answer to why the question may be wrong. If you use the summation technique posted by builgate you must have the answer to be:

 

[math]\sum_{n=0}^{50} (2n+1) = 51^2 = 2601[/math].

 

It's quite probable that someone made a numerical mistake, perhaps summing (2n-1) to give an answer of 50² = 2500 by mistake. I've looked at both the methods and can't see a problem, so... I don't know

[RyanJ]

Thanks for the help guys!

 

This was from a senior maths callange - how are you suposed to work this out in your hear in 20 seconds is what I'd like to know!

 

Oh and sorry 2,500 was supposed to be 2,601

 

Cheers,

 

Ryan Jones