In case you ever wondered what the most prestigious mathematical competition for high school students looks like, you get to solve 6 problems, in two sets of three problems. For each set, you get 4.5 hours of uninterrupted work, with all the scratch paper you might need, you bring your standard geometry drawing tools (ruler and compass) and you go.
For the list of problems, the IMO organization has a list of the official problems. Some are quite entertaining to do. This year, after being piqued a bit, I worked problem one in about half an hour to 45 minutes (I still got it). I used to compete in these types of competitions when I was in high school.
In any case, the problems are elementary: they just use algebra, trigonometry, basic plane geometry and elementary number theory. Here is problem one:
Let n be a positive integer and let
be distinct integers in the set {1, . . . , n} such that n divides 
If you ever have tried to design these problems, you will notice that the conditions are somewhat contrived. n appears in two places: both in the size of the original set, and in the division condition. Could one do without the first?
The answer is no. If all of the 
I struggled with the products of the products over the circle etc. Stirling formulae, comparisons of primes inside “n!.(n-1)!” and “n^n”, and so on. No clear result.
But one can do it without such stuff.
Spoilers follow (assuming that I was lucky: my IMO was back in 1992, in Moscow).
We’re told that “n” divides “a1.(a2-1)”. That means that “n” divides “a_1.a_l-a_1″ for “l=2″. By induction, I can actually prove the same thing for any “l = 2…k”. How? I already have the beginning of the induction.
The induction step is: we know that “n” divides “a_1.a_l-a_1″. But we are also told that “n” divides “a_l.a_{l+1}-a_{l}”. Now, these two numbers, “a_1.a_l-a_1″ and “a_l.a_{l+1}-a_{l}”, are pretty similar but “a_{l+1}” is missing in the former while “a_1″ is missing in the latter.
So I can extend them, by adding the missing factors. “n” actually also divides the numbers “(a_1.a_l-a_1) a_{l+1}” and “(a_l.a_{l+1}-a_{l}) a_1″ because they’re multiples of the previously mentioned multiples of “n”.
But that also implies that “n” divides their difference: in the difference, the “triple” term a_1.a_l.a_{l+1} cancels. So we know that “n” divides “a_1.a_l-a_1.a_{l+1}”. But by the induction assumption, “n” divides “a_1.a_l-a_1″, so by further subtraction, “n” also divides “a_1.a_{l+1}-a_1″, which is the induction step I wanted to prove (it could arguably have been done more directly).
From the induction performed up to “l+1=k”, we see that “n” also divides “a_1.a_k-a_1″. But the last condition we’re asked to prove impossible says that “n” divides “a_1.a_k-a_k”. If that were also true, “n” would also divide their difference, which is nothing else than “a_1-a_k”. But “n” can’t divide this difference because “a_1″ and “a_k” are different but differ by less than “n”.
QED.
I knew Lubos was the author of the first comment. I KNEW it!
There is another proof based on considering primes $p$ that divide $n$, I’ll just sketch it. p must divide $a_i$ or $a_{i+1} – 1, if it divides $a_i$ it does not divide $a_i – 1$ so it must divide $a_{i-1}$ and so on. If $n$ divides $a_k(a_1 – 1)$ you reach the conclusion that either $p$ divides all $a_i$ or $p$ divides all $a_i – 1$. Then you can see that any prime power that divides $n$ must also divide either all $a_i$ or all $a_i – 1$. From a result on simultaneous congruences you then conclude that all $a_i$ are congruent mod $n$
This method is not as clean as Luboš answer but it is more powerful if you want tighter limits on $k$ without assuming $n$ divides $a_k(a_1 – 1)$. for example if $n$ is prime then $k \leq 3$ with other limits on $k$ based on prime factorisation of $n$
If you want a tougher challenge try doing these problems in your head, it’s a great mental excercise.
My IMOs were 1978 and 1979. I could not quite keep up with a couple of exceptional team mates John Rickard and Richard Borcherds. Another character in our 78 team was Alan Dix who recounts some memories at http://www.hiraeth.com/alan/misc/IMO/imo.html
That’s a clever proof, the kind of a proof I wanted to find but I probably excessively strengthened the statement that should be proved…
Your proof was nice too Lubos. My own version of the solution was closer to PhilG’s. I used to like number theory and algebra problems a lot for these competitions and had a much harder time with geometry.
The problems seem to get harder each year. I have no idea how to even approach the grasshopper problem without using grad level analysis.
After spending the last 45 minutes or so trying to solve it, I give up and have to work.
Problem 6 in that Olympiad set is extremely hard and anyone looking for a challenge ought to try their hand at it.
The most obvious proof by induction approaches hits path ordering problems.
Hi Haelflix:
If I remember correctly, there were too many cookie-cutter examples that well trained students could do 100% of the time. Golds were only awarded for perfect scores a number of years, which is not really all that great for the competition.
Making the exam harder is more fair on the creativity side for good students that don’t have as much training, rather than unfair based on how much training an individual student has.
I completely agree with you, and not because of personal psychology. I’ve been always scared of easy exams and contests because they were the exams and contests where I was much more likely to get a relatively poor score by chance.
I have to admit, I dont understand the conditions. What does it mean to say that they are distinct integers in the set {1, . . . , n}??
I find that phrase totally obscure. does it mean that a_k=n and that all other number are smaller? it certainly doesnt say this.
where does lubos get the claim that a_1 and a_k differ by less than n? i dont see that in the conditions anywhere!
david says n is the size of the set. first, I dont see that in the condition, but even if I do: how does that guarantee anthing?
why is {9,6,3}, (i,e, a_1=9, a_2=6, a_3=3), not a counter example?????
Hi Eric:
Distinct means different. This is, a_1, not equal to a_2, no equal to a_3, etc. There are no repeats.
The setup is rigged so that you don’t have to say arithmetic modulo n, which is the natural setup for this problem, so instead they tell you to choose k different numbers from {1,…,n} which is the same thing.
The (9,6,3) would require that n>= 9, right? If you try it, you will see that 9 does not divide all the products that one needs.
Oh, OK OK OK.
when they said “be distinct integers in the set {1, . . . , n} ”
I though they meant ALL the integers in that set. So, it didnt occor to me that {1,…,n} meant what it usually means, i.e. {1,2,3,4,….,n}. because that would be downright weird. They mean, “FROM the set”. now i get it. OK. thanks!!!!!
I dont know why they didnt just say “distinct integers less than or equal to n”
that would be so much clearer.
“A grasshopper jumps along the real line…”
Please. A really good student would be bored to tears by this kind of crap. These competitions give young students a completely distorted idea of what doing mathematics or physics is really like. If I were running this thing, I would make the students sit down for 4 hours and tell them to come up with 6 genuinely interesting original *questions*. We all know that successful scientists are people who can ask good questions, not solve stupid pointless ones like these.
Find this year’s problems with their authors at http://www.googolplexideas.com
The results of various Science Olympiads ( Physics, Chemistry, Biology, Mathematics, APhO – Asian Physics Olympiad ) are given at
http://zookeepersblog.wordpress.com/results-2009-science-olympiads/
Chinese students are doing much better than Indian students. If you disagree then put a comment.
Thanks