# Problem Solving

I was lucky to have my early development in math shaped by an incredible high school math teacher – Mr. Waterman.  He lived and breathed math and got out of bed everyday thinking about how to teaching problem solving to high school kids.   I ate it all up back then and the problem solving techniques that I first learned in his classes remain important pieces of my mathematical tool kit even today.   It is actually pretty fun to look back and see how ideas originating in high school math contests can come into play 25+ years later at work.  Although maybe the fact that I still use these ideas every day explains why I think problem solving is such an important part of math education.

For the last few weeks I’ve been seeing a lot of posts on twitter about problem solving.  Yesterday, for example, I ran across this wonderful post from Fawn Nguyen:

Making Problem Solving Part of the Math Curriculum

While others may not, I find it difficult to talk about problem solving in the abstract.  In talking or learning about problem solving a specific example is much more valuable to me than 1,000 words of abstract discussion.  Two of the most amazing specific examples I’ve seen lately come from the Field’s Medalist Tim Gowers and from the head of Art of Problem Solving, Richard Rusczyk.    Gowers decided to “live blog” his attempt at working through problem 1 in this year’s International Mathematics Olympiad.   It is an all too rare treat to see the thought process of one of the top mathematicians in the world in real time:

Tim Gowers walks through an IMO problem

Richard Rusczyk’s example is also a math contest problem – in this case problem #24 from the 2013 AMC 12.  The problem asks a question about the quadratic function  $f(z) = z^2 + i z + 1.$  I’m sure that as a kid a quadratic with an imaginary component would have really intimidated me, but Rusczyk’s calm and systematic approach to walking through the problem takes all of that intimidation away.  It is such a great example of problem solving – in fact this blog post has been delayed by about 40 minutes as I’ve watched the video twice because I enjoy it so much!

With these two examples in mind, I thought it would be fun to do my own example, though believe me, it isn’t within a million miles of the quality of either of the examples above.  However, what I think is incredibly important about the Gowers and Rusczyk examples is that they show the problem solving process, and I think that the more examples of that process that are out there the better.  So, neither an IMO problem nor a problem from a big US math contest, but here’s the process that I went through thinking about a fun little problem I saw posted on twitter a week ago:

I was actually up in Boston running around with the family when I saw the original tweet, but for some reason the problem stuck with me and I spent the next few days sort of daydreaming about it.

The first thing I did was think through cases that I hoped would be easy – quadratic equations (and also simplified the problem a tiny bit by assuming that the infinitely many perfect squares arose from positive integers n).  Take a polynomial like $x^2 + 2x + 5$, for example.  We can rewrite this expression as $(x + 1)^2 + 4$.   Since the only perfect square than is 4 more than another perfect square is 4, this new expression helps us see that $x^2 + 2x + 5$ will not be a perfect square for infinitely many integers $x$.

What if the linear term has an odd coefficient, though – say $x^2 + 3x + 1$.  Writing this expression as  $(x + 1)^2 + x$ solves the problem in a slightly different way than the prior case.  For $x > 1$, we see that the new expression is greater $(x + 1)^2$ but less than $(x + 2)^2$.  Since  it lies in between two consecutive perfect squares, it cannot be a perfect square and so it will not be a perfect square for infinitely many positive integers x.

Since the coefficient of the linear term will either be even or odd, that takes care of the quadratic case. The only way that a quadratic polynomial can satisfy the conditions of the problem is if it can be written as $(x + a)^2$ for some integer a.  Great, but how does this fact generalize to higher degree polynomials?

The next example I thought about was the 4th degree polynomial $x^4 + 3x^3 + 3x^2 + 2x + 1 = (x^2 + x + 1)^2 + x^3$. From the quadratic case I thought that transforming the original polymonial into a perfect square plus a polynomial with a degree of 2n – 1 would be the way to go. Unfortunately I couldn’t see what to do, and certainly couldn’t see anything that would help in the case where the remainder was a general cubic polynomial.  What’s stopping a perfect square plus a number described by a cubic polynomial from being a perfect square just by accident? Hmmmm.

As we ran around Boston the problem stayed in the back of my mind. One day I got the idea to look for a different approach to the quadratic case and that turned out to be the key idea for getting my head around the problem. Writing the polynomial $x^2 + 3x + 1$ as $(x + 3/2)^2 - 5/4$ also helps you see that this polynomial cannot be a square for infinitely many integers.  Really for the same reason as above – the value is trapped between $(x + 1)^2$ and $(x + 2)^2$. This new expression led me to stumble on a similar statement for higher degree polynomials that was a nice little surprise (to me anyway!).

It turns out that completing the square generalizes in a neat way. For the case we are looking at – a monic polynomial of degree 2n with integer coefficients – the generalization is that you can always find a monic polynomial of degree n with rational coefficients whose square matches the first n + 1 terms of the original polynomial. In math symbols, I mean that we can write:

$x^{2n} + a_{2n-1} x^{2n-1} + a_{2n-2} x^{2n-2} + . . . + a_0$

as

$( x^n + b_{n-1} x^{n-1} + . . . + b_0 )^2$ + $c_{n-1} x^{n-1} + c_{n-1} x^{n-1} + . . . + c_0$

where the a’s are integers, and the b’s and c’s are rational.  The the 4th degree case I was looking at above gives an illustrative example:

$x^4 + 3x^3 + 3x^2 + 2x + 1 = (x^2 + (3/2) x + 3/8)^2 + 7x/8 + 55/64.$

Convincing yourself that this generalization of completing the square is true isn’t all that difficult.  When you square the polynomial with the $b_{i}$‘s above, you see that $2b_{n-1}$ has to be equal to $a_{2n-1}$, so solving for $b_{n-1}$ is exactly the same exercise you do when you complete the square for a quadratic.  Once you have the value for $b_{n-1}$ you see that $a_{2n-2}$ has to equal  $(b_{n-1})^2 + 2b_{n-2}$, which give you the value of $b_{n-2}.$  Similarly, once you have the first k $b_{i}$‘s, solving for the next one just involves solving a linear equation in $b_{n - k - 1}$.  Basically, you just end up dividing by 2 a lot.

Although the rational coefficients present a small problem, we can use  ideas similar to the ones  we used in the quadratic case to show that for large values of x the above expression cannot be a perfect square.  In the above example of the 4th degree equation, assume that the expression is equal to $z^2$ when x and z are integers.  Multiply everything by 64 to arrive at the equation:

$(8x^2 + 12x + 3)^2 + 56x + 55 = (8z)^2$

For large values of x, the expression on the left hand side lies between the consecutive perfect squares $(8x^2 + 12x + 3)^2$ and $(8x^2 + 12x + 4)^2$.   For clarity, note that $(8x^2 + 12x + 4)^2 = (8x^2 + 12x + 3)^2 + 2*(8x^2 + 12x + 3) + 1$.    As long as x is sufficiently large, $2*(8x^2 + 12x + 3) + 1$ will be larger than $56x + 55$ since the $x^2$ term will dominate the $x$ term.  Thus for sufficiently large integers x, the value of $(8x^2 + 12x + 3)^2 + 56x + 55$ (which we’ve assumed to equal $(8z)^2$) lies between two perfect squares and cannot be a perfect square itself.  So neither $(8z)^2$ nor $z^2$ can be a perfect square for sufficiently large values of x which, in turn, means that the original expression cannot be a perfect square for infinitely many positive integers x.

Essentially the same argument will work for any monic polynomial of degree 2n with integer coefficients, and also essentially the same argument works for showing that the polynomials cannot take on infinitely many perfect square values for negative integer values of x.

So, the generalization of completing the square shows that the only time a monic polynomial in x of degree 2n will take on infinitely many perfect square values for integer values of x is when the polynomial itself is a perfect square.  In that case, all of the values will be perfect squares as desired!

I doubt that my solution is the best or the most elegant, but I had a lot of fun thinking through this problem.  I’m also happy to have stumbled on this generalization for completing the square which I’m surprised to have either never seen previously or (more likely) just forgotten about.

As I said at the beginning of this post, the lessons about problems solving that I learned in the three years I spent in Mr. Waterman’s classes were such an important foundation in my own mathematical development.  Even though I’m not longer in academic math these problem solving strategies play a critical role in my work just about every day.  Away from work I try to communicate those lessons to my kids when we talk about math.

I hope that more mathematicians will follow the lead of Gowers and Rusczyk and give some public examples  of their own problem solving process so that everyone – and especially students – get lots of different looks at the problem solving process.  Seeing that work will help show that mathematical thinking  isn’t  about finding answers instantly and effortlessly, but often involves lots of trial and error, false starts, and most importantly joy at making a little progress.  These are important lessons from math with applications that go far beyond whatever specific problem you happen to be working on at the time.