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)$.
IMO Shortlist 2011 N5
- Thanic Nur Samin
- Posts:176
- Joined:Sun Dec 01, 2013 11:02 am
Hammer with tact.
Because destroying everything mindlessly isn't cool enough.
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]
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.
Because destroying everything mindlessly isn't cool enough.
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
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.Zawadx wrote: *** Bwwaaahhh infinities
Hammer with tact.
Because destroying everything mindlessly isn't cool enough.
Because destroying everything mindlessly isn't cool enough.
- Atonu Roy Chowdhury
- Posts:64
- Joined:Fri Aug 05, 2016 7:57 pm
- Location:Chittagong, Bangladesh