Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/