14
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You are given that $f : \mathbb{Z} \to \mathbb{N}$ is a function such that for any two integers $m$ and $n$, $$\frac{f(m)−f(n)}{f(m−n)} \in \mathbb{Z}\tag{1}$$ What does this imply about $f(0)$? About $f(1)$? About $f(2)$? About the relationship between $f(k)$ and $f(-k)$? Are there any functions $f: \mathbb{Z} \to \mathbb{N}$ that satisfy $(1)$ that are not constant? $\endgroup$ – Zubin Mukerjee Oct 13 '18 at 17:24
  • $\begingroup$ @Zubin Mukerjee There is not a problem in the question. But, maybe there is a problem in my solution. $\endgroup$ – lone student Oct 13 '18 at 17:33
4
+50
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.