Diophantine Equations, Apples, Bananas

Date: 06/08/97 at 06:28:53
From: Anna
Subject: Diophantine Equations

Mick has $5.63 worth of bananas and apples. Bananas are 13 cents each 
and apples are 7 cents each. How many different combinations of apples 
and bananas can he have and what are they?

Date: 07/13/97 at 14:44:43
From: Doctor Terrel
Subject: Re: Diophantine Equations

Dear Anna,

I see that you are interested in a famous math topic called Diophantine 
Equations.

First, we must remember that the solutions to your particular type of 
problem are always positive integers (i.e. the whole numbers). I mean, 
it would not do to try to count "negative" apples or bananas.  
Furthermore, we don't want to have parts of bananas and apples all 
over the place - you certainly can't do that in a store! This makes 
our job easier, as I'm sure you can see.

Next, we need to set up the equation for our problem. Let a equal the
number of apples and b equal the number of bananas we wish to buy.  
This gives us "7a" and "13b" as the number of cents we will spend for 
each type of fruit. Since the sum is given in dollars/cents ($5.63), 
I suggest we simplify matters a little by changing this to just cents,
i.e., 563 cents.  Now we can write an equation expressing the number 
of apples and bananas that Mick can buy for 563 cents:

7a + 13b = 563

This should look familiar if you've taken Algebra I in school; it's a 
linear equation, right?  Usually you work with things in x and y, like 
3x + 4y = 15. They make straight lines when you graph them; for that 
reason, they're called linear.

Usually you solve for the variable y, in terms of x, like this:

4y = 15 - 3x

      15 - 3x
 y = ----------
         4

Then you make a chart of values, called a T-chart in some books. You
choose various values for x, then compute what y will be.  It might 
look like this:

        x       |    y
       ---------|--------
         1      |    3
         2      |    2.25
         3      |    1.5
         4      |    0.75
         5      |    0

Of course, in this example the output values (y) do not have to be 
whole numbers. Decimals (or fractions) are okay; not so in our
apple/banana problem.  But that's my point - you simply must do the
same for 7a + 13b = 563; there are just different numbers in it.

But here are two final hints to make your Diophantine work even more
efficiently.

(1) Solve for the letter that has the smaller number with it, i.e. 
    "a". This means our equation will be:

          563 - 13b
     a = -----------
              7

If a whole number solution exists - and just because you have an
equation, there is no guarantee there is one - you will need to try 
no more than 7 guesses for "b".  This is based on the division fact 
that there are only six possible remainders (1 to 6) when you divide a 
whole number by 7. Here you should begin substituting  1, 2, 3, ... 
for "b". If after the 6 you still don't achieve a whole number value 
for "a", then 7 will do the job!

(2) Our T-chart for this problem begins like this:

        b    |     a
       ------|--------
        4    |    73
             |

Now here comes a beautiful feature that you can discover after trying
many more values, in order, for "b".  If you increase "b" by 7 (the 
"a" number in the equation), you get 11, which gives you another whole
number output for the "a".  This is: a = 60, and we have another
solution!  Just continue in this manner and you'll find all the 
positive integer solutions for buying apples and bananas.

I hope you can use a calculator to do some of those computations.  
This sort of problem can be tiring with paper and pencil, but it's 
fun with a calculator.

If you need more help, just let me know.

-Doctor Terrel,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/