IMO 2010

This year was a great year for the Danish IMO-team: We (I say “we” because I was deputy leader for the team) got our first gold medal, and as a team we beat our previous record, 77 points, by 13 point. In particular I was happy to see that we, together with China and US, was the best country on problem 5 (a problem that Tao thought was more challenging and interesting than problem 6). Denmark is usually in the second half on the country list, and even in a good year like this, we only beat 54% of the teams, so this is really remarkable. One reason, that we got that many points on problem 5 is, that is was a problem in combinatorics, and Denmark is usually good at combinatorics. Another reason is that problem 4 was a geometry problem, and Danes usually hate geometry! (remember that you get problem 1, 2, and 3 on day 1 and problem 4, 5, and 6 on day 2).

As you can see in the above link, Tao started a mini-polymath project about problem 5. So here you can see how a group of mathematicians worked together to solve that problem (and see the problem statement). I decided to ask some of the Danish contestants for a description of how they solved the problem, so that future contestants can see how a single person thinks. Here is Anders Eller Thomsen’s description. Edit: And here is Mathias Bæk Tejs Knudsen’s.

Prove a more general theorem

Often when you try to prove something, it is easier prove a stronger statement. Many of the examples of this, are statements that are proven by induction. E.g. define the sequence of functions by and for . Prove that has real roots (inspired by problem 2 day 1  IMC 2004).

When solving this problem, it helps to find a stronger statement, that is true for all n, because that gives you a stronger induction hypothesis, so that you can make the induction step. But sometimes, this is not enough, and you have to “invent” (or should I say discover?) other cases. Let me give an example of this:

Problem 5 day 1 IMC 1999: Suppose that points of a grid are marked. Show that for some one can select distinct marked points, say , such that and are in the same row, and are in the same column, , indices taken mod .

We have point and rows and columns, so on average there is points in each row and in each column. If we knew that there was at least two points in each row and column, the problem would be easy: We could just start at one point, go to a point in the same row,  then to a point in the same column, and so on. Continue to do this (you can do that, because there is a least two points in each row and column), until you hit a point you have visited before, and you have a loop (if you both began and ended with a “row-move” or with “column-moves”, you can just “jump over” the first point). But unfortunately, there could be rows or columns with only one point or none points at all. If there is both a row and a column with at most 1 point in each, we can delete this row and column, and we have a problem with a grid and at least marked points. This gives us a hope, that we can prove the statement by induction. But what if all rows contains 2 marked points, but some columns only contain 1? If we delete a column, we would get a grid with marked points, so this suggests that we should try to prove something stronger:

Stronger statement: Let points of a grid be marked. Now for some you can select distinct marked points, , such that and are in the same row, and are in the same column, , indices taken mod .

Proof: By induction on n and m. This is true if or if because you can’t choose points in a grid. If we have two point in every row and column, we can just use the above proof, if not, we delete a row or column with at most one point, and thereby reduces the problem to a smaller one.

Here is another IMC problem, you can try to solve:

Problem 5 day 1 IMC 2004: Let be a set of real numbers, where is a positive integer. Prove that there exists a monotone sequence such that

Update: Here are two MathOverflow questions about this subject, where you can find more examples

A solution to IMC09 problem 2

In this post I will explain how I solved the following problem:

Problem: Let , , and be real square matrices of the same size, and suppose that is invertible. Prove that if then .

It is possible to prove this in three lines, but I don’t think that anyone would learn anything about problem solving from just seeing the proof. Instead I want to describe how I solved it. In order to make it easier to read, I decided to write the description in present tense and to include the reader, so instead of “Then I tried to” I write “Now we try to”. I solved this problem about two months ago, so I probably had a lots of thoughts that I have forgotten about now.

At first this problem seems a bit confusing, so we’ll try get a better understanding of the problem. It is a problem from a contest, so unlike when you’re doing research, you don’t have to worry about the possibility that the statement could be false. The assumption is that , , and are real square matrices, so the first problem is to decide if this is important. What if , , and are complex matrices? Or more generally: What if , , and are elements in a ring? (If you don’t know what a ring is, don’t worry. All I’m asking is: Is it possible to prove that statement, by only using algebraic rules like ?). It is easy to state the problem for elements in a ring, and it seems unlikely that it should be false for rings, given that it is true for real matrices, so let’s try to work on this conjecture:

Conjecture: Let , , and be elements of a ring , and suppose that is invertible. Now implies .

In other words, you shouldn’t think of the matrices as sets of real numbers arranged in arrays, but only of their algebraic properties. The problem is still a bit difficult to get your head around, so we’ll try to “turn off” some of the difficulties. The three most obvious difficulties are , and , so let’s see what happens if we let one of them be the identity. We get three new problems:

1. 
2. 
3. 

Proving one or more of these won’t solve the original problem, but it might give an idea of how to solve it. (You could also set two of the three matrices to be equal to , but the resulting statements are too trivial to be interesting). Let’s look at the first of the three statements:

That is, if then and commute. How can we prove that two elements in a ring commute? Well, if their product is the identity, we know that they are each others inverses, and therefore commute (Edit: This is not true in a general ring, but it is true for matrices. See my comment). Unfortunately the right hand side is , and if we assume the statement is trivial. So instead we assume to be invertible and multiply by . Remember that right now we are not trying to give a formal proof of anything, but only to get some ideas of what a proof might look like, so we are free to add this “niceness” –assumptions about . Assume also that . Now we get:

That is, is the inverse of , so they commute and we have:

We have now proved the statement in the case where and is invertible. Now it’s natural to try the same idea in the -case. Without any further assumptions we get:

As we wanted. The final case is equivalent to showing that if then and commute. We can’t just use the same trick as before, because we don’t know that and commute. But we have learned one important lesson from the two other cases: In order to show that two matrices commute, it is useful to find two matrices that are each other’s inverse, and use that they commute. So we add the identity on both sides and move everything else to the left hand side, and look for a factorization:

Now that we have solved the three simpler problems, we can look back at the original conjecture.

There are two ways you can use a proof of a simpler case to prove a more general theorem: The first is to use the fact that the simpler case is true. If we make the assumption that is invertible, this technique is actually useful. We get:

Where we use that with and as and . Now we have proved the statement under the assumption that is invertible, but if we don’t have this assumption, we have to do something else. (We could use a limit argument, like Gowers did in a comment to my last post, but I didn’t think of this trick when I solved the problem).

I mentioned that there are two ways of using a proof of a special case to prove a more general theorem, but I only gave one. The other is one to modify your proof to cover the more general theorem. So let’s look back at the proof that , and try to modify the proof to showing that . Now the proof almost writes itself:

QED.

IMC09 problem 2

For a couple of years I have thought about starting a mathematical blog, but I decided not to, because I thought I didn’t have enough time and ideas to keep a high enough post rate. But now and then I have something I want to say, and no place to say it, so I have finally decided to start this blog anyway, but also that I won’t have to post something every month.

This post and the next are partly inspired by these two posts by Gowers, where he tries to explore how people think when they do math, by asking his readers to solve a very simple equation, and explain how they solved it. In this and my next post I will consider a more difficult problem: It is problem 2 from IMC09 (IMC, International Mathematics Competition, is a math completion for university students). The reason I’m using an IMC-problem is that University of Copenhagen is going to participate in IMC for the first time this year, and I hope that talking about how we solve problems will be a good preparation for the contest both for me and for the rest of the team. Still, I hope that this discussion will be of interest to both IMO contestants and to professional mathematicians.

I solved this problem about two months ago, but I thought a lot about what problem solving strategies I used, so I still remember most of my thoughts. I have chosen to write about this particular problem because I noticed that I used many general problem solving strategies, that are good to know. You are welcome to post your thoughts on the problem in a comment, even if you haven’t solved the problem. If you have solved the problem, please try to describe the whole thought process, not just the thoughts that led you to the solution. I will post a description of how I solved it in a couple of days.

The problem is:
Let , , and be real square matrices of the same size, and suppose that is invertible. Prove that if then .