Thursday, January 10, 2008

An Exceptional Math Contest Problem

Update: The solution I emailed to the director of the Math League is at the bottom after you scroll down a ways. Note how this ties into the difference of squares problem I posted the other day!

A very good friend of mine who runs one of the most successful math league contests in the US has given me permission to reprint the question below with the following attribution:
“Copyright Mathematics Leagues Inc 2007. May not be reproduced without permission of the copyright holder.”

This question was the last question on a recent contest. It certainly made me think! I felt the need to be rigorous about justifying one of the steps and that was the reason for the
M2 - N2 = 12 post from the other day. There are at least 3 methods that have been found thus far, according to my friend. Teachers often send in their own solutions and some even get included with the official solutions. My feeling is that questions like these are vital for our students intending to pursue higher mathematics, not just for those who happen to participate in contests. I also believe that variations on great questions like this will have an eternal life...


There's exactly one real number a for which ax2 + (a+3)x + (a-3) = 0 has two positive integer solutions for x. What are these values of x?

Have fun with this!
For more information about the Math League, visit here.

Scroll down to see the solution I sent to the directors of the Math League...

First of all, I'll state the answer I obtained before giving the details:

A real number
a which produces two positive integer solutions is a = -3/7 which does lead to the solutions x = 4 and x = 2. Proving that this is the only real value of a is far more challenging and I suspect that there's a much easier solution than the one I found. Anyway, here's my approach:

In order to simplify the original equation, divide both sides by a to make the leading coefficient equal to 1:

x^2 + (1+(3/a))x + (1 - (3/a)) = 0
To simplify further, let b = 3/a:
x^2 + (1+b)x + (1-b) = 0
From a well-known rule about the roots of a quadratic equation, the sum of the roots in this case equals -1-b and the product of the roots is 1-b. Since the roots must be positive integers, it follows that b is an integer less than -1. Remember for later:
b must be negative!

From the quadratic formula, we obtain the roots to be:
x = ((-1-b) +- SQRT(b^2+6b-3))/2.
In order for the roots to be integers, the expression b^2+6b-3 must be a perfect square.
I will rewrite this expression by completing the square:
(b+3)^2 - 12 and this must equal a perfect square , call it N^2.
Let b+3 = M, then we must have M^2 - 12 = N^2 or
M^2 - N^2 = 12. It's easy to guess a difference of perfect squares equal to 12, namely 16-4, but I will now prove this is the only solution:

Factoring, we have (M+N)(M-N) = 12 where M,N are integers.

The only pairs of factors to consider are: 12,1; 6,2; 4,3 as well as their negatives.
In order for M,N to be integers, the factors of 12 must BOTH be EVEN so the only possibilities are 6 and 2 or -6 and -2..
If M+N = 6, M-N = 2, then, by adding, M=4 and N=2. From b+3 = M, we would have b = 1, but this doesn't work since b must be negative (see above!)
Therefore M+N = -6 and M-N = -2. From this we have M=-4 and N=-2.
Then b = M-3 = -4 - 3 = -7.
b =-7 leads to the quadratic equation: x^2 + (1+(-7))x = (1-(-7)) = 0 or
x^2 - 6x + 8 = 0. Factoring we obtain the roots to be x = 4 and x = 2.

Since b = 3/a, it follows that -7 = 3/a or a = -3/7.


Totally_Clueless said...

Wicked problem, Dave!

I was able to arrive at two positive integer solutions after getting to an expression for an integer m such that m^2-12m-12 = (m-6)^2-48 had to be a perfect square. Thus, we had to find two numner n &k such that n^2 -k^2 = 48, which gives the connection to the previous post (neat!).

Of these, only one m gives both integer solutions, the other two I could find gave one integer solution and one half-integer solution.


Dave Marain said...

Wicked indeed! I'll post my detailed solution in a couple of days if others choose to hold off. I appreciate that you only hinted at the solution!
Remember, this was one of 6 contest questions. Students had 30 minutes to complete the contest. I have a feeling I would have needed more time than that just for this question alone!!

Totally_Clueless said...

Hi Dave,

I second that opinion about the time needed, but of course, old age and senility may have something to do with that in my case :-)


Joshua Zucker said...

Maybe too much of a spoiler here:

Since the sum of the roots is -(a+3)/a and the product is (a-3)/a, and the sum and product are both integers, then both a+3 and a-3 must be divisible by a.

This leaves you with very few possibilities to guess and check -- a = 1 or 3 or -1 or -3, it looks like.

Dave Marain said...

Hi Joshua! It's been a long time...
I started the same way you did until I realized that 'a' did not have to be an integer! I don't think the values of 'a' you listed will produce integer values of x.

Joshua Zucker said...

I thought it was quickly obvious that a = 3 gave 3x^2 + 6x = 0 which gives x = 0 or -2, and we're done.

But then I noticed that the original problem calls for POSITIVE integer values of x.

So, my bad, Dave. Thanks.

OK, let's try again ... Suppose a = p/q. Then we have -(p/q + 3)/(p/q) and (p/q - 3)/(p/q) are both integers. Multiply top and bottom by q, so (-p - 3q)/p and (p - 3q)/p are both integers. Now, interesting, that seems to show that either p is 3 or q is divisible by p (so if p/q is in lowest terms, then p is 1).

Let's look a little more at this p=1 possibility: then we have
(1/q)x^2 + (1/q + 3)x + (1/q - 3) = 0. Multiply through by q, and we have
x^2 + (1+3q)x + (1-3q) = 0 having two positive integer solutions. So q is pretty clearly negative, let's try some guess and check again:
x^2 - 2x + 4, nope.
x^2 - 5x + 7, nope.
x^2 - 8x + 10, nope.
x^2 - 11x + 13, nope.
x^2 - 14x + 16, nope.
In fact I think it's pretty clear that this pattern will never work (the sum of the two roots can't be so close to the product).

So let's try p = 3 instead?
(3/q)x^2 + (3/q + 3)x + (3/q - 3) = 0.

So multiply through by q/3 to get
x^2 + (1+q)x + (1-q) = 0
and again q is clearly negative, try q = -2 first
x^2 - x + 3 = 0
x^2 - 2x + 4 = 0
x^2 - 3x + 5 = 0
x^2 - 4x + 6 = 0
x^2 - 5x + 7 = 0
x^2 - 6x + 8 = 0
ah ha!
Looks like 2 and 4 are the solutions with q = -7 and thus a = - 3/7.

I think there's probably a shorter cut to all this, because in both cases we got a sum and product that differ by 2. There aren't many pairs of positive integers where that's true! In fact (2,4) is the only one, I think.

Dave Marain said...

Hey folks...
Read the original post again to see the solution I sent to the Math League. You have to scroll down a bit since I didn't want it immediately visible (kind of silly actually!). The argument is fairly rigorous...

Totally_Clueless said...

My approach was similar to Dave's, but slightly different. The sum of the sum and product of the roots of the original equation was -6/a, which had to be a positive integer. Thus, I had to choose a of the form -6/m. Rewriting the equation and solving it, I had the condition that m^12-12m-12 had to be a perfect square. There are 3 values: 13, 14 and 19. m=14 gives the solution we want, and m=13 and m=19 give one integer solution and one half integer solution.


Dave Marain said...

I like that tc! Cleaner than mine...
The director of the league sent me a couple of other solutions and I may share those as well.

Anonymous said...

Nice problem. Once you have it down to x^2 + (1+b)x + (1-b)=0, let r,s be the roots and then r+s = -1 -b and rs= 1-b (note then r can't be 1). Subtract these equations to get rs-r-s=2 which is symmetric in r and s. Now write s as a function of r, i.e. s = (2+r)/(r-1) and looking at the graph of this function for r>1, see (using the symmetry of the graph around the line s = r) that if r > 4 then 1< s < 2 which rules out any integer pairs when r > 4. Thus the only possible r values are 2, 3, 4, which yield s = 4, 5/2, 2 and so the root pair 2 and 4 is the only possible pair.... Ned

Dave Marain said...

Cleaner and more elegant solution than mine. I like how you focused directly on the roots rather than the value of 'b' as i did.

I have another of these challenge problems coming at the end of Feb - try it!! It will be geometric in nature rather than algebraic, but I think you will like it.