Problem Solving part 2 – an old AIME problem

[note: I’m up in Boston today and decided to take a trip to the MIT library to check out a book that Jordan Ellenberg mentions in his book “How not to be Wrong.” I didn’t know the MIT libraries were closed until 11:00 am today (they used to be open 24 hours!!), so I wrote this post fairly quickly in the hour I had to kill waiting for the library to open!. Sorry if it seems rushed – it sort of was!]

I few months ago I wrote about Tim Gowers live blogging his solution to one of the IMO problems:

Problem Solving and Tim Gowers’s live blogging an IMO problem

I thought that live blogging problem solving was a good idea because I think that kids (and everyone) needs to see that most solutions you get to problems aren’t the super perfect “official solutions” and don’t come to mind immediately. In that post I talked through my solution to a number theory problem that David Radcliffe had put on Twitter. Today’s blog is my second attempt at live blogging a problem. I saw today’s problem in Art of Problem Solving’s Precalculus book in the chapter 8 challenge problems.

It also happens to be problem 15 from the 1991 AIME – see the bottom of the page here:

The 1991 AIME Problems hosted by Art of Problem Solving

Here is the problem:

For a positive integer $n$ define $S_n$ to be the minimum value of the sum:

$\sum_{k = 1}^{n} \sqrt{ (2k - 1)^2 + a_{k}^{2} }$

where $a_1, a_2, \ldots, a_n$ are positive real numbers whose sum is 17. There is a unique positive integer $n$ for which $S_n$ is also an integer, find this $n.$

The “live blogging” of my solution is below:

Background:

I had a nice (and short) discussion on twitter with Patrick Honner about Art of Problem Solving’s Precalculus book. I personally like this book because of chapter 8 – the geometry of complex numbers. This chapter, and in particular section 8.5, has content that I’ve not seen anywhere else.

@MrHonner you my copy to look at if you want. It'll be a few years before we get there. For Section 8.5 + the challenge problems and +

— Mike Lawler (@mikeandallie) November 27, 2014

Following that discussion, I grabbed my copy of the book to take a fresh look at chapter 8. I ended up back in the challenge problems and the problem I’m writing about today caught my eye.

My first reaction, frankly, was fear. Back in high school I’d not really understood analysis all that well, and did not have a good grasp of theorems that helped with this type of summation problem – the Cauchy Schwarz inequality, for example: The Cauchy-Schwarz Inequality. An “analysis” approach to this problem probably requires an even more general inequality – Hölder’s inequality – though I would not have known that in high school.

Whenever I see this type of problem, even today, I remember the fear of the analysis ideas that I had in high school. Funny how those old high school fears never seem to go away!

But wait – why would the Art of Problem Solving folks put an analysis problem in the chapter about the geometry of complex numbers? There must be a geometric solution here somewhere? Where is it?

So, let’s look at a few terms:

(1) $n = 1.$ The “sum” is just one term $\sqrt{1^2 + 17^2}$ . Certainly not an integer, but also certainly reminiscent of the Pythagorean theorem and a right triangle with legs of length 1 and 17.

(2) $n = 2.$ The sum is now $\sqrt{1^2 + a^{2}} + \sqrt{3^2 + (17 - a)^2}$ . Now there are two right triangles – one with legs 1 and $a$ , and another with legs 3 and $(17 - a)$ . The sum of the integer length legs is 4, and the sum of the other legs is 17.

Oh, wait, I see what’s going on. The general case is going to have a bunch of right triangles whose “heights” always adds up to 17 and whose “lengths” will sum up to $1 + 3 + 5 + (2n - 1) = n^2.$

See here for the sum of the odd numbers:

How cool! The minimum value of the sum we are being asked to consider is going to come when we can make all of the hypotenuses of these triangles form a straight line, and that length will be $\sqrt{ (n^2)^2 + 17^2}$ from a “large” right triangle with length $n^2$ and height 17.

Sweet – per the statement of the problem, there must only be one right triangle with integer side lengths where one of the side lengths is 17. That shouldn’t be too hard to find.

We know there’s a 3,4,5 triangle, and a 5, 12, 13 triangle, and a 7, 24, 25 triangle – which helps see the pattern fairly quickly. For an odd number, you’ll get a right triangle with integer sides by finding two consecutive numbers that add up to the square of the odd number. From the three examples above: 4 + 5 = 3*3, 12 + 13 = 5*5, and 24 + 25 = 7*7.

So . . . 144 + 145 = 289 = 17*17, so there must be a 17, 144, 145 triangle. By luck 144 is a perfect square and we indeed have a right triangle with integer sides having one leg equal to 17 and the other leg equal to a perfect square.

That means the minimum value of the sum we were looking for is 145, and the value $n$ for that particular triangle is 12.

Fun and super clever problem. Love the connection between geometry and algebra here – especially because the algebra side of this problem still makes me nervous 🙂

Most of the thoughts above were in my head – my “work” for the problem is in the picture below. I’m glad I saw the geometric solution before trying to dive into all of the analysis which, I assume, is way more grungy and way less of a fun solution.

Problem Solving part 2 – an old AIME problem

Published by mjlawler

Leave a Reply Cancel reply

Share this:

Like this:

Published by mjlawler

Leave a Reply Cancel reply