Warning: the following post contains algebra; I just thought I should be transparent. If three-space, divisibility, or inequalities make you queasy, please escape while you can. This afternoon, I was re-united with an old problem that I had managed to shunt into the back of my memory. Maybe because I remember it being incredibly frustrating, but (most likely) because it doesn't fit nicely into a niche of school mathematics.

The problem is summarized as follows:

You need to buy exactly 100 pets. You have exactly $100 to do so. Dogs cost $15, Cats cost $1, and Mice cost $.25. How many of each pet do you have to buy?

(You must buy at least 1 of each)

I first encountered a variation of this problem at SUM 2010. (Saskatchewan Understands Mathematics) A keynote speaker presented the problem to a room full of teachers. Once you have had time to tinker with the problem, you can guess what happened in the room. Almost every pen began to scratch out equations in hope of setting up an augmented matrix. Systems of equations dominate a large portion of grade 12, so it was natural for teachers to go there. Soon there was an interesting buzz around the room as people discovered that they could only create 2 equations, but had 3 variables. Teachers began smirking, and dismissed the problem as "cute". They had to categorize it as such because their sacred cannon had failed to find a solution. Of course, some adventurous teachers set out with a guess-and-check method. The most senior teachers in the room scoffed at the triviality of the approach. Imagine! A high school teacher stooping to the level of trial and error!

Once the standard system of equations method is abandoned, problem solvers take two main approaches. Both have value, and there is meaningful mathematics in both.

The first method is the previously mentioned trial and error method. As students begin to modify their results, they develop conjectures that will get them closer to a solution. We know that the number of pets always has to equal 100; we also know that we can't have pieces of pets. (If we keep the problem PG) We also notice that mice need to come in groups of 4 so the dollar amount remains an integer. A logical approach begins with a set number of dogs and cats, and then increasing the number of mice by 4 at a time. This could take several "guesses", but there is rich understanding in this method. The numeracy needed to understand the 'mouse conjecture' and the balancing of dollars and pets is quite complex. Such methods of problem solving are rarely recognized for their merit.

The second method involves a mixture of algebra and logical reasoning; I will detail it below, but I don't want to lose the purpose of the post. School math does not represent the be-all and end-all of mathematical value. Mathematical intuition is awfully hard to develop within standard algorithms. With that point made, I now proceed to sell-out to rigor.

I begin with a definition of variables, and a list of equations and inequalities to define the problem.

let 'x' be the number of dogs

let 'y' be the number of cats

let 'z' be the number of mice

x>=1, y>=1, z>=1, x<=98, y<=98, z<=98

x+y+z = 100

15x + y + .25z = 100

This is all we need to proceed. It is also vital to this solution that we keep in mind the fact that x,y, and z must all be natural numbers--no fractional pets! The inequalities bound the solution in the first octant. If you are unfamiliar with 3-space geometry, it is the section of the graph where all three variables are positive.

The 2 equations are those that would make up the traditional system of equations. Instead of using them this way, we solve both for 'z' and set them equal to one another. This procedure will give us the equation of the line of intersection between the two planes defined by the equations.

.25z = 100 - 15x - y |*4

(1) z = 400 - 60x -4y

(2) 100 - x - y = z

Setting (1) equal to (2) we get:

400 - 60x - 4y = 100 - x - y

300 - 59x - 3y = 0

-3y = 59x - 300

y = (-59/3)x + 100

This is the formula for the line of intersection in our nice, comfortable y=mx+b form. Now we take a step back and use the fact that 'y' must always be a whole number to prove that the term (-59/3)x must also be a whole number. In order for this to be true, 'x' must be divisible by 3 (to cancel out the denominator). So we define:

x = 3a, where 'a' is a whole number

This essentially states that the value of 'x' must be such to cancel out the denominator value of 3. We know that 59 will not cancel it out because 3 is not a factor of 59. We use the bounds on 'x' to get the bounds on 'a':

x<=98

so...

3a<=98

a<=(98/3)

because 'a' must be a whole number, it is never equal to (98/3)

a<(98/3)

a<32.6666

again, 'a' must be a whole number so...

a<=32

Now we set up the inequality for 'y' using the equation of the line of intersection:

y = (-59/3)x + 100

y = (-59/3)*3a +100 (because x=3a)

y = -59a +100

Use the fact that 1<= y <= 98 to set up...

1<= -59a +100 <= 98 |-100

-99 <= -59a <= -2 | /-1

When we divide by a negative, we flip the inequalities...

2 <= 59a <= 99

(2/59) <= a <= (99/59)

Again, 'a' must be a whole number so we round the results to whole numbers.

1 <= a <= 1

Here, we need to recognize that (2/59) would actually be rounded to zero, but it can't be because if a=0 then x=0 by definition. From the original problem, we must have at least 1 dog. This inequality statement gets us our desired result. There is only 1 viable, solution--when a=1.

a=1, so x=3(1)

x=3 --> 3 dogs must be bought.

so...

y = (-59/3)x + 100

y = (-59/3)*3 +100

y = -59 +100

y = 41 --> 41 cats must be bought.

so that leaves...

z = 100 - 3 - 41

z = 56 --> 56 mice must be bought.

(3, 41, 56) is the only point consisting solely of whole numbers on the line of intersection.

The process of back-substitution is very rapid once we find our first value. Let's check our solution (which, by the way, is the only solution according to our algebra).

3 Dogs, 41 Cats, 56 Mice = 100 Pets

$45 for Dogs, $41 for Cats, and $14 for Mice = $100

Upon further review, it turns out that the trial and error method provides far less of a headache, but the rigorous algebraic method provides the interesting proof that there is only 1 solution. I encourage those readers that made it to the end to see the value in both approaches.

NatBanting

Spoiler alert:

ReplyDeletehttp://davidwees.com/javascript/dogscatsmice/

I solved this with a script. Is that cheating? :)