Associated Topics || Dr. Math Home || Search Dr. Math

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

- Doctor Greenie, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Basic Algebra
High School Linear Equations
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search