Ask Marilyn ® by Marilyn vos Savant is a column in Parade Magazine, published by PARADE, 711 Third Avenue, New York, NY 10017, USA. According to Parade, Marilyn vos Savant is listed in the "Guinness Book of World Records Hall of Fame" for "Highest IQ."
In Marilyn's Parade Magazine column of July 6, 1997, she explains that Diophantine equations are popular for puzzles because there is no simple technique for solving them. There may be anywhere from zero to an infinite number of solutions, some of which may need to be ruled out because the problem requires positive integral solutions. She doesn't include step by step solutions because they're too mathematical.
10 c + 3 p + h/2 = 100
c + p + h = 100
where c, p and h are positive integers representing the number of cows, pigs, and
chickens, respectively. The first equation specifies the total price paid for the
animals, and the second equation specifies the total number of animals.
We have two equations with three unknowns. First, eliminate one of the unknowns (it doesn't really matter which one). Let's eliminate h (we'll get back to it later to make sure that our solution(s) for c and p allow for a positive integral h). Twice the top equation minus the bottom gives us:
19 c + 5 p = 100
This equation has an infinite number of solutions. In order to solve the problem, we need to find those solutions which result in positive integral values for both c and p.
Treat f(c,p) = 19 c + 5 p as a function, which we hope will eventually evaluate to 100. We first note that if c = 5 and p = -19, the function would evaluate to zero, so any solution can be incremented by adding 5 to c while subtracting 19 from p or subtracting 5 from c while adding 19 to p, and the new values will also be a solution.
Therefore, if we can find integral values for c and p that when substituted in the function would produce 100, even if one of the numbers was negative, we could add or subract 5 and -19 to c and p respectively as many times as needed to make the negative one positive.
To find values for c and p that produce 100, we'll start with the simpler concept of finding values that make 1. First of all, that is possible because the greatest common factor of 19 and 5 is 1. (If the greatest common factor is not also a factor of the value of the function, in this case 100, we would not necessarily be able to find integral solutions for the function f(c,p) = 100.)
There is an algorithm for finding this that also leads to a way of expressing that greatest common factor as a combination of the original numbers. What we do is to divide one number into the other, finding a remainder. The remainder is then divided into the previous divisor, and the process repeated until nothing remains. In the column on the left below, beginning with the third line down, each number is the remainder of the number directly above it divided into the number above that:
f(c,p) c p 19 1 0 5 0 1 4 1 -3 1 -1 4 0 5 -19The columns labeled c and p merely keep track of the values for c and p that would cause 19 c + 5 p to have the value for f(c,p) on that line. Clearly if c were 1 and p were 0, 19 would be produced, and likewise if c were 0 and p were 1, 5 would be produced. Then, to obtain the next line, we must realize that division of 5 into 19 giving a quotient of 3 and remainder of 4 is also expressed in 4 = 19 - 5 (3). In general terms r = n1 - n2(q). But we express the 19 and the 5 (the n1 and n2) as their equivalents in c and p, so we get new values of c and p. As a result, the algorithm calls for finding the new c or p value by subtracting the quotient of the division multiplied by the previous number in the column from the value above that. Thus 1 - 3(0) = 1, and 0 - 3(1) = -3. Likewise, as the next quotient is that of 5/4, or 1, the new c is 0 - 1(1) = -1 and the new p is 1 - 1(-3) = 4. And in the final step the quotient is 4/1, or 4, so the new c is 1 - 4(-1) = 5 and the new p is -3 - 4(4) = -19.
The last line tells us what we already know: c = 5 and p = -19 results in 19c+5p = 0. The previous line gives us something we didn't know before: c = -1 and p = 4 results in 19c+5p=1. We just need to multiply this by 100 to get 19c+5p=100. Thus c=-100 and p=400 is a solution, but c is negative. We can make c positive by adding as many times 5 as is necessary so long as we add that same number times -19 to p. Adding 20 times 5 to c would just make it 0, so we need to add at least 21 times 5, bringing c to a value of 5. Matching this with 21 times -19 being added to p, brings p to 400 + (21)(-19) = 400 - 399 = 1. So this must be the unique solution as if we were to add another 5 to c we would have to subtract another 19 from p making that negative, so we can't do it. Indeed 5 cows and 1 pig do make the solution, with the consequence that there are 94 chickens, once you look back at the original equations. To summarize this last paragraph in equations:
19 (-1) + 5 (4) = 1, so
19(-100) + 5 (400) = 100, but
19(5) + 5(-19) = 0
so we can add 21 times this equation to the previous, giving
19(5) + 5(1) = 100, which is the solution.
Depending upon the problem, or perhaps depending upon which variable we chose to eliminate initially, we might have had zero, one, or multiple solutions with positive integral values for the first function f(c,p) = 100. We need to try each solution to see whether it produces a positive integral value for the third variable. This might eliminate none, some, or all of the solutions for the first function.