Yesterday, I had a chance to sit through a problem solving session where Abhishek Dang and Ashwin Deopurkar (final year BScM students at CMI) solved some 2009 IMO problems for the benefit of some school students. According to them, the problems were “actually very easy”. In fact, I was surprised to find that I was able to understand the solutions quite well, but that’s more a testament to their impressive skill in exposition than anything else.
Anyway, here is a nice problem. I am writing this (without permission from either of them!) so that I can refer back to it when I want to, and since otherwise I will forget it completely! It will stay here as long as there is a take-down notice from Abhishek! :-) At which point, Shreevatsa will teach me how to make this post private, I am sure!
Determine all functions from to such that for all and , the numbers and form the three sides of a non-degenerate triangle.
Here is the solution as described by Abhishek.
Take and let . Then we know that for all , and form the sides of a non-degenerate triangle. In particular, this means that , i.e. and , i.e. . Thus . But notice that this says that either or is a periodic function. But if is a periodic function, it is bounded. But then we can choose large enough (say more than twice the largest value that can take) so that there is no for which form a triangle. Thus, it has to be the case that .
Now we have determined that . Let’s play around a little more to gain more information about We could try to set and see what we can learn. Well, in that case and thus we conclude that for all form the sides of a nondegenerate triangle. Arguing as before, we see that for all . But this easily implies that is a bijection from the positive integers to itself.
What more? Try . Let . We know that since and is a bijection. Let . Now we see that for all form the sides of a nondegenerate triangle. But this means that for all . In particular, since is a bijection (and ), we know that for all , either or .
Now consider the value of on . It is an easy proof by induction (using the fact that is injective) that . But this would mean that is a bijection between and , and this can happen only if . And it follows that is the identity!
Nice, wasn’t it?