## IMO Shortlist 2011 N5

For discussing Olympiad Level Number Theory problems
Thanic Nur Samin
Posts: 176
Joined: Sun Dec 01, 2013 11:02 am

### IMO Shortlist 2011 N5

Let $f$ be a function from the set of integers to the set of positive integers. Suppose that for
any two integers $m$ and $n$, the difference $f(m)-f(n)$ is divisible by $f(m-n)$. Prove that for
all integers $m, n$ with $f(m) \le f(n)$ the number $f(n)$ is divisible by $f(m)$.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Thanic Nur Samin
Posts: 176
Joined: Sun Dec 01, 2013 11:02 am

### Re: IMO Shortlist 2011 N5

If $f(m)=f(n)$ then $f(m)|f(n)$.

Now, assume that $f(m)<f(n)$. We consider $3$ cases.

Case $1$: $f(m-n)<f(m)$.

We know that, $f(m-n)|f(m)-f(n)$ and $f(m-(m-n))|f(m)-f(m-n)\Rightarrow f(n)|f(m)-f(m-n)$.

So, $f(m-n)\le |f(m)-f(n)|=f(n)-f(m)$.

$f(n)\le |f(m)-f(m-n)|=f(m)-f(m-n)$.

Adding them, $f(m-n)+f(n)\le f(n)-f(m-n)$, which isn't possible as the range of $f$ is positive integers.

Case $2$: $f(m-n)>f(m)$

Similar to the previous case,

We know that, $f(m-n)|f(m)-f(n)$ and $f(m-(m-n))|f(m)-f(m-n)\Rightarrow f(n)|f(m)-f(m-n)$.

So, $f(m-n)\le |f(m)-f(n)|=f(n)-f(m)$.

$f(n)\le |f(m)-f(m-n)|=f(m-n)-f(m)$.

Adding, $f(n)+f(m-n)\le f(n)+f(m-n)-2f(m)$ Which is again impossible as the range of $f$ is positive integers.

So, $f(m-n)=f(m)$.

However, $f(m-n)|f(m)-f(n)\Rightarrow f(m)|f(m)-f(n)\Rightarrow f(m)|f(n)$.

So, whenever $f(m)\le f(n)$, $f(m)|f(n)$. [Proved]
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Posts: 90
Joined: Fri Dec 28, 2012 8:35 pm

### Re: IMO Shortlist 2011 N5

My solution is a bit... lengthy:

Let $P(m,n)$ denote the statement that $f(m-n)|f(m)-f(n)$.

$P(m,0) \Rightarrow f(m)|f(0)$ for all $m$ (Lame Lemma 0)

$P(0,m) \Rightarrow f(-m)|f(0) - f(m) \Rightarrow f(-m)|f(m)$ for all $m \in \mathbb{Z}$ (Using Lame Lemma 0)

So, for fixed $m$, $f(-m)|f(m)$ and $f(m)|f(-m)$ and $f(m), f(-m) > 0$. Thus, $f(m)=f(-m)$. (Lame Lemma 1)

Serious Lemma 1:$f(m)|f(mn)$ for all $n \in \mathbb{N}$.
Proof: Now we shall prove this by induction. The base case is trivial. Assuming it holds for $n$,

$P(mn+m, mn) \Rightarrow f(m)|f(mn+m) - f(mn) \Rightarrow f(m)|f(mn+m)$

Then it holds for $n+1$. (Sub-QED)

Serious Lemma 2: Given $z|a \in \mathbb{N}, f(a) \neq f(z) \Rightarrow f(z-a) = f(z)$ and $f(z-a) \neq f(z) \rightarrow f(a) = f(z)$
Proof: By Serious Lemma 1, $f(z)|f(a)$ and $f(z)|f(z-a)$.
Let $f(a) = xf(z)$ and $f(z-a)=yf(z)$ for $x,y \in \mathbb{N}$
Now,
$P(z-a, z) \Rightarrow f(a)|f(z-a)-f(z) \Rightarrow y-1 = kx$ for $k \in \mathbb{N}_0$
$P(a, z) \Rightarrow f(z-a)|f(a) - f(z) \Rightarrow x-1= ly$ for $l \in \mathbb{N}_0$

Suppose $k, l > 0$ This would mean $x>y$ and $y>x$, a contradiction! So one o $k, l$ equals $0$. The lemma follows from this. (sub-QED)

Serious Lemma 3: If $n < k \Rightarrow f(n)=f(1) [n \in \mathbb{N}]$ for some maximal $k$, then $f(a) \neq f(1) \Leftrightarrow k|a$

Note that if $k$ exists to fulfill the condition, then $f(n)=f(1)$ for all $n$ and we are trivially done.

Now, $k|a \Rightarrow f(k)|f(a) \Rightarrow f(a) > f(1)$

Since $f(mk) \neq f(1)$, by Serious Lemma 2 we have $f(mk+1) = f(mk+2) = f(mk+3) = \dots = f(mk + k -1) = f(1)$ . Thus we are done (sub-QED).

Now we are ready to solve the problem. Suppose for $n>0$ maximal value*** is obtained $f(n)$ with minimal $n$ for some number $r$. Then all the other numbers with maximal value of $f(n)$ are multiples of $r$ (by Serious Lemma 1).

Now, since the only non-f(1) values of $f$ are multiples of $k$, we define a more interesting $f_1(n) = f(kn), n \in \mathbb{N}_0$. Then the process continues. So we can define $f_i$, and the corresponding $k_i$ and $r_i$. Note that as $i$ increases, $r_i$ decreases by factor of $k_{i-1}$. Eventually it must reach $1$, at which point the process terminates. At that point we conclude that $f(m) \leq f(n) \Rightarrow f(m)|f(n)$, since $f(m) \leq f(n)$ is only possible if they were last found in different levels of $f_i$, which means $m|n$.

*** Bwwaaahhh infinities

Thanic Nur Samin
Posts: 176
Joined: Sun Dec 01, 2013 11:02 am

### Re: IMO Shortlist 2011 N5

But $f(n)|f(0)$ and $f(0)>0$, doesn't that mean $f$ does achieve a maximal value? So your solution is correct I think.