All Possible Solutions: Diophantine Equations

Date: 12/06/2002 at 14:29:26
From: Chris
Subject: Algebra problem

I've tried everything that I can think of and I can't figure out how 
to do this. Could you please try it and let me know how to do it? I 
have the answer (16 Combos, 17 Hot dogs, 22 Hamburgers, 25 Sodas), 
but I do not know what method to use to solve it. Thanks!  

Lance and Mario were working in the snack bar at the Turbulent Tunas 
Concert. They sold hot dogs for $1.65, hamburgers for $2.35, sodas 
for $.85, and the combo plate with fries, salad, a hamburger; and 
soda for $3.89. They sold 80 items in an hour for $163.24. How many 
of each kind of food did they sell, and how much did they make on 
each kind of food?

Date: 12/09/2002 at 00:23:51
From: Doctor Greenie
Subject: Re: Algebra problem

Hello, Chris -

You apparently have one of many possible solutions to this problem.  
I have found several others and have not completed the task of finding 
all solutions. Following is a description of how you can go about 
finding all the solutions to this problem.

You are selling the following items:

  $1.65 -- hot dog
  $2.35 -- hamburger
  $0.85 -- soda
  $3.89 -- combo

80 items were sold for a total of $163.24.  Suppose we let

  D = # (hot) Dogs sold
  H = # Hamburgers sold
  S = # Sodas sold
  C = # Combos sold

Then we have two equations; one says the total number of items sold is 
80, and the other says the total cost of those items is $163.24. To 
avoid working with decimals, we write the second equation in terms of 
cents instead of dollars. The two equations are then

(1) D + H + S + C = 80
(2) 165D + 235H + 85S + 389D = 16324

To limit the types of combinations we need to search for, notice that 
the prices of a hot dog, a hamburger, and a soda are all multiples of 
5. That means the total cost of the hot dogs, hamburgers, and sodas is 
a multiple of 5, so that total cost of those items has final digit 0 
or 5. Since the total cost of all items sold is $163.24, that means 
that the total cost of the combos has final digit either 4 or 9. This 
in turn means that the number of combos sold must be a number with 
final digit either 1 or 6.

So we have the following possibilities at this point:

   # combos  cost of combos   # other items   cost of other items
  ----------------------------------------------------------------
        1        3.89                79             159.35
        6       23.34                74             139.90
       11       42.79                69             120.45
       16       62.24                64             101.00
       21       81.69                59              81.55
       26      101.14                54              62.10
       31      120.59                49              42.65
       36      140.04                44              23.20
       41      159.49                39               3.75

The largest number of combos that could have been sold is 41, because 
with the next possible number, 46, the cost of the combos is by itself 
more than the total amount of the sales.

Also, examination of the last two columns in the above table shows 
that there will be no solutions with either 36 or 41 combos, because 
the cheapest item is 85 cents, and you can't get the total in the 
last column by selling the number of items in the next-to-last column.  
And for the possible combination with 31 combos and 49 other items, 
the cost of 49 sodas is $41.65, so there won't be a solution with 31 
combos either.

However, it is possible and even likely that there are solution(s) for 
any of the other numbers of combos in the table.

Following is how to find all the solutions with 6 combos sold; you can 
try to use the same process to find the solutions with other numbers 
of combos.

We have 6 combos sold, for a total of $23.34; leaving 74 other items 
with a total cost of $139.90. So now, with C=6, we have the following 
equations:

  D+H+S = 74
  165D+235H+85S = 13990

We can solve this pair of equations by eliminating the "S" variable -
by factoring a constant of 5 out of the second equation and then 
multiplying the first equation by 17:

  33D+47H+17S = 2798
  17D+17H+17S = 1258
  ------------------
  16D+30H     = 1540

The approach at this point is to solve this equation for one of the 
variables in terms of the other and then to use the fact that the 
variables have integer values to determine the possible combinations 
of values for D and H.

  16D = 1540-30H

  16D = (1600-32H) + (2H-60)

  D = (100-2H) + (2H-60)/16

100 is an integer; and H is an integer, so 2H is an integer. For D 
to be an integer, then, (2H-60)/16 must be an integer, so (2H-60) 
must be a multiple of 16. We then get the following solutions with 
C=6:

    H     D=(100-2H)+(2H-60)/16   S = 80-(C+H+D)
  ------------------------------------------------
   30       (100-60)+0 = 40      80-(6+30+40) = 4
   38       (100-76)+1 = 25      80-(6+38+25) = 11
   46       (100-92)+2 = 10      80-(6+46+10) = 18

The values chosen for H are those which make (2H-60) a multiple of 16.  
The next larger value of H would give a negative value for D, so this 
table shows all the solutions with C=6.  We can check these three 
solutions to the problem:

  combos (C):      6 @ $3.89 = $23.34
  hamburgers (H): 30 @ $2.35 = $70.50
  hot dogs (D):   40 @ $1.65 = $66.00
  sodas (S):       4 @ $0.85 = $ 3.40
                              -------
                              $163.24

  combos (C):      6 @ $3.89 = $23.34
  hamburgers (H): 38 @ $2.35 = $89.30
  hot dogs (D):   25 @ $1.65 = $41.25
  sodas (S):      11 @ $0.85 = $ 9.35
                              -------
                              $163.24

  combos (C):      6 @ $3.89 = $23.34
  hamburgers (H): 46 @ $2.35 =$108.10
  hot dogs (D):   10 @ $1.65 = $16.50
  sodas (S):      18 @ $0.85 = $15.30
                              -------
                              $163.24

You can follow the same procedure to find the other solutions to the 
problem. I did some quick calculations to verify that there is at 
least one solution with 1 combo sold and at least one solution with 
26 combos sold; so I suspect there will also be at least one solution 
each with 11, 16, or 21 combos sold.

Equations like those in this problem - where the number of unknowns is 
more than the number of equations, and where the values of the 
unknowns are integers - are called Diophantine equations. If you 
would like a better understanding of problems like this, try searching 
the Dr. Math archives using the keyword "Diophantine" and take a look 
at some of the pages that the search provides to you.

I hope all this helps.  Please write back if you have any further 
questions about any of this.

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/