IMO 2011: Prove that, for all integers $m$ and $n$ with $f(m)<f(n)$, the number $f(n)$ is divisible by $f(m)$

Question

Problem: 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$ and $n$ with $f(m)<f(n)$, the number $f(n)$ is divisible by $f(m).$ (Resource: IMO $2011$)

My method:

$$\frac {f(m)-f(n)}{f(m-n)}\in\mathbb{Z}$$

If $f(m)=f(n)$ , $\frac{f(n)}{f(m)}=1\in \mathbb {Z^{+}}$

I can accept $f(n)>f(m)$.

It is obvious, $f(n)-f(m)≥f(m-n)$

$$ \begin{cases} m \mapsto m & \\ n \mapsto m-n& \end{cases} \Rightarrow \begin{cases} f(m) \mapsto f(m) & \\ f(n) \mapsto f(m-n) & \end{cases} $$

Now, I will prove that $f(m-n)=f(m)$ must be.

It is obvious $$\frac {f(m)-f(n)}{f(m-n)}\in\mathbb{Z} \Rightarrow \frac {f(m)-f(m-n)}{f(n)}\in\mathbb{Z}$$

If $f(m)≠f(m-n)$, we can write $\mid f(m)-f(m-n) \mid ≥f(n)$. Considering $f(m)>0 , f(m-n)>0$ and $f(n)>f(m)$ we get $f(m-n)>f(m)$ must be.

Case $1.$

$$f(m-n)-f(m)≥f(n) $$

Case $2.$

$$f(m)=f(m-n)$$

Let $n=0$, for Case $1$, we can write $f(n)≤f(m-n)-f(m) \Rightarrow f(0)≤0$ But, this is a contradiction. Because, $E(f)>0$. So, we get, if $f(n)>f(m)$ then $f(m)=f(m-n)$ must be.

Finally,

$$\frac {f(m)-f(n)}{f(m-n)}\in\mathbb{Z} \Rightarrow \frac {f(m)-f(n)}{f(m)}\in\mathbb{Z} \Rightarrow \frac {f(n)}{f(m)} \in \mathbb{Z^{+}} $$ Q.E.D.

Can You verify my solution? Because, I'm not so sure. I don't have a teacher to approve the solution.

Answer 1

Your proof looks correct to me.

Now, I will prove that $f(m-n)≥f(m)$ must be.

I think that you have a typo here. It should be $f(m-n)=f(m)$.

It is obvious $$\frac {f(m)-f(n)}{f(m-n)}\in\mathbb{Z} \Rightarrow \frac {f(m)-f(m-n)}{f(n)}\in\mathbb{Z}$$

Yes, $f(m)-f(m-n)$ is divisible by $f(m-(m-n))=f(n)$.

If $f(m)≠f(m-n)$, we can write $\mid f(m)-f(m-n) \mid ≥f(n)$. Considering $f(m)>0$ and $f(m-n)>0$, we get $f(m-n)>f(m)$ must be. Because, $f(n)>f(m).$

Case $1.$

$$f(m-n)-f(m)≥f(n) $$

Case $2.$

$$f(m)=f(m-n)$$ Let $n=0$, for Case $1$, we can write $f(n)≤f(m-n)-f(m) \Rightarrow f(0)≤0$ But, this is a contradiction. Because, $E(f)>0$. So, case $1$ is impossible.

I think there is no need to separate it into cases as follows :

"Suppose that $f(m)\not =f(m-n)$. Then, we can write $\mid f(m)-f(m-n) \mid \ge f(n)$. Considering $f(m)>0$ and $f(m-n)>0$, we get $f(m-n)>f(m)$ because $f(n)>f(m).$ It follows that $f(m-n)-f(m)\ge f(n)$. Let $n=0$. Then, we can write $f(n)≤f(m-n)-f(m) \implies f(0)≤0$ which contradicts $f(0)\gt 0$. So, we have $f(m)=f(m-n)$."

---

Another way to prove $f(m-n)=f(m)$.

We have $$-f(n)\lt f(m)-f(n)\le -f(m-n)\lt 0$$ from which $$0\lt f(m-n)\lt f(n)$$ follows.

From $$f(m)-f(m-n)\lt f(m)+f(m-n)\le f(n)$$ and $$f(m-n)\lt f(n)\lt f(n)+f(m)\implies -f(n)\lt f(m)-f(m-n)$$ we get $$-f(n)\lt f(m)-f(m-n)\lt f(n)$$

Since $f(m)-f(m-n)$ is divisible by $f(m-(m-n))=f(n)$, we get $f(m)-f(m-n)=0$.