Buying Cows, Pigs, and Chickens

Date: 07/09/97 at 17:34:56
From: Velda Thomas
Subject: Math question

Greetings!

I recently came across one of the most challenging math problems I've 
ever seen. I know that it is a Diophantine problem, and I know the 
answer, but I just cannot seem to figure out how to get it. Can you 
help?

Here it is:

A farmer buys 100 animals for $100.00. The animals include at least 
one cow, one pig, and one chicken, but no other kind. If a cow costs 
$10.00, a pig costs $3.00, and a chicken costs $0.50, how many of each 
did he buy?

Answer: 5 cows; 1 pig; and 94 chickens.

Thanks,
Velda L. Thomas

Date: 07/15/97 at 20:24:07
From: Doctor Sydney
Subject: Re: Math question

Velda,

It is always a good idea to first label your objects. So, let's make 
the following definitions:

    A = the number of cows
    P = the number of pigs
    C = the number of chickens

Now we can translate our information into equations.

First, we know that the total number of animals is 100:

    A + P + C = 100          (1)

And the total cost is $100:

   10A + 3P + 0.5C = 100     (2)

Now we have 2 equations and 3 unknowns. Usually a system of equations 
like this would have many different solutions if A, P, and C were 
allowed to be any number. However, because we know that A, P, and 
C must be positive integers (we can't have parts of animals and we 
can't have negative animals), the number of possible solutions is 
significantly reduced. The fact that A, P, and C are positive integers 
will be very important for finding the solution to this problem.

Whenever you have a system of equations that gives relationships 
between lots of variables, you want to simplify it so that you can 
find out what the individual variables are. One way to do this is to 
get rid of as many variables as you can. Using substitution we can 
simplify the above two equations into one equation that gives the 
relation between just two of the variables. This new equation will be 
much easier to work with.

So, first we need to rearrange equation (1) so that it shows what one 
of the variables is equal to; we shall solve for C (but you could 
solve for P or A, too, if you wanted):

    C = 100 - P - A          (3)

Substituting equation (3) into equation (2):

    10A + 3P + 0.5 (100 - P - A) = 100

Doing some rearranging:

    10A + 3P + 50 - 0.5P - 0.5A = 100
                    9.5A + 2.5P = 50
                       19A + 5P = 100

Now we have an equation that relates just two of our variables. What 
do we do with it? Well, we know that both A and P are positive 
integers, right? That is the only piece of information we have left 
that can help us solve the problem. Often at this stage, people write 
the above equation in a form such that it has "solved for" one of the 
variables. For instance, we could solve for P and rewrite the above 
equation as:

    P = 20 - 19A
             ---
              5

This is helpful because when it is in this form, it is easy to plug in 
whole number values for A and see immediately whether or not P will 
also be a whole number. For instance, we can see right off the bat 
that if A = 1, P will not be a whole number; therefore A cannot be 1.

Now look carefully at the equation above. For what values of A will P 
be a whole number?  

The only values of A which make P a whole number are those such that 
when divided by 5 yield a whole number, right? In other words, 5 must 
divide evenly into A. Thus, the only possible values for A that make P 
a whole number are 5, 10, 15, and so on. 0 is not a possibility 
because we are told that A > 0.  

We are making progress! Let's see what happens when A = 5. Plugging 
into the equation above, we see that:

    P = 20 - 19*5  = 1
             ----
               5

So far, so good. Now, let's check to make sure when A is 5 and P is 1 
that we have that C is a positive integer. You can do this on your 
own; you'll find that C must be 94 when A is 5 and P is 1.  

So, we are done, right? Not so fast! We have shown that A = 5, P = 1, 
C = 94 is one solution, but these problems often have multiple 
solutions. We must check to see if there are other solutions.  

Let's go back to where we left A and P. We had tried A = 5, right?  
Next we need to try A = 10. What value does P take on when A = 10?  
Plug into the equation to get that:

    P = 20 - 38 = -18  

Oh dear!  This won't work, since P > 0, right? What about if we try to 
plug in bigger and bigger values for A?  Well, if you look at the 
equation relating P and A, you'll see that P will get more and more 
negative. Hence, for all A > 5 such that A is divisible by 5, we have 
that P < 0. Thus, the only value that A can be is 5. 

Now that we have found a solution that works and we've shown that it 
is the only solution, we have finished.  

I hope this has helped you to understand how to solve Diophantine 
Equations better. Please do write back if you have any more questions.  
Good luck! 

-Doctors Susan and Sydney,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/