求证：不存在函数 $f:\mathbb{N}\rightarrow \mathbb{N}$，此处 $\mathbb{N}=\{0,1,2,\cdots\}$，使得对所有 $ n\in\mathbb{N} $，都有 $ f(f(n))=n+1987$．（越南）
【难度】
【出处】
1987年第28届IMO试题
【标注】
【答案】
略
【解析】
证法一
用反证法．假设这样的函数 $f$ 存在．首先易知 $f$ 是单射．事实上，若 $f(n_1)=f(n_2)$，则 $f(f(n_1))=f(f(n_2))$，于是 $n_1+1987=n_2+1987$，故 $n_1=n-2$．
因 $f$ 是单射，所以 $f(0),f(1),f(2),\cdots,f(1986)$ 是 $1987$ 个互不相同的数．记 $M=\{f(0),f(1),\cdots,f(1986)\}$．
用 $f(n)$ 代题设中的 $n$，得 $f(f(f(n)))=f(n)+1987$
所以 $f(n+1987)=f(n)+1987$ ①
当 $n\geqslant 0$ 时，$f(n)\geqslant 0$．反复利用 ① 式，得
$f(n+1987k)=f(n)+1987k,k\in\mathbb{N}$．
故当 $n\geqslant k\cdot 1987$ 时，$f(n)\geqslant k\cdot 1987$．
对于 $n\in(0,1987]$，因为 $f(f(n))=n+1987<2\cdot 1987$，
所以 $f(n)<2\cdot 1987$．
记 $I_1=[0,1987),I_2=[1987,2\cdot 1987)$，则 $M \subset I_1\bigcup I_2$，设 $|M\bigcap I_1|=m_1,|M\bigcap I_2|=m_2$，则 $m_1+m_2=1987$．
任取 $f(a)\in M\bigcap I_1$，则必存在 $b,0\leqslant b<1987$，使得 $f(a)=b$．于是 $f(b)=f(f(a))=a+1987$，即 $f(b)\in M\bigcap I_2$．因为不同的 $f(a)$ 对应于不同的 $f(b)$，故 $m_1\leqslant m_2$．
用同样的方法可证得 $m_1\geqslant m_2$，所以 $m_1=m_2$．由此可得 $m_1+m_2=2m_1=1987$，矛盾．
证法二
假设存在这样的函数 $f$，则有 $f(n+1987)=f(f(f(n)))=f(n)+1987$．
反复利用上式可得 $f(n+1987m)=f(n)+1987m,m\in \mathbb{N}$．
记 $M=\{0,1,2,\cdots,1986\}$，设 $i,j\in M$，若 $f(i)\equiv j\pmod{1987}$，
则令 $j=f(i)+1987k$，于是
$\begin{aligned}
f(j)&=f(f(i)+1987k)\\
&=f(f(i))+1987k\\
&=i+1987(k+1)\\
&\equiv i\pmod{1987}
\end{aligned}$
因为 $M$ 的元素个数为奇数，所以存在 $n\in\mathbb{N}$，使得 $f(n)\equiv n\pmod{1987}$．
设 $f(n)=n+1987k,k\in\mathbb{Z}$．则
$\begin{aligned}
f(f(n))&=f(n+1987k)\\
&=f(n)+1987k\\
&=n+1987\cdot 2k\end{aligned}$
于是 $2k=1$，矛盾．
用反证法．假设这样的函数 $f$ 存在．首先易知 $f$ 是单射．事实上，若 $f(n_1)=f(n_2)$，则 $f(f(n_1))=f(f(n_2))$，于是 $n_1+1987=n_2+1987$，故 $n_1=n-2$．
因 $f$ 是单射，所以 $f(0),f(1),f(2),\cdots,f(1986)$ 是 $1987$ 个互不相同的数．记 $M=\{f(0),f(1),\cdots,f(1986)\}$．
用 $f(n)$ 代题设中的 $n$，得 $f(f(f(n)))=f(n)+1987$
所以 $f(n+1987)=f(n)+1987$ ①
当 $n\geqslant 0$ 时，$f(n)\geqslant 0$．反复利用 ① 式，得
$f(n+1987k)=f(n)+1987k,k\in\mathbb{N}$．
故当 $n\geqslant k\cdot 1987$ 时，$f(n)\geqslant k\cdot 1987$．
对于 $n\in(0,1987]$，因为 $f(f(n))=n+1987<2\cdot 1987$，
所以 $f(n)<2\cdot 1987$．
记 $I_1=[0,1987),I_2=[1987,2\cdot 1987)$，则 $M \subset I_1\bigcup I_2$，设 $|M\bigcap I_1|=m_1,|M\bigcap I_2|=m_2$，则 $m_1+m_2=1987$．
任取 $f(a)\in M\bigcap I_1$，则必存在 $b,0\leqslant b<1987$，使得 $f(a)=b$．于是 $f(b)=f(f(a))=a+1987$，即 $f(b)\in M\bigcap I_2$．因为不同的 $f(a)$ 对应于不同的 $f(b)$，故 $m_1\leqslant m_2$．
用同样的方法可证得 $m_1\geqslant m_2$，所以 $m_1=m_2$．由此可得 $m_1+m_2=2m_1=1987$，矛盾．
证法二
假设存在这样的函数 $f$，则有 $f(n+1987)=f(f(f(n)))=f(n)+1987$．
反复利用上式可得 $f(n+1987m)=f(n)+1987m,m\in \mathbb{N}$．
记 $M=\{0,1,2,\cdots,1986\}$，设 $i,j\in M$，若 $f(i)\equiv j\pmod{1987}$，
则令 $j=f(i)+1987k$，于是
$\begin{aligned}
f(j)&=f(f(i)+1987k)\\
&=f(f(i))+1987k\\
&=i+1987(k+1)\\
&\equiv i\pmod{1987}
\end{aligned}$
因为 $M$ 的元素个数为奇数，所以存在 $n\in\mathbb{N}$，使得 $f(n)\equiv n\pmod{1987}$．
设 $f(n)=n+1987k,k\in\mathbb{Z}$．则
$\begin{aligned}
f(f(n))&=f(n+1987k)\\
&=f(n)+1987k\\
&=n+1987\cdot 2k\end{aligned}$
于是 $2k=1$，矛盾．
答案
解析
备注
