This is a problem you're surely supposed to just figure out in your head, it's almost embarrassing some of the things you guys(not everyone, I hasten to add) have come up with. Your application of some methods is sound, but totally out of place, especially as if you do want a rigorous solution to a generalised version of this, it's the sort of maths any computer student should know, although I'm not saying they should be able to solve it. Personally I skipped all of the optimisation lectures last year, because I found them intensely boring, I actually better start learning it from the notes soon, before term starts.

As for the phds and the test, I'd imagine it was the test that was at fault, or the premise of the test. The phd students will probably have backed up their arguments with solid reasoning. Anyway phd students don't exist to do trivial put it in the formula questions that high school students are capable of. Having said that, they just could have just been applied 'mathematicians'.

[edit] On second reading my post seems a little grouchy, if not hostile. Apologies, I've just been woken up by the cleaners, who I'm now trying to be polite to! [/edit]

of course 25=10+10+5 it's damn simple and should not take more than fraction of second to solve.No matter if you're PHD or not[grin]. But it's anyway funny to generally solve simple problems that turns to be not that simple when are generalized... at least it IMHO is more funny than for 100th time explain concepts of inverse matrix, or for 1000th time explainin column vectors versus row vectors.

IIRC there was a more nicer versions.
Something like
John had N coins of same type, M coins of other type, and some other coins,
he paid exact summ for ticket that costs O cents
and then he had P cents left.
What coins he have.(or what coins he had)
And also you have to prove that solution is unique(and it's big enough so bruteforce will take too long).

Quote:Original post by higherspeed
As for the phds and the test, I'd imagine it was the test that was at fault, or the premise of the test. The phd students will probably have backed up their arguments with solid reasoning.

Either test was bad or students was bad or both. In all cases, it's fault of education system.

If it was odd geometry problems, and PHDs had to derive most of geometry from axioms, while freshmen know only what's needed to pass the test using "pure knowledge" and no thinking, in that case it's fault of test.

Quote:
Anyway phd students don't exist to do trivial put it in the formula questions that high school students are capable of. Having said that, they just could have just been applied 'mathematicians'.

It's not like moving to C++ from assembler and forgetting assembler. It's mathematics. Even simplest things in math is used till the top.

Forgive the variable naming, never been good with that. And it probably could be cleaned up a lot, but it's early and I'm feeling lazy (that combination could lead to problems I haven't spotted, too).

Also note that it fails under certain conditions, as the last two point out, namely if the solution requires a number of small coins equal to the value of a larger coin (and at least one of said larger coin).

#include
#define COIN_PENNY 0
#define COIN_NICKEL 1
#define COIN_DIME 2
#define COIN_QUARTER 3
#define COIN_MAX 4

void solution( int money, int numCoins )
{
int valueCoins[COIN_MAX] = { 1, 5, 10, 25 };
int tCoins[COIN_MAX];
int a=numCoins+1,b,c=COIN_MAX,d,e=0;

while( c >= COIN_PENNY )
{
a = 0;
b = money;
c--;
for( d=0; d=COIN_PENNY; d-- )
{
if( b>=valueCoins[d] )
{
tCoins[d] = b / valueCoins[d];
b %= valueCoins[d];
a += tCoins[d];
}
}
if( a == numCoins )
{
for( c=COIN_QUARTER; c>=COIN_PENNY; c-- )
{
if( tCoins[c] != 0 )
printf( "%d*%d + ", tCoins[c], valueCoins[c] );
}
printf( "\b\b= %d\n", money );
e++;
}
}

if( e == 0 )
printf( "Couldn't find an answer." );
return;
}

void main( )
{
solution( 25, 3 );
printf( " (25,3)\n\n" );
solution( 30, 3 );
printf( " (30,3)\n\n" );
solution( 12, 3 );
printf( " (12,3)\n\n" );
solution( 25, 5 );
printf( " (25,5)\n\n" );
solution( 110, 12 );
printf( " (110,12)\n\n" );
solution( 5, 5 );
printf( " (10,2 )\n\n" );
return;
}

Simple if not optimal solution in Haskell. Gives all combinations.

Test runs:

> coins 40 4
[[5,5,5,25],[10,10,10,10]]

> coins 60 8
[[1,1,1,1,1,5,25,25],[5,5,5,5,5,5,5,25],[5,5,5,5,10,10,10,10]]

Quote:Original post by teamonkey

Quote:Original post by Dmytry
what if it's 31 and you need to do that in 7 steps, and there's 25c,5c,and 1c?,

(solution is not unique,25+6*1 or 5*6+1)

Well in that case the question wouldn't specify that there was only one solution, would it? ;)

You're right though. However, this is *elementary* grade maths.

But is there a way to do this without using discrete mathematics/numerical methods/programming? Thats whats bothering me. I don't think there is since the coins by nature are discrete.

The procedure given below will be better than a brute force approach for solving problems similar to that of the original poster's. Please bear with it. It is hard to describe in notation using plain text and ASCII.


Suppose S is a proper subset of the natural numbers, and that S = {c1, c0, c1, ..., cn}. The members represent the coin type values.

Without imposing any conditions, there will be
|S|! possible arrangments of n coins.

Each successive requirement/condition decreases the number of possibilities.

If the requirement changes to be that n coin types must be used, and not coins, then there will be |S|!(|S|-n)! arrangements, which we will NOT assume is the case.

Each of those arrangments would need to be summed and then checked against our given value, G. That is, let G denote the value which we wish to find an arrangement that will sum to. In the original post, the value was 25.

We will initially form n identical sets equal to S, denoted S1, S2, ..., Sn. The sets will have a definite order, that being S1 > S2 > ... > Sn.

What we are going to do is apply logic in order to eliminate members from the sets Sn. By doing so we will be decreasing the total number of arrangments that need to be checked, so the possibilities will be |S1|*|S2|*...*|Sn|. We seek a minimum.

Since there are n coins to be used, if G > n*cn, then all members c1, ... , cn can not be the greatest coin value used and so can be eliminated from S1.

[If G = 25, then 3 pennies will not sum to 25 and so a penny will not the greatest coin, thus we eliminate it from our "greatest coin set", which is S1, but the other sets!]

We can further reduce members from S1. If G 3*5 and so S1 can be reduced to {10, 25}. We have thus reduced the possible arrangments by a factor of 2.

S1 = {10, 25}. We select 10. G1 = 25 - 10 = 15. 15 > 2*5 = 10, so S2 = {10, 25}. 10 is not greater than 2*10=20, so we stop there. Now we see that 15 1 so S3 = {5, 10, 25}. 5 is not greater than 5, so it stays. 5 < 10 so S3 = {5}.

Since n = 3, we can no more columns to switch to. HOWEVER, we need to repeat the same procedure for the remaining values of S1. S1 = {10, 25}. Since we checked 10, we now check for 25.

The new G = 25 - 25 = 0. Since 0 is not greater or equal to 1, it is less than 1 and so all values greater than 1 will be removed from the set S2 for coin 25. Since this set is empty, we do not continue to S3, but rather remove 25 from S1.

We are thus left with the sets S1={10}, S2={10} and S3={5}. We sum all arrangments of these, there is only one, and we get G, which is 25. Thus 2 dimes and a nickle is the only solution. ]

PLEASE NOTE MY POST ABOVE WAS ALTERED BY THE FORUM SYSTEM FOR SOME UNKNOWN REASON AND SO MATERIAL WAS LEFT OUT AND ALTERED. THIS IS NOT A REPEAT.

The procedure given below will be better than a brute force approach for solving problems similar to that of the original poster's. Please bear with it. It is hard to describe in notation using plain text and ASCII.


Suppose S is a proper subset of the natural numbers, and that S = {c1, c0, c1, ..., cn}. The members represent the coin type values.

Without imposing any conditions, there will be
|S|! possible arrangments of n coins.

Each successive requirement/condition decreases the number of possibilities.

If the requirement changes to be that n coin types must be used, and not coins, then there will be |S|!(|S|-n)! arrangements, which we will NOT assume is the case.

Each of those arrangments would need to be summed and then checked against our given value, G. That is, let G denote the value which we wish to find an arrangement that will sum to. In the original post, the value was 25.

We will initially form n identical sets equal to S, denoted S1, S2, ..., Sn. The sets will have a definite order, that being S1 > S2 > ... > Sn.

What we are going to do is apply logic in order to eliminate members from the sets Sn. By doing so we will be decreasing the total number of arrangments that need to be checked, so the possibilities will be |S1|*|S2|*...*|Sn|. We seek a minimum.

Since there are n coins to be used, if G > n*cn, then all members c1, ... , cn can not be the greatest coin value used and so can be eliminated from S1.

(If G = 25, then 3 pennies will not sum to 25 and so a penny will not the greatest coin, thus we eliminate it from our "greatest coin set", which is S1, but the other sets!)

We can further reduce members from S1. If G 3*5 and so S1 can be reduced to {10, 25}. We have thus reduced the possible arrangments by a factor of 2.

S1 = {10, 25}. We select 10. G1 = 25 - 10 = 15. 15 > 2*5 = 10, so S2 = {10, 25}. 10 is not greater than 2*10=20, so we stop there. Now we see that 15 1 so S3 = {5, 10, 25}. 5 is not greater than 5, so it stays. 5 < 10 so S3 = {5}.

Since n = 3, we can no more columns to switch to. HOWEVER, we need to repeat the same procedure for the remaining values of S1. S1 = {10, 25}. Since we checked 10, we now check for 25.

The new G = 25 - 25 = 0. Since 0 is not greater or equal to 1, it is less than 1 and so all values greater than 1 will be removed from the set S2 for coin 25. Since this set is empty, we do not continue to S3, but rather remove 25 from S1.

We are thus left with the sets S1={10}, S2={10} and S3={5}. We sum all arrangments of these, there is only one, and we get G, which is 25. Thus 2 dimes and a nickle is the only solution.)