IMO Shortlist 2012 problem A6
Dodao/la:
arhiva3. studenoga 2013. Let
![f: \mathbb{N} \rightarrow \mathbb{N}](/media/m/c/3/e/c3e922e496d1f497166720b9e7f9b257.png)
be a function, and let
![f^m](/media/m/3/e/4/3e469411dd41878c95088ab99c741b33.png)
be
![f](/media/m/9/9/8/99891073047c7d6941fc8c6a39a75cf2.png)
applied
![m](/media/m/1/3/6/1361d4850444c055a8a322281f279b39.png)
times. Suppose that for every
![n \in \mathbb{N}](/media/m/2/b/a/2ba27c6141ca415bb86bae1d237f1fac.png)
there exists a
![k \in \mathbb{N}](/media/m/3/7/4/3740df5f7c5224aee0c08404b0d63c46.png)
such that
![f^{2k}(n)=n+k](/media/m/1/e/9/1e90ae6d21bb753e6479334b125aa5be.png)
, and let
![k_n](/media/m/c/6/b/c6bcd1faa47798feadc34f5f61555163.png)
be the smallest such
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
. Prove that the sequence
![k_1,k_2,\ldots](/media/m/4/6/9/469d540f0e47eb8fe57e4362f0390190.png)
is unbounded.
%V0
Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function, and let $f^m$ be $f$ applied $m$ times. Suppose that for every $n \in \mathbb{N}$ there exists a $k \in \mathbb{N}$ such that $f^{2k}(n)=n+k$, and let $k_n$ be the smallest such $k$. Prove that the sequence $k_1,k_2,\ldots$ is unbounded.
Izvor: Međunarodna matematička olimpijada, shortlist 2012