Thursday, April 3, 2008

Monthly Math League Challenge: List all ordered triples of positive integers (x,y,z) whose product is 4 times their sum and x>y>z.

The problem in the title is another wonderful challenge for our readers or for students. Questions like these are powerful tools to develop student reasoning and problem-solving prowess. Once again I have received permission from the directors of the Math League to publish this question on MathNotations. This was the last question from the first contest this year.

Please cite the question in the title as:
Copyright Mathematics Leagues Inc 2007. May not be reproduced without permission of the copyright holder.

You can learn more about Math League Contests at the Math League website.

Now you know that I'm not going to simply copy a problem and just leave it at that!
How can we make this more of an enrichment experience for our algebra students who may not quite be ready for the contest level. Can you guess? Scroll down...


Well, what makes the contest problem particularly formidable is the use of three variables. In fact, two numbers is already a difficult problem for most! So we use the "Let's Make It Simpler" strategy:

Find all ordered pairs (x,y) of positive integers whose product is four times their sum and x>y.

I'll begin some analysis, starting with our basic equation:
xy = 4(x+y)
.

Before one starts the traditional solving for y in terms of x ritual (then let's go to the graphing calculator), we need to remind our students that this is a positive integer problem, which allows for a somewhat different kind of approach.
I also frequently suggest to students to consider the case that x = y even though the restrictions do not allow this.
If x=y, then x2 = 8x leading to x=8, y = 8 (or ____?). Even though this is not allowed, it could suggest other solutions. Those who enjoy graphical solutions will also appreciate that this solution is one of the two points of intersection of the graph of our basic equation with the line y = x. I'll leave it to our readers to find the other.

Note that from xy = 4x + 4y we can see that neither x nor y can equal 4. For example, if x=4, we'd obtain 4y = 16+4y, which is impossible.
Similarly, neither x nor y could be less than 4. This is more readily proved algebraically. I'll omit the details.

Note: Another important tool for students in solving these kinds of problems is to consider symmetry. The basic equation is symmetrical in x and y. Symmetry can be very useful.

Ok, while most students are using guess-test methods (they would call it 'plugging in'), we will solve for y in terms of x (skipping a few steps):
y = 4x/(x-4).
There's a well-known algebraic device students need to see here when finding integer solutions, which is equivalent to long division. Rewrite the previous equation as:
y = (4x-16)/(x-4) + 16/(x-4). I'll let you guess why I subtracted 16 in the first fraction then added it back in the second. This is equivalent to:
y = 4 + 16/(x-4).

Now we use the integer condition (and the fact that x > 4 and x > y) to find solutions:
x-4 has to be a factor of 16 which implies that x-4 could equal 16, 8, 4, 2, or 1. In fact we can show that only 16 and 8 are possible. I'll leave the rest to you...

7 comments:

Florian said...

I would've solved the two variable
problem slightly different here's how:

Write:

x*y = 4x+4y

Look sharp and see that x,y>4.
(otherwise x*y < 4x+4y)

Now rewrite the equation to:

y = 4x/(4-x)

Find bound for x:

4x/(4-x) < x (y < x)
<=> 4x < (x-4)x (x-4 > 0)
<=> 4x < x^2 -4x (x > 0)
<=> 4 < x-4
<=> 8 < x

So far so good, now lets checkout the
rewritten equation a bit more:

y = 4x/(4-x)

By polynomial division we get:

y = 4 + 16/(x-4)

Since y is an integer (x-4) has to be a factor of 16.

From y>4 follows that 16/(x-4) > 0<=> (x-4) <= 16 <=> x<= 20

Now we have an upper and a lower bound for x and we can checkout
for which values of x (x-4) divides 16 (without having to try out
too many values of x>8):

For 8 > x >= 20, (x-4) divides 16 only for two values of x:

x=12 => (x-4) = 8 => y = 4+16/8 = 6
x=20 => (x-4) = 16 => y = 4+16/16 = 5

So the only two solutions are:

(12,8)
(20,5)

Check: 70 = 12*6, 4*12+6*8 = 72
Check: 100 = 20*5, 4*20+4*5 = 80+20 = 100

Joshua Zucker said...

For the two-variable case, use Simon's Favorite Factoring Trick (see http://artofproblemsolving.com or your favorite search engine for details. "Completing the rectangle" is what I call it, but SFFT is a fine name too.).

xy - 4x - 4y = 0
xy - 4x - 4y + 16 = 16
(x-4)(y-4) = 16

Now we need to find two positive integers whose product is 16 ... this won't take long.

I still don't see any particularly elegant ways to do the three variable version; mostly just nice ways of narrowing the possibilities enough to exhaustively check the rest.

Which math league has these problems, by the way? This seems like a pretty good supply of interesting problems. Mandelbrot is still my favorite contest but maybe this one is worth looking into also.

Thanks!

Dave Marain said...

Nice explanation, Florian. My explanation was intentionally haphazard with some teaching heuristics thrown in for instructors who may not have experience in training youngsters for math contests.

Joshua, the SFFT is powerful and definitely works well with problems set up like this. Students should see both the long division and this IMO.

As far as the Math League is concerned, check the link I provided to their website. They have many different levels starting in elementary school and have some excellent talented authors. I've known the directors of the league for over 30 years. Steve Conrad used to edit the Student Math Journal, one of the best publications for mathletes. Remember it? Dan Flegler and I ran our County Math League for a year or so here in Jersey. Mandelbrot actually came along later and I had my math team participate in it from its inception. A somewhat different flavor. I would recommend you consider doing both - they complement each other. The Math League invites more students to try the contests because the first couple of questions on each contest are accessible even to 9th graders. These questions are also excellent for SAT prep. Like I've always told my students - You want 800 on the Math part of the SATs - just take monthly math contests for 2 years!

Florian said...

Now the three variable problem:

xyz = 4(x+y+z) = 4x+4y+4z

There are no solutions if min(x,y,z) > 4.
(otherwise xyz > 4x+4y+4z). Therefor lets
examine z=1,2,3,4:

z=1:

xy = 4x+4(y+1) <=>
x = 4(y+1)/(y-4) <=> (polynom division)
x = 4(1+ 5/(y-4)) <=> 4+20/(y-4)

=> y = 5,6,8,14,24
=> x = 24,14,9,4,5

z=2:

2xy = 4(x+y+2) <=>
xy = 2x+2(y+2) <=>
x = 2(y+2)/(y-2) <=> (polynom division)
x = 2(1 + 4/(y-2)) <=> 2 + 8/(y-2)

=> y = 3,4,6,10
=> x = 10,6,4,3

We stop here checking for values of z, because
z=3,4 are already values which we found.

So the sorted solutions are:

(24,5,1)
(14,6,1)
(9,8,1)
(10,3,2)
(6,4,2)

Eric Jablow said...

There's a research opportunity for students here:

There are many research questions concerning the Markov numbers, which are triples (x, y, z) satisfying

x² + y² + z² = 3xyz, x ≤ y ≤ z.

For example, is any number z in two such triples (as the largest element)?

Look it up in Wikipedia or Mathworld if you want.

Florian said...

Eric, I don't have the time to
evaluate this but my guess is
to write

3xyz = xx+yy+zz

as

3 = x/yz + y/xz + z/xy

Then find all combinations of x,y,z
such that the fractions add up to
an integer. First try non-reducable
fractions then argue the possibility
of reducable fractions with x,y and
z.

Eric Jablow said...

Florian, the arguments about Markov numbers are based on this idea:

(1, 1, 1) is a solution. Now, given any (x, y, z) satisfying this, choose two to keep and 1 to change. It's all the same for (1, 1, 1) of course.

For (1, 1, 1), keep x=1 and y=1: you get

1 + 1 + z² = 3∙1∙1∙z, or

z² -3z + 2 = 0. z=1 is a solution, so its other solution is also an integer, which here is z = 2.

From (1, 1, 2) you can keep a 1 and a 2, and change the other 1. You get (1, 2, 5). You end up with an infinite binary tree. In this case, varying the 5 gets you (1, 1, 2) again, while changing another gives new triples. The structure of this tree has aroused a lot of mathematical interest.

This is not a student challenge problem, but it is a research problem that students can understand.