April 22, 2016 – Mike's Math Page

Earlier today I wrote about problem #! from the 2016 European Girls’ Mathematical Olympiad:

I thought the problem was wonderful and “live blogs” of different people solving the problem would help people (kids especially) learn about different aspects of mathematical thinking.

Here’s the problem:

And here’s a sketch of the process I went through to solve it. First, though, here’s what my scattered notes looked like by the time I got to the end:

Step 1: Total confusion after reading the problem. You just have a seemingly random set of numbers . . . how can you show that the max of one set of expressions is even related to the min of another set of expressions? No idea what to do.

Step 2: Oh wait, I remember the arithmetic mean / geometric mean inequality – that’s what’s written down in the middle of my note paper. You’ll see the scratched out inequality when I first wrote it down, because I remembered the inequality backwards.

This inequality comes from the simple idea that the quantity $(a - b)^2$ has to be greater than or equal to zero. The idea is that any real numbers squared has to be greater than or equal to zero. When you expend the algebraic expression you get $a^2 - 2ab + b^2 \geq 0$ which simplifies to $a^2 + b^2 \geq 2ab.$

That’s what I’ve got written down in the middle of the page. Feeling good at this point in the problem solving process!

Step 3: Wait a minute, the inequality in the problem goes the other way. It says less than or equal to not greater than or equal to. What?? This problem seems to want me to prove the exact opposite of the arithmetic mean / geometric mean inequality. But this inequality is so true that it has its own Wikipedia page:

The Arithmetic Mean / Geometric Mean inequality on Wikipedia

So proving the opposite is probably not going to be the right strategy!

Ummmm . . . . . Not feeling good anymore . . . .

Step 4: Well . . . $x_{i}^2 + x_{x+1}^2$ sort of looks like a geometric expression. It relates to the distance between the point $(x_i,x_{i+1})$ and the point (0,0) in the plane – maybe there is a geometric angle to the problem. What would the term $2x_j x_{j+1}$ mean in this setting? It would be an area, or maybe twice the area of a rectangle, but how would I compare that to a length? Hmmm . . .

No idea . . . .

Step 5: Time for an example – you’ll see that I wrote down the numbers 1, 3, and 5 in the upper left hand corner of the paper and in the upper middle right of the paper I wrote down the values for the two sets of expressions in the problem:

The min of $x_{i}^2 + x_{x+1}^2$ was 10 and the max of $2x_j x_{j+1}$ was 30, so the inequality we are trying to prove seems to be true for the numbers 1, 3, 5. Yay, I guess, but what now?

Step 6: I started wondering about why the problem wanted you to use an odd number of numbers, so I tried to see if I could find a set of 4 numbers that didn’t work. Maybe that would help me see something. Just to keep the numbers as simple as possible I tried 1, 2, 1, 2 and found that the min / max inequality in the problem didn’t work. $x_{i}^2 + x_{i+1}^2$ was always 5 and $2x_j x_{j+1}$ was always 4.

Interesting.

Step 7: You’ll see that I’ve got $a < b < c$ written down in the lower left hand part of my paper. Maybe what was special about my 1, 3, 5 example is that the numbers were increasing. When you have three increasing numbers like this $a^2 + b^2$ will be less than $2bc$ because $2bc$ is greater than $2b^2$ and $2b^2$ is greater than $a^2 + b^2$ since $b$ is greater than $a.$ That’s what this part is saying:

That’s it for the notes in the lower left hand corner. A nearly identical argument would show that three decreasing numbers would produce a solution to the problem, too.

By the way, once you find that one of the $2 x_{i} x_{i+1}$ expressions is greater than one of the $x_{j}^2 + x_{j+1}^2$ expressions, you’ve solved the problem because the max of the $2 x_{i} x_{i+1}$ expressions has to be greater than or equal to the one you’ve found and the min of the $x_{j}^2 + x_{j+1}^2$ expressions has to be less than or equal to the one you’ve found. That means the max of the $2 x_{i} x_{i+1}$ terms will be larger than the min of the $x_{j}^2 + x_{j+1}^2$ terms.

So, yay, we can solve the problem if we have three increasing (or decreasing) numbers in a row, but why does there have to be three numbers like this in a row? It seems as if the numbers are chosen totally at random. Hmmmmmmm . . . .

Step 8: The triangle on the right hand side of my notes – it wasn’t just a doodle!

The numbers $x_1$ to $x_n$ aren’t really arranged in a row. The problem points out that the last comparison involves $x_{n+1}$ which is equal to $x_1$ . The numbers are really going around in a circle – or a triangle as I’ve drawn.

As you move from one number to the next you will either increase or decrease (because if two are ever equal the inequality in the problem is an equality and the problem is solved immediately). You are making $n$ up or down movements as you move around the circle of numbers, but since $n$ is odd you have an odd number of total steps around the circle, and the number of times you move up in value as you step cannot be equal to the number times you move down in value.

Aha.

You can imagine going around the triangle and having 2 up comparisons and 1 down. The two ups have to be next to each other because there are only three sides, so any arrangement of the two ups and one down has to have the two ups next to each other. As soon as you have two ups in a row you know you have three increasing numbers.

The general case isn’t that much harder. Assume that you have more ups than downs and you want to try to spread out the ups and downs as much as possible so that there are never two of the same type in a row. Put, for example, an up in the first position, a down in the second, and etc. The ups will always be in odd positions and the downs will be in even positions. If you are really lucky and can spread them out as much as possible you’ll have an up in the last position (since that position is odd) with no ups or downs next to each other.

But WAIT, since the numbers are going around in a circle the last position is really next to the first position. oops – even if you are lucky enough to be able spread the ups and downs out as much as possible you end up with two next to each other. So . . . you are forced to have either two ups or two downs together (which ever type of comparison there are more of) when you put an odd number of numbers around a circle!

That’s it – that’s the main idea in the problem!

I know this write up isn’t perfect and certainly not perfect enough for something that a contestant would need to write up during the contest, but I wasn’t going for perfection here. I just wanted to communicate my thought process as I worked my way through the problem.

This was a fun problem to think through and I hope that some ideas about how people trained in mathematics think about problems like this one came through in my write up.

Two interesting math contest related articles this week. First in the Atlantic an article about different participation rates in math contests for girls and for boys:

Math for Girls, Math for Boys

By the way, the 2009 study by Ellison and Swanson mentioned in the article has one of the most interesting (and frankly baffling) statements about math education that I’ve ever seen. From the top of page 3:

“Whereas the boys come from a variety of backgrounds, the top-scoring girls
are almost exclusively drawn from a remarkably small set of super-elite schools: as many girls come from the top 20 AMC schools as from all other high schools in the U.S. combined.”

As far as I know, no one has done a follow up study to see what’s going on at those 20 schools. Seems like a very interesting topic to study.

The second article was about the US team finishing 2nd at the European Girls’ Math Olympiad:

US Team Takes Second at European Girls’ Mathematical Olympiad

After reading this article I clicked through to see the problems, and problem #1 caught my attention:

I found the problem to be fun to solve and also pretty interesting mathematically. It struck me as a great problem to use to show how mathematicians think.

Tim Gowers did an fantastic “live blog” showing his own thought process in solving a problem from the International Mathematics Olympiad a few years ago:

Tim Gowers walks through an IMO problem

I love this self-depricating line: “You idiot Gowers, read the question: the a_n have to be positive integers.”

Richard Rusczyk also has a fantastic example showing mathematical thinking involved in solving a contest problem – in this case problem #24 from the 2013 AMC 12.

So, my challenge to math folks is this – live blog your solution to problem #1 from the 2016 European Girls’ Mathematical Olympiad. Share your thinking, share your false starts, share the “aha” moments. I think this problem provides a great opportunity for people to see how people in math think, and, importantly, that the path to the solution of a problem isn’t always a straight line.

M	T	W	T	F	S	S
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

Day: April 22, 2016

My respose to my challenge

A challenge / plea to math folks