Archive for July 2010

IMO 2010

July 23, 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

July 20, 2010

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 f_n:\mathbb{R}\to\mathbb{R} by f_1(x)=x^2-1 and f_n(x)=f_{n-1}(f_1(x)) for n\geq 2. Prove that f_n has n+1 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 2n points of a n\times n grid are marked. Show that for some k > 1 one can select 2k distinct marked points, say a_1,...,a_{2k}, such that a_{2i-1} and a_{2i} are in the same row, a_{2i} and a_{2i+1} are in the same column, \forall i, indices taken mod 2k.

We have 2n point and n rows and n columns, so on average there is 2 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 (n-1)\times (n-1) grid and at least 2(n-1) 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 n\times (n-1) grid with 2n-1 marked points, so this suggests that we should try to prove something stronger:

Stronger statement: Let n+m points of a n\times m grid be marked. Now for some k > 1 you can select 2k distinct marked points, a_1,...,a_{2k}, such that a_{2i-1} and a_{2i} are in the same row, a_{2i} and a_{2i+1} are in the same column, \forall i, indices taken mod 2k.

Proof: By induction on n and m. This is true if n=1 or if m=1 because you can’t choose m+1 points in a 1\times m 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 S be a set of \displaystyle { 2n \choose n } + 1 real numbers, where n is a positive integer. Prove that there exists a monotone sequence \{a_i\}_{1\leq i \leq n+2} \subset S such that
|x_{i+1} - x_1 | \geq 2 | x_i - x_1 | ,\text{for all } i=2,3,\ldots, n+1

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