Solving Diophantine Equations By Organized Thinking
Date: 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:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.