5. Function f has range and domain belonging to the set of integers.
f(1 + n) > f(n)
f(n + f(m)) = f(n) + 1 + m

Find f(2001). .

For question 5: There are some routine procedure for functional equations. First, we establish the value for f(0) by letting m=n=0. We obtain f(f(0))=f(0)+1, since we have f(2)> f(1) > = f(0)+1, we must have f(0)=1.

From f(0)=1, we can see that f(1)=2, f(2)=3, ... so it is reasonable to conjecture f(k)=k+1 for all k. Indeed that is true by induction on m (keeping n=0).

Kerwin

PS. Out of interest, anyone has question 3? Nobody posted the question on this board yet, and the BMOC website does not have it when I last look at it about 10 minutes ago.

f(2)> f(1)> f(0)+1, we must have f(0)=1
how does this work?

Julians diagram seems to say the condition is PC=CD=DQ and P is the intersection of DA extended and CB extended. DA extended and AD extended are different (there is an implicit direction associated with the extension when we label a line by two points)

Kerwin

Im not quite sure why f(f(0))=1+f(0) forces f(0)> 0
if f(0)=-1, then what is wrong with f(-1)=0

Once you've got to f(0) = 1 you needn't induct on m - you can just set m = 0 and you get f(n + 1) = f(n) + 1 so you're done.

To answer George's question:

f(0) cannot be negative. f is strictly increasing and f(n + f(0)) = f(n) + 1. So if f(0) is negative n + f(0) < n hence f(n + f(0)) < f(n) so f(n) + 1 < f(n) which is impossible.

f(0) is an integer, say a. Then f(a)=1+f(0)> f(0). Our condition f(n+1)> f(n) forces a> 0. (It is an easy task to get a contradiction if a=0 or a < 0).

Michael's way is slightly quicker. I was thinking
f(k+1)=f(f(k))=f(0)+1+k=k+2.

Kerwin

Thank you, can you now explain in a similar way why if f(1)> =f(0)+1, so we have f(0) < =1.

If l > 0 then by induction on l, f(n+l) ³ f(n)+l for any n. Since f(0) > 0 we then get f(n+f(0)) ³ f(n)+f(0). But f(n+f(0))=f(n)+1 so f(n)+1 ³ f(n)+f(0) hence 1 ³ f(0) so f(0)=1, done.

Suppose f(0)> 1. Then we have f(f(0))> f(1) since f is strictly increasing. Further, we have f(1) > = f(0)+1. Hence we obtain f(f(0))> f(0)+1, contrary to our result f(f(0))=f(0)+1. So we must have f(0)< = 1.

Kerwin

Solution to question 5:

First, we have f(1)=n where n is an +ve integer.

So f(1+n)=f(1+f(1))=f(1)+1+1=n+2

However, the function f is ever increasing, so f(1+n)-f(1)> = n (f(1+n)-f(n)=n when f(1+x)-f(x)=1), i.e.every term is at least 1 greater than the previous term.

So f(1+n)-f(1)> = n => n+2-n³ n
and we get 2> = n

So n can only be 1 or 2.

Then if n=1,
f(1)=1
f(2)=f(1+1)=f(1+f(1))=f(1)+1+1=3
f(3)=f(2+f(1))=f(2)+1+1=5

Then prove the nth term is 2*n-1 by induction.
So f(2001)=2*2001-1=4001

If n=2,
f(1)=2
f(3)=f(1+2)=f(1+f(1))=2+1+1=4
There is only 1 interger between 2 and 4,
namely 3, and f is increasing, so f(2)=3

Then prove by induction that f(n)=n+1:
Let s(n) be f(m)=m+1 for all m< = n
s(2) is true.
Assume s(k) is true, then s(k+1):
f(k+1)=f(1+k)=f(1+f(k-1))=f(1)+k-1+1=k+2=(k+1)+1
Hense s(n) is true for all integer n.

So f(2001)=4001 (when n=1)
=2002 (when n=2)

By the way (again),

In Qn 5, does Z+ really mean non-negative integers or natural numbers? It does not make a difference to the solution but if f produces non-negative integers I have to consider f(1)=0, then f(1) also equals to f(1+0)=f(1+f(1))=0+1+1=2, so f can never produce 0.

I rank the level difficulty of the questions as :

Qn3(easiest) < Qn1 < Qn5 < Qn2 < Qn4(hardest, I mean there is no way to check your answer!)

For Qn 2 I was very lucky, I managed to find the angle indirectly by some random attempt on summing different angles. Then I spent half an hour trying to give a more natural proof, but I failed to do so :-(. Also, how detailed should the proof be, do I have to prove some obvious facts like the angles share the same arc are equal? (In which case I have no idea how)

Does anyone know when the papers are going to be marked and when we will get the result officially?

Ryan,

Can you clarify what q5 should be (as it is stated on the paper)? Is f a function from integers to integers, or positive integers to positive integers, or non-negative integers to non-negative integers? Julian quoted the question as integers to integers, in which case we cannot have f(1) equals to anything other than 2 (see earlier posts).

Your answer to question 3 is correct.

Kerwin

For Q5 I've just realised that the condition f(n+1) > f(n) is almost redundant. There are only two functions f: Z-> Z satisfying f(n + f(m)) = f(n) + m + 1. These are f(n) = n+1 and f(n) = -n-1. You then need the condition f(n+1) > f(n) to eliminate the second of these.

To prove that these are the only possibilities, note that f(n + f(0)) = f(n) + 1, and so for any integer x we have f(n + x f(0)) = f(n) + x. Setting x = 1 - f(0) and n = 0 we obtain:

f(n + (1 - f(0))f(0)) = f(n) + 1 - f(0)

Therefore n = 0 yields:

f((1 - f(0))f(0)) = 1

Now we have f(n + f(m)) = f(n) + m + 1. Set m = (1 - f(0))f(0) we get:

f(n + 1) = f(n) + 1 + f(0) - f(0)²

Therefore:

f(n) = f(0) + n*(1 + f(0) - f(0)² )

But f(f(0)) = f(0) + 1 so setting n = f(0):

f(0) + 1 = f(0) + f(0)(1 + f(0) - f(0)² )

And

1 = f(0)(1 + f(0) - f(0)² )

So f(0) divides into 1, and this implies that f(0) = 1 or f(0) = -1, so substituting this back into:

f(n) = f(0) + n*(1 + f(0) - f(0)² )

we get either f(n) = n+1 or f(n) = -n-1.

It is positive integers, to positive integers.

That's strange, since I think that makes the condition f(n + 1) > f(n) redundant...

If f: N-> N satisfies f(n + f(m)) = f(n) + m + 1 then clearly f is injective.

Now there exist distinct a,b between 1 and 3 such that f(a) = f(b) (mod 2). So WLOG f(a) = 2l + f(b) for some natural l .

Now f(n + f(1)) = f(n) + 2, so f(n + l f(1)) = f(n) + 2l . Setting n = b we get:

f(b + l f(1)) = f(b) + 2l = f(a)

Hence by injectivity b + l f(1) = a. But a,b between 1 and 3 so we must have f(1) = 1 or f(1) = 2.

f(1) = 1 leads to f(n+1) = f(n) + 2, i.e. f(n) = 2n - 1 for all natural n, which doesn't satisfy the equation.

Therefore f(1) = 2, and since then f(n+2) = f(n) + 2 we have f(2n-1) = 2n for all natural n.

Now f(n + f(m)) = f(n) + m + 1 so setting n = 1, we have f(1 + f(m)) = m + 3. Therefore f(1 + f(2n-1)) = 2n+2 = f(2n+1) so by injectivity we have 1 + f(2n-1) = 2n+1 for all natural n, so f(2n-1) = 2n.

Therefore f(n) = n+1 is the only solution for f: N-> N under the hypothesis f(n + f(m)) = f(n) + m + 1.

Er, whoops. The penultimate paragraph doesn't prove anything, since I'd already proved that f(2n-1) = 2n, what I wanted was f(2n) = 2n+1.

I think the conclusion still holds though. We have established:

f(1) = 2

So f(n + 2) = f(n) + 2. It follows by induction that:

f(n) = n + 1 (for odd n)
f(n) = n + f(2) - 2 (for even n)

Now f(n + f(m)) = f(n) + m + 1 so setting n = 1, m = 2 we have f(1 + f(2)) = f(1) + 2 + 1. It is obvious that f(2) is odd so f(2) + 1 is even therefore:

1 + f(2) + f(2) - 2 = f(1) + 2 + 1 = 5

Therefore 2f(2) = 6 and f(2) = 3, therefore for even n we get f(n) = n+3-2 = n+1. Therefore f(n) = n+1 for all natural n.

Of course showing f(n) = n+1 for even n is not directly relevant to the question, since we only need f(2001). It's still strange though that the question apparently includes redundant information.

Qn 5 actually says f(n) is from Z+ to Z+ where Z+ is the set of non-negative integers. This is a bit misleading as I think Z+ actually means the set of positive integers excluding 0.

OK, but that doesn't change anything significantly since 0 can't possibly be in f's range. (f(m) = 0 implies that f(n + 0) = f(n) + m + 1, i.e. m = -1 which is impossible as -1 is not in the domain of f). So essentially it is a function from Z+ to N, therefore the same reasoning as before must apply.

So what is the correct answer to Qn 5? Only f(2001)=2002? More importantly, does Z+ include 0?

I still think that Z+ means the set of +ve integers (i.e. natural numbers). 0 is not +ve so 0 is not in Z+, at least that is what I was taught in school.

It turns out that Z+ is not the set of non-negative integers, so 0 does not belong to Z+ after all. So is question 5 flawed? (it says that Z+ is the set of NON-NEGATIVE integers in the question)

I think the question actually means +ve integers since it asks for ALL POSSIBLE VALUES of f(2001). I understand that this does not mean anything on its own and it is perfectly possible that there is only one f(2001) but it does increase the probability that the question is flawed.

See the following web pages for the definition for integers and so on:

http://mathworld.wolfram.com/WholeNumber.html
http://mathworld.wolfram.com/Integer.html
http://mathworld.wolfram.com/Positive.html
http://mathworld.wolfram.com/Nonnegative.html
http://mathworld.wolfram.com/Zero.html
http://mathworld.wolfram.com/Negative.html

Yes, I thought that as well. Well I don't think it matters too much - f(2001) = 2002 is the correct answer either way - your solution above is fine. I still think f(n+1) > f(n) is redundant. Assuming f is from the non-negative integers to the non-negative integers and we have f(n + f(m)) = f(n) + m + 1 for all non-negative integers m, n then the only possibility is f(n) = n+1.

Proof:

Note that f must still be injective (that is f(x) = f(y) implies x = y, in other words f hits every number in its range at most once).

We know f(n + f(0)) = f(n) + 1, so f(n + lf(0)) = f(n) + l for all non-negative integers n, l . Therefore:

f(1 + l₁ f(0)) = f(1) + l₁

f(2 + l₂ f(0)) = f(2) + l₂

for all non-negative integers l₁, l₂.

It is obvious that we can choose non-negative l₁, l₂ to make the right hand sides equal. Then we get:

f(1 + l₁ f(0)) = f(2 + l₂ f(0))

By injectivity:

1 + l₁ f(0) = 2 + l₂ f(0)

And:

f(0)(l₁ - l₂ ) = 1

It is then easily seen that f(0) = 1. Therefore f(n+1) = f(n) + 1 and f(n) = n+1 as required, without using f(n+1) > f(n).

Could anyone check my solution to question 5, based on the FACT that 0 is not in Z+?

I don't think f(n+1) > f(n) is redundant, I used this to establish that f(1) < 3.

But you can prove this without using f(n+1) > f(n) - see my messages of 8:55 and 11:27 yesterday.

Your solution is fine, except f(2001) = 2002 is the only possibility. The two solutions you come up with are f(n) = 2n-1 and f(n) = n+1. Try substituting f(n) = 2n-1 into the equation f(n + f(m)) = f(n) + m + 1 and you'll find it doesn't work, so you can discount this solution, and the only answer is f(2001) = 2002.

Oops, I wish I had realised that earlier...

Thanks for your patience, Michael.

Just out of interest, is school maths really suffient for BMO1? What about BMO2?

The organisers would claim that you don't need special knowledge beyond school maths for BMO 1 and 2. In one sense this is true - none of the questions involve concepts beyond school level so arguably anyone sufficiently talented could solve all the problems with school level knowledge.

However this is a misleading way of looking at it. You could argue similarly that you don't need anything beyond school knowledge to solve Fermat's last theorem - provided of course you have the insight to rediscover most of 20th Century mathematics from first principles. In practice I think there are a lot of tricks, and well known techniques not taught at school, which you need to have a chance of doing well in Olympiads.

We have f(n + f(m)) = f(n) + m + 1. So by induction on l, f(n + lf(m)) = f(n) + l(m+1) for all positive integers l. Now set l = f(l) for some positive integer l. We get f(n + f(l)f(m)) = f(n) + f(l)(m+1) for all positive integers l, m, n. Since the left hand side is symmetric on l and m we must have f(l)(m+1) = f(m)(l+1), so setting l = 2 we obtain f(m) = r(m+1) where r = f(2)/2. Now f(1 + f(1)) = f(1) + 2, so f(1 + 2r) = 2r + 2, r(2r + 2) = 2r + 2, r² = 1, and r = 1 or -1. Therefore f(n) = n+1 or f(n) = -n-1 and the second solution clearly isn't allowed, so again f(n) = n+1 is the only possibility, without needing to use f(n+1) > f(n).

This sort of approach can also be used to show that the only solutions for f: Z+ \toZ satisfying f(n + f(m)) = f(n) + m + 1 (whenever m, n and n + f(m) are positive integers) are f(n) = n+1 and f(n) = -n-1.