A math problem …

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 f from \mathbb{N}^+ to \mathbb{N}^+ such that for all a and b, the numbers a, f(b) and f(b+f(a)-1) form the three sides of a non-degenerate triangle.

Here is the solution as described by Abhishek.

Take a = 1 and let f(1) = r. Then we know that for all b: 1, f(b), and f(b+r-1) form the sides of a non-degenerate triangle. In particular, this means that f(b) + 1 > f(b+r-1), i.e. f(b) \geq f(b+r-1) and f(b+r-1)+1 > f(b), i.e. f(b+r-1) \geq f(b). Thus \forall b: f(b) = f(b+r-1). But notice that this says that either r = 1 or f is a periodic function. But if f is a periodic function, it is bounded. But then we can choose a large enough (say more than twice the largest value that f can take) so that there is no b for which a, f(b), f(b+f(a) - 1) form a triangle. Thus, it has to be the case that r = 1.

Now we have determined that f(1) = 1. Let’s play around a little more to gain more information about f. We could try to set b = 1 and see what we can learn. Well, in that case f(b) = 1 and thus we conclude that for all a: 1, a, f(f(a)) form the sides of a nondegenerate triangle. Arguing as before, we see that for all a: a = f(f(a)). But this easily implies that f is a bijection from the positive integers to itself.

What more? Try a = 2. Let f(2) = r. We know that r > 1 since f(1) = 1 and f is a bijection. Let r-1 = d. Now we see that for all b: 2, f(b), f(b+d) form the sides of a nondegenerate triangle. But this means that for all b: f(b) - 1 \leq f(b+d) \leq f(b)+1. In particular, since f is a bijection (and d \neq 0), we know that for all b, either f(b+d) = f(b)-1 or f(b+d) = f(b)+1.

Now consider the value of f on 1, 1+d, 1+2d, \ldots. It is an easy proof by induction (using the fact that f is injective) that f(1+(i-1)d) = i. But this would mean that f is a bijection between \{1+(i-1)d \mid i \in \mathbb{N}^+\} and \mathbb{N}^+, and this can happen only if d = 1. And it follows that f is the identity!

Nice, wasn’t it?

Advertisements

4 comments

  1. Quite. It’s hard to tell from looking at a solution whether the problem was easy or not — any student can quite easily understand the solution to most good IMO problems, but coming up with them is another matter altogether.

    A side-effect of reading this post: I had been trying to solve Problem 3 on and off for about a week (while eating lunch, etc.), but thanks to Abhishek and Ashwin’s assurance that the problems were “actually very easy”, I managed to actually solve it today during a lecture I was even paying attention to. :-)

    1. Quite right about understanding versus coming up with the solutions. One of the students asked why one shouldn’t guess the answer and then try to prove – when you are trying to solve it in a computation, say. Srikantth too asked me the same. So is the problem ill-specified, as I have stated it (and I am just repeating what Abhishek said)? In fact, you just have to guess and show that the function satisfies the conditions given. There’s no need to prove anything.

      I just checked the IMO paper and it asks one to determine all f with these properties. That indeed makes a big difference!

      Inspired by you, let me try problem 3 as well!

      1. It’s perfectly fine to guess and prove — that’s an important part of the olympiad problem-solver’s strategy. :-) But I don’t think for this problem one would get many (any?) points for observing that the identity function is one function which satisfies the condition; the whole point is to prove that there are no other functions. (It could have been stated ‘Prove that f is the identity function’.)

        Usually, in these functional equations (as this genre of problems is called), one function (or family of functions) which satisfies the conditions is obvious, but it can be very hard to prove it is the only one — and often it can be untrue. For example, for the functional equation f:ℝ→ℝ, f(x+y)=f(x)+f(y), you can prove that f(x)=cx for some c for all rational x, but without further assumptions on f, linear functions are not the only ones on ℝ. In fact, the set of such functions has the same cardinality as the set of all functions from ℝ to ℝ!

  2. Some of these people are really good at what they do, and i think we should appreciate them to have followed what they’r heart wanted-pure mathematics and not fallen into the ‘engineering trap’ so common in India these days.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s