IMO Shortlist 2011 N5

For discussing Olympiad Level Number Theory problems
User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am
IMO Shortlist 2011 N5

Unread post by Thanic Nur Samin » Mon Feb 20, 2017 6:30 pm

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.

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

Re: IMO Shortlist 2011 N5

Unread post by Thanic Nur Samin » Mon Feb 20, 2017 6:45 pm

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.

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

Re: IMO Shortlist 2011 N5

Unread post by Zawadx » Wed Feb 22, 2017 12:03 am

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

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

Re: IMO Shortlist 2011 N5

Unread post by Thanic Nur Samin » Wed Apr 26, 2017 7:39 pm

Zawadx wrote: *** Bwwaaahhh infinities
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.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

User avatar
Atonu Roy Chowdhury
Posts:64
Joined:Fri Aug 05, 2016 7:57 pm
Location:Chittagong, Bangladesh

Re: IMO Shortlist 2011 N5

Unread post by Atonu Roy Chowdhury » Mon May 01, 2017 9:45 pm

$f(m-n)|f(m)-f(n)$
$n=0$ implies $f(m)|f(0)$
$m=0$ and $n=m$ implies $f(-m)|f(m)$ . Similarly we get $f(m)|f(-m)$ . So, $f(m)=f(-m)$
$n=-n$ implies $f(m+n)|f(m)-f(n)$ from which we get $ f(m+n) \le f(n)-f(m)$
Again, $m=m+n$ and $n=m$ implies $f(n)|f(m+n)-f(m)$ .

Assume $f(m) \neq f(m+n)$ . Here we've 2 cases.

Case 1: $f(m+n)-f(m) > 0$
This ineq along with the previous one implies $f(m+n)-f(m) \ge f(n) \ge f(m+n)+f(m)$ which gives $2f(m) \le 0$ . A contradiction!

Case 2: $f(m+n)-f(m) < 0$ . This ineq along with $f(n) \ge f(m)$ implies $f(m)-f(m+n) \ge f(n) \ge f(m)$ . Another contradiction!

So, $f(m) = f(m+n)$ . Substituting $m=m+n$ , we get $f(m)|f(m+n) - f(n)$ . Done!
This was freedom. Losing all hope was freedom.

Post Reply