Romanian Masters in Mathematics
Romanian Masters in Mathematics might become the most prestigious math competition for high school students. Romania invites teams from the 20 best countries from the previous year’s International Math Olympiad. This way they guarantee that all the competitors are extremely strong and they can give more difficult problems than the usual IMO problems.
This year they held their second competition and my son, Sergei Bernstein, was invited to join the USA team. Here is one of the problems:
For a finite set X of positive integers, define ∑(X) as the sum of arctan(1/x) for all elements x in X. Given a finite set S, such that ∑(S) < π/2, prove that there exists a finite set T such that S is a subset of T and ∑(T) = π/2.
The official solution involved a tedious greedy algorithm. My son, Sergei, got an extra point for his unique solution, which was very different from the official one. Here’s his solution:
To an integer x we associate a complex number x + i, which in polar coordinates is r(cosθ + i sinθ). Note that θ equals arctan(1/x). That means we can interpret ∑(X) as the angle in the polar form of ∏(x+i) — the product of (x+i) for all x in X.
We are given a set S with elements sj such that ∏(sj+i) has a positive real part, and we need to find other elements tk, such that ∏(sj+i) multiplied by ∏(tk+i) has real part 0.
But we know that the ∏(sj+i) = a + bi, for some integers a and b. I claim that we can always find a positive integer y, so that (a + bi)(y + i) has a smaller real part than a.
Note that ∑(S) < π/2, hence a and b are positive. By an ever so slightly modified version of the division algorithm we can find integers q and r such that b = aq + r, 0 < r ≤ a. Now simply set y equal to q + 1 (which is a positive integer). Then the real part of (a + bi)(y + i) equals ay – b = a – r, and is a non-negative number less than a.
Now we just repeat the process, which obviously has a finite number of steps.
My son’s solution wasn’t complete. The problem talked about sets of numbers and that implies that the numbers should be distinct. I leave it to my readers to finish this solution for distinct numbers.
Share:
Ashutosh Mehra:
That was a very nice and short solution.
Regarding the uniqueness of the generated y’s, I think it should be sufficient to invoke the identity:
arctan(1/y) = arctan(1/(y+1)) + arctan(1/(1+y(y+1))).
Since the given set S is finite, and since the algorithm described above generates only finitely many y’s, we could use this identity to “transform” the generated y’s to new values that are different from existing values in S and already generated values.
It is a pleasure reading your posts!
10 March 2009, 10:41 amesmeyny:
It is unfair to people from smaller countries to restrict a competition to the best countries and then tout it as the most prestigious one.
22 September 2009, 5:19 pmTanya Khovanova:
esmeyny,
I agree that it is unfair to students from non-top countries. Ironically, there are many very small countries at the top of IMO team resutls.
24 September 2009, 12:46 pm