|
|
Solving Diophantine Equations By Organized ThinkingDate: 11/25/2003 at 09:19:44 From: Linda Subject: helping me and my girls to break down word problems Laura is in charge of lighting. Each light fixture supplies exactly 1,000 watts of power to light the bulbs in the fixture. Laura can use any combination of 150-watt, 100-watt, 75-watt, or 60-watt bulbs, but the total number of watts must be 1,000. How many different combinations of bulbs could Laura use in a light fixture? We started out by trying guess and check, but are wondering if there is a more albebraic solution method? The teacher says there are 30 possible answers. What's the best way to find them all?
Date: 11/25/2003 at 11:48:09
From: Doctor Ian
Subject: Re: helping me and my girls to break down word problems
Hi Linda,
Algebraically, we can let:
x be the number of 150-watt bulbs
y 100
z 75
w 60
The condition to be satisfied is then
1000 = 150x + 100y + 75z + 60w
However, we note that x, y, z, and w must all be integers. (You can't
use half a bulb!) This makes the equation an example of a Diophantine
equation'. For an example of a classic problem involving this type
of thing, see
Solving for Multiple Unknowns
http://mathforum.org/library/drmath/view/62585.html
What makes this difficult to deal with using algebra is that we have
more unknowns (4) than equations (1). This usually means that more
than one solution will be possible, which is certainly the case here.
In this kind of situation, the best you can do is try to proceed
systematically. One way to do that is to set up an intial state, e.g.,
150 100 75 60
--- --- --- ---
6 1 0 0
and then define a set of legal state transitions. Each transition
will basically say "I can trade ___ of one thing for ___ of another".
(Note that at this point, it's more like a computer programming
problem than a math problem.)
For example, you can trade one 150-watt bulb for two 75-watt bulbs.
Let's call that transition T1:
T1: 1*150 -> 2*75
Applying this transition leads to some new states:
150 100 75 60
--- --- --- ---
6 1 0 0 T1
5 1 2 0 T1
4 1 4 0 T1
3 1 6 0 T1
2 1 8 0 T1
1 1 10 0 T1
0 1 12 0 ~T1
The 'T1's to the side indicate that we've applied transition T1 to the
states. The '~T1' at the end indicates that it's not possible to
apply transition T1 to the state.
A second transition might be trading two 150-watt bulbs for three
100-watt bulbs:
T1: 1*150 -> 2*75
T2: 2*150 -> 3*100
As before, we want to apply this transition to each of our states, if
that's possible, and indicate that it's not possible when that's the
case.
150 100 75 60
--- --- --- ---
6 1 0 0 T1 T2
5 1 2 0 T1 T2
4 1 4 0 T1
3 1 6 0 T1
2 1 8 0 T1
1 1 10 0 T1
0 1 12 0 ~T1
4 4 0 0 T2
2 7 0 0 T2
0 10 0 0 T2
3 4 2 0 T2
1 7 2 0 ~T2
and so on. Now, sometimes you'll apply a transition, and you'll end
up with a state that already exists. In that case, you just note that
you've applied the transition to the state, without adding a new row
to the table.
Note that you'll also need to go back and apply old transitions to new
states. For example, we need to apply transition T1 to states like
(4,4,0,0).
When you've applied every possible transition to every state in your
table, you'll know that you've found every possible state.
When creating transitions, note that you don't want to have redundant
transitions. For example, you can exchange two 150-watt bulbs for
three 100-watt bulbs. You could also exchange four 150-watt bulbs for
six 100-watt bulbs; but you don't need to include that as a separate
transition, since applying the first one twice is the same as applying
the second one. Does that make sense?
Note that one nice thing about this method is that you never try
anything that doesn't work!
A second way to approach this is to decompose the problem into
sub-problems. For example, the question
How many ways can we use 150, 100, 75, and 60 watt bulbs
to get 1000 total watts?
can be reduced to the smaller problems
1) How many ways can we use 100, 75, and 60 watt bulbs
to get 1000 watts?
2) How many ways can we use 100, 75, and 60 watt bulbs
to get 850 total watts?
3) How many ways can we use 100, 75, and 60 watt bulbs
to get 700 total watts?
4) How many ways can we use 100, 75, and 60 watt bulbs
to get 550 total watts?
5) How many ways can we use 100, 75, and 60 watt bulbs
to get 400 total watts?
6) How many ways can we use 100, 75, and 60 watt bulbs
to get 250 total watts?
7) How many ways can we use 100, 75, and 60 watt bulbs
to get 100 total watts?
Each of these corresponds to having a particular number of 150 watt
bulbs. If we answer each of the smaller problems, we can just add the
answers to get the answer to the larger problem.
We can break each smaller problem into still smaller problems, each
corresponding to some number of 100 watt bulbs:
1) How many ways can we use 100, 75, and 60 watt bulbs
to get 1000 watts?
1a) How many ways can we use 75 and 60 watt bulbs
to get 1000 watts?
1b) How many ways can we use 75 and 60 watt bulbs
to get 900 watts?
1c) How many ways can we use 75 and 60 watt bulbs
to get 800 watts?
1d) How many ways can we use 75 and 60 watt bulbs
to get 700 watts?
1e) How many ways can we use 75 and 60 watt bulbs
to get 600 watts?
1f) How many ways can we use 75 and 60 watt bulbs
to get 500 watts?
1g) How many ways can we use 75 and 60 watt bulbs
to get 400 watts?
1h) How many ways can we use 75 and 60 watt bulbs
to get 300 watts?
1i) How many ways can we use 75 and 60 watt bulbs
to get 200 watts?
1j) How many ways can we use 75 and 60 watt bulbs
to get 100 watts?
1k) How many ways can we use 75 and 60 watt bulbs
to get 0 watts?
Adding the answers to (1a) through (1k) gives us the answer to (1).
(Note that some of these answers will be: 0. For example, there's no
way to combine 60 and 75 watts to get 100 watts!)
Adding the answers to (1) through (7) gives us the answer to the whole
question.
You could use a tree structure to keep things a little more compact.
In such a structure, you would start by selecting each possible number
of 150-watt bulbs:
No.
150W
bulbs
+-- 0 (1000)
|
+-- 1 (850)
|
+-- 2 (700)
|
+--+-- 3 (550)
|
+-- 4 (400)
|
+-- 5 (250)
|
+-- 6 (100)
At each node of the tree, we put the remaining watts to be accounted
for in parentheses. In the second level of the tree, we select, for
each node, the number of 100-watt bulbs that could be used:
No. No.
150W 100W
bulbs bulbs
+-- 0 (1000)
|
+-- 1 (900)
|
+-- 2 (800)
|
+-- 3 (700)
|
+-- 4 (600)
|
+-- 0 (1000) --+-- 5 (500)
| |
| +-- 6 (400)
| |
| +-- 7 (300)
| |
| +-- 8 (200)
| |
| +-- 9 (100)[x]
| |
| +-- 10 (0)[s]
|
|
|
+-- 1 (850)
|
+-- 2 (700)
|
+--+-- 3 (550)
|
+-- 4 (400)
|
+-- 5 (250)
|
+-- 6 (100)
I've used [s] to mark a node where there are no watts left to be
accounted for. This is a 'solution' node, and doesn't need to be
expanded any further.
I've used [x] to mark a node where there are no solutions to be found.
As we noted earlier, there are no ways to combine 75 and 60 watt
bulbs to get 100 watts.
You want to keep expanding the tree until every node (1) has other
nodes coming out of it, (2) is marked with [s], or (3) is marked with
[x]. At that point, you know that you've covered all the
possibilities, and you just have to count the [s] nodes.
In each of these methods, the key is to set up a system for generating
every possible solution, without generating any solution more than
once. This is somewhat tedious... but not nearly as tedious as going
in circles, wondering if there are solutions that you've missed!
I hope this helps. Write back if you'd like to talk more about this,
or anything else.
- Doctor Ian, The Math Forum
http://mathforum.org/dr.math/
|
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/
