Sign in to follow this  

Simple Elementry school problem made difficult.

This topic is 4828 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

My girlfriend is getting her degree in education, and has to take elementry math so she can be able to teach it. When I heard she had to take elementry math and she complained to me the problems were hard I made fun of her. Though, the jokes on me because I can't figure it out either. The series of problems generalized is you have n amount of coins and M amount of money. How many nickels, dimes, quaters, and pennies do you need to get M. So an example of a question was if you had 25c and 3 coins how many n,d,q, and p's would you have? I tried solving a general form of an equation but my system of equations are always under-determined. That is.
25x + 10y + 5z + 1w = 25
x + y + z + w = 3
or
[25 10 5  1 ]  [x] [25]
[1  1  1  1 ]  [y] [3]
[a1 a2 a3 a4]* [z]=[u1]
[b1 b2 b3 b4]  [w] [u2]

There are 2 equations and four unkowns so the system is underdetermined. The constraint that you have so many coins to add up to so much money leads me to believe there is only one answer and since there is only one answer to the problem there must be a way to solve the problem mathematically not algorithmically. And it bothers me very much that I can't figure it out. -Dave

Share this post


Link to post
Share on other sites
[EDIT: just realized i missed the constraint of 3 coins... oops :)]

you don't solve this with a system of equations, that's why it's "elementary math". there are many possible answers. you can have all pennies, or just pennies and nickles, etc. you solve it by iterative modulus operations. maybe someone can come up with some equations to solve, but this is the easy way (and how you'd teach 6yr olds to do it, albeit not in code :))


//amount passed as amount of cents
void howMany( int amount )
{
int numQuarters = 0, numDimes = 0;
int numNickles = 0, numPennies = 0;

numQuarters = amount % 25;
amount -= numQuarters * 25;

if ( amount > 0 )
{
numDimes = amount % 10;
amount -= numDimes * 10;

if ( amount > 0 )
{
numNickles = amount % 5;
amount -= numNickles * 5;

if ( amount > 0 )
numPennies = amount;
}
}
}





Share this post


Link to post
Share on other sites
This reminds me of that study where phd students from an ivy league school scored worse than highschool feshman on the same test.

the moral was that the phd guys tried answering the questions using calculus, and the freshmen jsut used formulas they learned in geometery. the phd students made more mistakes.

the constraints you're forgetting are that x,y,z,w are all integers and always positive or zero.

this is implicit in the question. the elementary students pick up on it right away. you tried to apply linear algebra to the problem without first checking to see if linear algebra will work in this case.

Share this post


Link to post
Share on other sites
Quote:
Original post by Palidine
you don't solve this with a system of equations, that's why it's "elementary math". there are many possible answers. you can have all pennies, or just pennies and nickles, etc. you solve it by iterative modulus operations. maybe someone can come up with some equations to solve, but this is the easy way.

*** Source Snippet Removed ***


No, there is only one answer because their is a restraint on the problem. The restraint is you have so many coins that add up to a certain amount of money.

Example: You have 3 coins and 25 cents, how many nickels, dimes, pennies, and quaters do you have. Only one possible solution to the problem..

-Dave

Share this post


Link to post
Share on other sites
The problem doesn't even have to have a solution which is a problem =p

ie 27 cents with 4 coins

The solution is unique if there is one though.

Basically you take the set A = {x,y,z,w in N such that 25x + 10y + 5z + 1w = 25}

Then you take the set B = {x,y,z,w in N such that x + y + z + w = 3}

Then your result is A intersection B.

It would be simple to write an algorithm to do exactly that but you could make optimizations to make it run faster.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by ph33r
No, there is only one answer because their is a restraint on the problem. The restraint is you have so many coins that add up to a certain amount of money.

Quote:
Original post by O_o
The solution is unique if there is one though.

No, there can be more than one answer as well as there can be less. For instance, you can get 30c with 6 coins in two ways (25+1+1+1+1+1 or 5+5+5+5+5+5).

Share this post


Link to post
Share on other sites
I'd be able to tell you if it were in pounds, shillings and old pence ;)

Er, a dime's 5c isn't it and I'd guess a quarter's 25c.

Anyway, the solution's a simple box fitting solution in three steps (because you've got three coins).

1) find the largest coin that is less than 25c
2) find the largest coin that is less than the remainder
3) the remainder of that is the value of the last coin

The "less than" contraints aren't "less than or equal" because you know there's three coins.

Share this post


Link to post
Share on other sites
It's so because many "positive integer" problems are not very generalizable, and in many cases can not be solved without doing some iterations. Even simple ones. Intersection of several sets it's general solution to all problems.

With that problem, you can just calculate it as minimal amount of coins, and then do several replacement,like, 10=2*5 or 20=2*10
(for some really weird money systems(something like.... 1,2,3,4,5,6,7,8,9,10,20,25,30,50,100) that might not work in some cases. I don't know your system exactly, probably it's provable that any such problem can be solved by that method).

as about story about PHD students, i'd say, it must mean something is very wrong with education system.

p.s.
Good example of integer problem:
xn+yn=zn
n is integer
n>2
prove that there's no that integers x,y,z so equality is true.
[grin]

Share this post


Link to post
Share on other sites
Quote:
Original post by teamonkey
I'd be able to tell you if it were in pounds, shillings and old pence ;)

Er, a dime's 5c isn't it and I'd guess a quarter's 25c.

Anyway, the solution's a simple box fitting solution in three steps (because you've got three coins).

1) find the largest coin that is less than 25c
2) find the largest coin that is less than the remainder
3) the remainder of that is the value of the last coin

The "less than" contraints aren't "less than or equal" because you know there's three coins.

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

largest less than 31: 25
largest less than 6: 5
largest less than 1: none.

So you'll need to traverse a tree.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
As I can't find my password at the moment, and my email's broken, I post this as an AP.

If you're looking for a simple equation to solve it, you won't find one. As you said, there's too many unknowns to solve for. It's a multi-step question.

If anyone's still looking/wanting an answer for this, it's 2 dimes and a nickel.

-overflowed

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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).

[CODE]#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;
}[/CODE]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Simple if not optimal solution in Haskell. Gives all combinations.

coinr _ 0 0 l = [l]
coinr [] _ _ _ = []
coinr _ _ 0 _ = []
coinr (x:xs) sum n l = coinr (x:xs) (sum-x) (n-1) (x:l) ++ coinr xs sum n l

coins sum n = coinr [25,10,5,1] sum n []


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]]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
OK. This thread is basically OFF-TOPIC, seeing as how it is related to a specific math problem from elementary school education and not game development specifically. The Forum FAQ summarizes the forum policy on homework/schoolwork/related things.

That said, I'm allowing the thread to remain open since, to me, it feels like a legitimately stated request. At least it has invoked an interesting team problem-solving exercise and that alone makes the discussion relevant to game development.

But, be warned. Topics that don't follow the forum policy (see Forum FAQ) are always open for immediate closure.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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. ]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
For some unknown reason the forum software is not displaying the text correctly and so the material will not make any sense. A large portion of my text has been removed. It's a shame since it was a solution to the general problem.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
For some unknown reason the forum software is not displaying the text correctly and so the material will not make any sense. A large portion of my text has been removed. It's a shame since it was a solution to the general problem.


Please post a bug report to the sticky thread, if you did not already.

Share this post


Link to post
Share on other sites
Proceeding as you started you end up with a general solution of (-1/3,10/3,0,0)+(1/3,-4/3,1,0)s+(3/5,-8/5,0,1)t. Now you have the constraint that the solution has to be integers, so how do you work that in? Well, you have q=-1/3+1/3s+3/5t and d=10/3-4/3s-8/5t, but you can put those over a common denominator to rewrite them at 1/15(-5+5s+5t) and 1/15(50-20s-24t). Since they are integers (-5+5s+5t) mod 15=0 and (50-20s-24t) mod 15=0. So ((5s+5t) mod 15)=(5 mod 15) and ((5s+9t) mod 15)=(5 mod 15). Solving those you get s={1,4,7,10,13}+15m, t=0+15n. Well, m and n have to be zero because otherwise you get a negative number of coins or more than three. Additionally s has to be one because otherwise you have more than three coins. So s=1 and t=0 is the only solution. Pluging those into the general solution you find [0,2,1,0] is the solution and it is the only one.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
compute 1/((1-x*y)*(1-x^5*y)*(1-x^10*y)*(1-x^25*y)) as a power series. The coefficient of x^n*y^m is the number of ways you can make n cents with exactly m coins of 1, 5, 10 or 25 cents.


That solution is flawed
------------------------

Here is a solution:

Expand the quantity

1/((1-x)*(1-x^5)*(1-x^10)*(1-x^25)) {There are no y's in this formula}

in x about the point x=0. The resulting series solution is comprised
by terms A_i*x^i. Then the coefficient A_i is the number of
combinations
of pennies, nickels, dimes, and quarters can be arranged to give i
cents.

The solution you gave appears to be flawed. Try a simple example such
as

1/((1-x*y)*(1-x^5*y))

and we want to make 10 cents. You gave the coefficient y for each
factor
of x^n in the denominator which I think is wrong. You should write y_p
or
y_p for the number of pennies or nickels but I'll show both examples
and
neither one gives the correct answer. Let's consider the case where
y_p=y_n=2 which gives

1/((1-2*x)*(1-2*x^5)).

The coefficient of x^10 is 1092. Clearly that is wrong. Let's try some
other examples. When y_p=1 and y_n = 2, we get

1/((1-x)*(1-2*x^5)).

In this case the coefficient of x^10 is 7. That is still too big unless
we
allow multiple counting but that makes no sense. Finally, lets try
y_p=10
and y_n=2. This is the maximum number of pennies and the maximum number
of
nickels required to come out to 10 cents. We have

1/((1-10*x)*(1-2*x^5)).

The coefficient of x^10 here is 10000200004 which is utter nonsense.

The only correct answer is when y_p=y_n=1 which gives the answer I gave
above,

1/((1-x)*(1-x^5)).

For this case and only this case, the coefficient of x^10 is 3. We can
see
that is correct because we could have

10 pennies
5 pennies & 1 nickel (or 1 nickel & 5 pennies but we don't double
count)
or
2 nickels.

Perhaps I misunderstood what you were doing with your y's but
you didn't explain what they were doing there in the first place. In
summary, set all y's equal to 1 and your formula is correct.

Share this post


Link to post
Share on other sites

This topic is 4828 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this