function (USAMO 2012, Balkan 2012, IMO proposal 2010)
- Phlembac Adib Hasan
- Posts:1016
- Joined:Tue Nov 22, 2011 7:49 pm
- Location:127.0.0.1
- Contact:
Find all functions $f:\mathbb{N}\to \mathbb{N}$ such that $f(n!) = f(n)!$ for all positive integers $n$ and $m-n$ divides $f(m) - f(n)$ for all distinct positive integers $m, n$.
- asif e elahi
- Posts:185
- Joined:Mon Aug 05, 2013 12:36 pm
- Location:Sylhet,Bangladesh
Re: function (USAMO 2012, Balkan 2012, IMO proposal 2010)
$f(1)=f(1!)=f(1)!$.So $f(1)=1$ or $2$. By Wilson's theorem,for a prime $p$ $(p-1)!\equiv -1\equiv p-1(mod p)$ or $(p-2)!\equiv 1(mod p)$.
So $p\mid (p-2)!-1\mid f((p-2)!)-f(1)=f(p-2)!-(1 or 2)$.So $gcd(p,f(p-2)!)=1$. This implies $f(p-2)\leq p-1$.Again $(p-2)!-1\mid f(p-2)!-f(1)$. So $f(p-2)!=(p-2)!$ or $f(p-2)=p-2$ and $f(1)=1$. Again $(p-2)-n!\mid f(p-2)-f(n)!$ or $(p-2)-n!\mid (p-2)-f(n)!-(p-2)+n!=n!-f(n)!$ for all prime p.But for p large enough $p-2-n!> n!-f(n)!$ so doesn't divide $n!-f(n)!$. So $n!-f(n)!$ must be equal to zero. So $n!=f(n)!$ or $n=f(n)$ for all n.
So $p\mid (p-2)!-1\mid f((p-2)!)-f(1)=f(p-2)!-(1 or 2)$.So $gcd(p,f(p-2)!)=1$. This implies $f(p-2)\leq p-1$.Again $(p-2)!-1\mid f(p-2)!-f(1)$. So $f(p-2)!=(p-2)!$ or $f(p-2)=p-2$ and $f(1)=1$. Again $(p-2)-n!\mid f(p-2)-f(n)!$ or $(p-2)-n!\mid (p-2)-f(n)!-(p-2)+n!=n!-f(n)!$ for all prime p.But for p large enough $p-2-n!> n!-f(n)!$ so doesn't divide $n!-f(n)!$. So $n!-f(n)!$ must be equal to zero. So $n!=f(n)!$ or $n=f(n)$ for all n.
Re: function (USAMO 2012, Balkan 2012, IMO proposal 2010)
@asif e elahi
You have left out the solutions: $f(n)\equiv 1 \forall n\in \mathbb{N}, f(n)\equiv 2 \forall n\in \mathbb{N}$.
And I can't understand how you deduced $f(p-2)=p-2$. Could you please make it clear?
You have left out the solutions: $f(n)\equiv 1 \forall n\in \mathbb{N}, f(n)\equiv 2 \forall n\in \mathbb{N}$.
And I can't understand how you deduced $f(p-2)=p-2$. Could you please make it clear?
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$
- asif e elahi
- Posts:185
- Joined:Mon Aug 05, 2013 12:36 pm
- Location:Sylhet,Bangladesh
Re: function (USAMO 2012, Balkan 2012, IMO proposal 2010)
By Wilson's theorem $p\mid (p-2)!-1\mid f(p-2)!-f(1)$. If $f(p-2)>p-1$ then $p\mid f(1)$. So $f(p-2)\leq p-1$.AgainSANZEED wrote:@asif e elahi
You have left out the solutions: $f(n)\equiv 1 \forall n\in \mathbb{N}, f(n)\equiv 2 \forall n\in \mathbb{N}$.
And I can't understand how you deduced $f(p-2)=p-2$. Could you please make it clear?
$(p-2)!-1\leq f(p-2)!-f(1)\leq(p-2)!-1$. So $f(p-2)=p-2.$