Tuesday, September 13, 2011

Weird functions!

Here is another problem from IMO 2011, number 5 to be more precise:

Let ƒ be a function from the set of integers to the set of positive integers (Z+). Suppose that, for any two integers m and n, the diference ƒ(m)−ƒ(n) is divisible by ƒ(m−n), i.e. ƒ(m−n) | ƒ(m)−ƒ(n). Prove that, for all integers m and n with ƒ(m) ≤ ƒ(n), the number ƒ(n) is divisible by ƒ(m).

Weird indeed, but let's sort it out. We will consider that ƒ(m) < ƒ(n), because ƒ(m) = ƒ(n) case is straightforward. Let's prove some useful (and weird) properties of these functions first.

1. ƒ(m)=ƒ(m-0) | ƒ(m)-ƒ(0) ⇒ ƒ(m) | ƒ(0), for ∀m.

2. ƒ(-m)=ƒ(0-m) | ƒ(0)-ƒ(m). From (1) we know that ƒ(-m) | ƒ(0) which means:
- ƒ(-m) | ƒ(m) (*)
Similarly ƒ(m)=ƒ(0-(-m)) | ƒ(0)-ƒ(-m), which means:
- ƒ(m) | ƒ(-m) (**)
From (*), (**) and the fact that all the values returned by ƒ are positive ⇒ ƒ(-m) | ƒ(m) | ƒ(-m) ⇒ ƒ(-m)=ƒ(m), for ∀m.

3. From ƒ(n)>ƒ(m) (both are positive numbers) ⇒ ƒ(n)>ƒ(n)-ƒ(m)>ƒ(m)-ƒ(m)=0. But ƒ(n-m) | ƒ(n)-ƒ(m), which means, there ∃ an integer q≥1 so that q⋅ƒ(n-m)=ƒ(n)-ƒ(m) ⇒ ƒ(n)>ƒ(n)-ƒ(m)=q⋅ƒ(n-m)≥ƒ(n-m)>0.
From 0<ƒ(n-m)<ƒ(n) and 0<ƒ(m)<ƒ(n) results (from a≤b≤c≤d ⇒ |c-b|≤|d-a|):
- if ƒ(n-m)≤ƒ(m) ⇒ 0≤ƒ(m)-ƒ(n-m)<ƒ(n) or
- if ƒ(n-m)≥ƒ(m) ⇒ 0≤ƒ(n-m)-ƒ(m)<ƒ(n)
But both ƒ(m)-ƒ(n-m) and ƒ(n-m)-ƒ(m) are divisible by ƒ(n):
- ƒ(n)=ƒ(m-(m-n)) | ƒ(m)-ƒ(m-n)=(from 2)=ƒ(m)-ƒ(-(m-n))=ƒ(m)-ƒ(n-m)
- ƒ(n)=(from 2)=ƒ(-n)=ƒ((m-n)-m) | ƒ(m-n)-ƒ(m)=(from 2)=ƒ(-(m-n))-ƒ(m)=ƒ(n-m)-ƒ(m)
Or, saying it otherwise, ƒ(n) divides a positive number that is smaller than itself, which is possible only if the number is zero. In our case ƒ(n-m)-ƒ(m)=0 or ƒ(m)-ƒ(n-m)=0, which means ƒ(m)=ƒ(n-m).
As a result, if ƒ(n)>ƒ(m) ⇒ ƒ(m)=ƒ(n-m)

In the point 3 we stated that there ∃ an integer q≥1 so that q⋅ƒ(n-m)=ƒ(n)-ƒ(m), which is ⇔ q⋅ƒ(m)=ƒ(n)-ƒ(m) when ƒ(n)>ƒ(m) ⇔ ƒ(n)=(q+1)⋅ƒ(m) ⇔ ƒ(m) | ƒ(n)