Solving equation with multiple variables

Hi,
My son is in third grade and came home with a math word problem the other day.
The basic problem said something like

"Ted has $6.00 to spend. How many combinations can he buy if  
Ice pops:  $.40
Candy: $.25
Toy: $.30

We answered it by trial and error, but I was thinking there must be a way to solve this to find all the possible result sets.
I know how to solve systems of equations but in this case it would only be one equation

40x + 25y + 30z = 600

Any ideas how to solve this for all possible (interger) result sets?  My algebra is rusty, it's been a while since I've been in grade school.

I'm working on it myself now in perl, but wanted to see what everyone else came up with.

Nacht
LVL 1
nachtmskAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

ozoCommented:
You say
40x + 25y + 30z = 600
but that sounds more like
"Ted has to spend $6.00"
than what you initially described as
"Ted has $6.00 to spend"
Can you clarify the actual requirements?

http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity
0
nachtmskAuthor Commented:
ozo,
 Yes it has to be $6.00 total, he can't have any change left over.  At least that's what the problem implies the way it's written. It's a third grade problem so It might be written a bit vague.
What I basically want to do is solve 40x + 25y + 30z = 600 for all possible positive integer values of  x y and z.
I can see doing it with some nested loops picking an arbitrary high value for x y and z (Say 50) and running the script. But I'm thinking there must be a more elegant way to do this.
Thanks
Nacht
0
byundtMechanical EngineerCommented:
By brute force, I get 21 combinations of purchases that total exactly $6.00. I made a table in Excel showing number of toys down column A and number of ice pops in row 2. I then used the following formula to determine the number of candy to make the total $6.00. Fractional and negative values were replaced with an empty string.
=IF(AND(6>=($A3*0.3+B$2*0.4),MOD((6-$A3*0.3-B$2*0.4)/0.25,1)=0),(6-$A3*0.3-B$2*0.4)/0.25,"")
NumberPurchaseCombinationsQ28227.xlsx
0
Introducing Cloud Class® training courses

Tech changes fast. You can learn faster. That’s why we’re bringing professional training courses to Experts Exchange. With a subscription, you can access all the Cloud Class® courses to expand your education, prep for certifications, and get top-notch instructions.

byundtMechanical EngineerCommented:
I forgot to allow for the possibility of 0 ice pops or toys. The number of combinations increases to 27. Of those, 18 include some of all three items.
NumberPurchaseCombinationsQ28227.xlsx
0
phoffricCommented:
Determine the least common multiple, LCM, of the four cases where you have more than one selection.
http://en.wikipedia.org/wiki/Least_common_multiple

Ice pops:  $.40
Candy: $.25
Toy: $.30

1) LCM(40, 25) = 200 goes into 600 3 times
2) LCM(40, 30) = 120 goes into 600 5 times
3) LCM(25, 30) = 150 goes into 600 4 times
4) LCM(25, 30, 40) = 600 goes into 600 1 time
==================================
Conclusions:
Easy 3 cases:  all Ice pops, or all Candy, or all Toys.

1) If buying just Ice pops and Candy, then you have to buy in chunks of $2.00. You could buy two chunks of Ice pops ($4.00) and one chunk of Candy ($2.00); or one chunk of Ice pops ($2.00) and two chunks of Candy ($4.00).
==> 2 combinations

2) If buying just Ice pops and Toys, then you have to buy in chunks of $1.20. You could buy 4 chunks of Ice pops ($4.80) and one chunk of Toys($1.20); etc.
==> 4 combinations
...
4) If you had to buy at least one of all three items, you need $18.00
==> 0 combinations
0
phoffricCommented:
It looks like my total combinations is less than that produced by the spreadsheet.. Possibly the spreadsheet is computing combinations that add up to less that 6.00 (i.e., some change after purchase).
0
phoffricCommented:
If you wrote exactly the way the problem was written, then I would assume that if he has $6.00 to spend, then some change would be allowed (otherwise, the question should have said something about spending exactly $6.00, or something about no change allowed). Nevertheless, when you clarified what you wanted (i.e., no change allowed), I went with the sum of the total purchases must be exactly $6.00.
0
byundtMechanical EngineerCommented:
phoffric,
Your remark about the number of combinations of only two out of three commodities uncovered a rounding issue that my formula was sensitive to. Excel only has 15 significant figures in its calculations. In some cases, my formula calculated 10^-15 more or less candies than a whole number. The formula then improperly rejected those possible combinations.

To avoid this issue, I realized that the smallest increment of money (one penny) represented 0.04 candies. I took advantage of this fact by adding an infinitesimal (0.001 in this case) before taking MOD(# candies, 1) to return the number of fractional candies. If the number of fractional candies were less than 0.02, then the combination was valid. The resulting formula is:
=IF(AND(6>=($A3*0.3+B$2*0.4),MOD((6-$A3*0.3-B$2*0.4)/0.25+0.001,1)<0.02),(6-$A3*0.3-B$2*0.4)/0.25,"")

Bottom line: there are 37 possible combinations of toys, ice pops and candy that will result in an exact expenditure of $6.00.

Brad
NumberPurchaseCombinationsQ28227.xlsx
0
phoffricCommented:
>> combinations of only two out of three commodities uncovered a rounding issue
Right.. I see that you now have improved in this specific area and as a result uncovered more cases where all three items are required.

Obviously, I need to correct my case 4 conclusion, and still be able to explain it to a 3rd grader....

Not sure how you can explain your formula to a 3rd grader. ;)
0
nachtmskAuthor Commented:
Wow. You guys/girls are great! Thanks. My kids are still awake, but once they go to bed I'm going to look over all this in more detail.
Nacht
0
ozoCommented:
Elegant can mean simple or it can mean efficient.
In this case, the most efficient program would not be the simplest.
The simplest program here would be a brute force search.
For numbers this small, brute force search is still very fast, and a simple approach, like
perl -le 'for($x=0;$x<=600;$x+=40){for($y=0;$y<=600;$y+=25){for($z=0;$z<=600;$z+=30){++$n if $x+$y+$z==600}}}END{print $n}'
would seems to be more efficient use of programmer time.

If you are interested, we could develop a more sophisticated perl program based on Bézout's identity, but this may be beyond the understanding of most  3rd graders.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
byundtMechanical EngineerCommented:
My explanation to the 3rd grader is simple:
1.  Make a table showing 0 to 20 toys in the first column and 0 to 15 ice pops in the first row.
2.  Calculate the number of candies you could buy for each combination of toys and ice pops.
3.  If the number of candies is a whole number, then it's a valid combination

Solving the problem involves a lot of practice with multiplication, addition, subtraction and division. That's why we have computers to solve problems like this when we get older.

Looking at the spreadsheet, it appears that every solution falls on a diagonal line, and involves two more toys and four less candies for each ice pop added to the previous solution. So to enumerate all the solutions as a 3rd grader, you need to find the starting points (either zero or one toys, or zero ice pops, with varying numbers of candies). Then step off all the related possibilities.
0
nachtmskAuthor Commented:
This is what I came up with in Perl.

I picked 50 as the loop counter figuring it would never be higher than that. Must be a way to figure out a more accurate number though before starting. Going to think about that.
I get 37 combos also.
Brute force does seem to be the most efficient method. This ran very fast
--------------------------------------
#40x + 25y + 30z= 600
## How many combos can you buy for  $6.00.
$c=0;



for ($x =0; $x <=50; $x++){
        for ($y =0; $y <=50; $y++){
                for ($z =0; $z <=50; $z++){

                        if( 40 * $x + 25 * $y + 30  * $z == 600)
                        {
                        $c++;
                        print "Ice Pops: $x  Candy: $y Toy: $z\n";
                        }
                } # end z loop

        }#end y loop

}#end x loop
print "Total Combos are: $c\n";
0
byundtMechanical EngineerCommented:
The maximum loop counters would be $6.00 worth of each commodity: 15 ice pops, 20 toys and 24 candies.
0
nachtmskAuthor Commented:
byundt -- your correct. That's exactly what the loop counter should be. Thanks!
N
0
ozoCommented:
Adding your print statements to http:#a39455556
perl -le 'for($x=0;$x<=600;$x+=40){for($y=0;$y<=600;$y+=25){for($z=0;$z<=600;$z+=30){$n+=print "Ice Pops: ",$x/40,"  Candy: ",$y/25," Toy: ",$z/30 if $x+$y+$z==600}}}print "Total Combos are: $n"'
We can also tighten the loop bounds to increase efficiency:
perl -le 'for($x=0;$x<=600;$x+=40){for($y=0;$x+$y<=600;$y+=25){for($z=int((600-$x-$y+29)/30)*30;$x+$y+$z<=600;$z+=30){$n+=print "Ice Pops: ",$x/40,"  Candy: ",$y/25," Toy: ",$z/30 if $x+$y+$z==600}}}print "Total Combos are: $n"'
An additional small increase in efficiency can be gained by moving the +=25 loop to the inside.
I was working on a way to directly compute the total from Bézout's identity in the general case for n different prices, but if we need to print all the individual solutions, then that would dominate the run time anyway.
0
BigRatCommented:
I'd be very surprised if this question is meant to be answered in full by a third grader. In fact it is a Diophantine equation in three variables requiring positive integer solutions. But I suppose by enumeration, or by using a computer, it is possible to work it out.

But to solve such problems as these - without a computer - is a bit more than third grade. Here is a good example of doing this, In fact the problem is very similar, athough the full solution is required rather than just an enumeration :-

http://mathforum.org/library/drmath/view/61325.html
0
BigRatCommented:
Also here is a rather nice presentation on the general problem of linear Diophantine equations :-

http://www.cs.cmu.edu/~adamchik/21-127/lectures/divisibility_5_print.pdf
0
TommySzalapskiCommented:
You can solve it without using fancy words like Diophantine though.

You have to buy an even number of candies since otherwise you'd have a .05 there.
So you can replace the candy item with pair_of_candies which would be .50

Multiply everything by 10 and you get

3t + 4i + 5c = 60

The most items you could ever have is 20 toys (which is a valid solution).
Now
4 toys is the same as 3 ice pops
5 toys is the same as 3 pairs of candy
3 toys is the same as 1 ice pop and 1 candy

That should be all the interesting possible matching sets.

So start with 20t as the base and swap out valid matches. Each one will be a solution.

If you put 20t as the root of a tree and draw three branches out for each of the three possible trades and keep doing that until you run out of toys, you will eventually have all the answers (note the tree will get rather large and there will be duplicates. If you hit a duplicate on a branch, you can stop that branch there).

This still seems a bit complicated for third grade, but perhaps more manageable.
0
TommySzalapskiCommented:
I get this
So the first solution is 20t,0i,0c
Next level is 17t,1i,1c  16t,3i,0c   15t,0i,3c
Next 14,2,2  13,4,1  12,1,4  12,6,0  11,3,3 10,0,6 (note that there were three duplicates)
Next 10,5,2 9,2,5 10,5,2 9,7,1 8,4,4 9,2,5 7,1,7 8,9,0 7,6,3 6,3,6 5,0,9 (lots of duplicates)
Next 6,8,2 5,5,5 4,2,8 5,10,1 4,7,4 3,4,7 2,1,10 4,12,0 3,9,3 2,6,6 1,3,9 0,0,12 (lots of duplicates)
Next 2,11,2 1,8,5 0,5,8 1,13,1 0,10,4 0,15,0 (lots of duplicates)

I think I got all the duplicates, so that's about 39. Also remember that you need to double the candy number for each one of mine to get individual candies instead of pairs. I just typed the above as I solved it so there may be errors, but I checked periodically to make sure they equated back to $6 so if it's not 100% right, it should be close.
Again, that's a bit much for third grade. Maybe they just wanted to see a few good solutions and not all of them?
0
nachtmskAuthor Commented:
Hi Tommy,
Thanks for the input.
I really appreciate all of the solutions and discussions on this problem.
It is indeed a bit much for third grade. I wrote to my son's teacher suggesting just that.
She wrote back almost immediately and apologized. Apparently in her haste, she had copied the wrong homework assignment for the class. She agreed that this one was much to hard for them "at this point in the year", and she was going to explain it to them this morning in class.
I'm thinking after the kids learn their multiplication tables this will be easier for them.
My son had a problem similar to this last week but the numbers were much smaller, he didn't have a problem with that one because you could just 'see' the answers. This was much harder.
I have to look over your solution, I don't see how you figured it out right off, but I only gave it a quick look. I wrote a small script that solved it by brute force, I think I got 37 results (scroll up to see).
I'm going to assign points to this soon, but it's going to be hard, everyone has been great. I'll be splitting points because everyone's input was valuable.
I am curious to know if any of the third graders were able to solve this on their own - maybe there exists a math prodigy in that class?!

Thanks again,
Nacht
0
TommySzalapskiCommented:
Yes. Looking again, I have 10,5,2 and 9,2,5 in there twice. So I also obtained 37 solutions. All that fancy talk about computers and diophaniwhatevers looked confusing me so I just approached the problem the way I would have when I was in third grade (or maybe fifth, that's still a bit much for third).

The idea is to find one valid solution and then see all the ways you can transform that solution into another valid one. The candy pair thing is a quick short cut that should be easy to understand and cuts the problem size down a lot.
The only real trick is knowing that those three transformations that I listed are all the valid ones.
Proving it would be fairly simple but would use modulo arithmetic. It's just a matter of what combinations of 4 and 5 can produce multiples of 3. Since 4 is one more than 3 and 5 is two more, 4t=3i, 3c, and 1i+1c are all you need (3 shares no factors with 4 or 5 so it should be fairly easy to prove this).
Every other transform is based on those.
0
awking00Commented:
Is the question really how many combinations can he buy or what is the maximum number of all three combinations can he buy?
0
nachtmskAuthor Commented:
The question is how many solutions sets are there for the equation, which means how many combinations can he buy without having change left over.
0
byundtMechanical EngineerCommented:
Were it my child with the assignment, I'd encourage him to make a presentation of how one might solve the problem. The pattern recognition suggested by TommySzalapski ought to be understandable to the class. So too would be a poster showing the actual solutions in a grid. And everybody would get a laugh out of Dad needing to write a computer program. With sufficient parental coaching and rehearsal, a ten minute presentation would establish his reputation at the beginning of a school year.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Perl

From novice to tech pro — start learning today.