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 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 which simplifies to
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:
So proving the opposite is probably not going to be the right strategy!
Ummmm . . . . . Not feeling good anymore . . . .
Step 4: Well . . . sort of looks like a geometric expression. It relates to the distance between the point and the point (0,0) in the plane – maybe there is a geometric angle to the problem. What would the term 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 was 10 and the max of 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. was always 5 and was always 4.
Step 7: You’ll see that I’ve got 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 will be less than because is greater than and is greater than since is greater than 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 expressions is greater than one of the expressions, you’ve solved the problem because the max of the expressions has to be greater than or equal to the one you’ve found and the min of the expressions has to be less than or equal to the one you’ve found. That means the max of the terms will be larger than the min of the 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 to aren’t really arranged in a row. The problem points out that the last comparison involves which is equal to . 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 up or down movements as you move around the circle of numbers, but since 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.
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.