My respose to my challenge

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.

my experience was extremely similar to yours, so I’ll mostly note differences rather than a full write-up:

First difference, I focused on specific points in the question that seemed technical/minor: n is odd and the sequence “loops around” (x_{n+1} = x_1).
Impression was that these would be crucial.

Also explored case of even n and considered that, for any particular pair of numbers, the inequality would go the other way.

Dead-ends around thinking about cute ways of arranging the data from the problem, thinking that there would be some kind of pairing to create where one number didn’t have a partner (b/c n is odd).

Considered that there might be an induction argument, so focused on n=3.
Realized that, for n=3, all pairs of the 3 numbers are adjacent, so I could assume we had a monotonic sequence a< bb>c for which the inequality was easy. From this, realized that, for any n, I just need to find a string of three increasing or decreasing numbers in the sequence. This was the breakthrough.

Decided to imagine the signs of the differences as Xs and Os b/c I didn’t care which was which, just needed to distinguish the two signs. If we start labeling the sign of the first difference as X and try not to have two Xs or Os together (formalize through proof-by-contradiction), then we get a sequence
(XO)^((n-1)/2)XX
where the last two Xs come from the sign of x_{n+1} – x_n = x_1-x_n and x_2-x_1.

Other logistical differences:
– didn’t have time to sit down to write anything out, so keeping everything in my head helped me stick to simple methods.
– took a long time from reading your challenge to solving it (roughly 2 days). Of course that wasn’t all spent thinking about the problem, but still, way below the standards of the contestants!

4 thoughts on “My respose to my challenge”

Patrick Sepúlveda says:

April 24, 2016 at 3:00 am

I remenbered that one of the question in my test in the first year of University is the third photo, try to demostrate its take a lot of time 😦 but i did! I feel sooooo happy for that

Joshua says:

April 24, 2016 at 2:19 pm

my experience was extremely similar to yours, so I’ll mostly note differences rather than a full write-up:

First difference, I focused on specific points in the question that seemed technical/minor: n is odd and the sequence “loops around” (x_{n+1} = x_1).
Impression was that these would be crucial.

Also explored case of even n and considered that, for any particular pair of numbers, the inequality would go the other way.

Dead-ends around thinking about cute ways of arranging the data from the problem, thinking that there would be some kind of pairing to create where one number didn’t have a partner (b/c n is odd).

Considered that there might be an induction argument, so focused on n=3.
Realized that, for n=3, all pairs of the 3 numbers are adjacent, so I could assume we had a monotonic sequence a< bb>c for which the inequality was easy. From this, realized that, for any n, I just need to find a string of three increasing or decreasing numbers in the sequence. This was the breakthrough.

Decided to imagine the signs of the differences as Xs and Os b/c I didn’t care which was which, just needed to distinguish the two signs. If we start labeling the sign of the first difference as X and try not to have two Xs or Os together (formalize through proof-by-contradiction), then we get a sequence
(XO)^((n-1)/2)XX
where the last two Xs come from the sign of x_{n+1} – x_n = x_1-x_n and x_2-x_1.

Other logistical differences:
– didn’t have time to sit down to write anything out, so keeping everything in my head helped me stick to simple methods.
– took a long time from reading your challenge to solving it (roughly 2 days). Of course that wasn’t all spent thinking about the problem, but still, way below the standards of the contestants!

1. mjlawler says:
  
  April 24, 2016 at 2:22 pm
  
  thanks! You are the first person to respond.
  
Joshua says:

May 1, 2016 at 2:05 pm

In case it appeals to your tastes, I built an activity for my kids (far younger than the EGMO target age) inspired by this question. The main meat is here: Reversed Inequality

After going through most of this discussion, I did talk about the EGMO problem itself with my middle son. So far, we have only done some examples of odd and even length series to get a flavor for when the inequality in the problem holds and when it doesn’t.

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

My respose to my challenge

Published by mjlawler

4 thoughts on “My respose to my challenge”

Leave a Reply Cancel reply

Share this:

Like this:

Published by mjlawler

4 thoughts on “My respose to my challenge”

Leave a Reply Cancel reply