Suppose $k_1,k_2,\ldots$ is bounded above by $M$. The key is that for fixed $n$, $f^k(n)$ grows too slowly as a function in $k$ to be injective (since $\{f^k(n)\}$ is unbounded, we cannot have $f^i(n) = f^j(n)$ for $i\ne j$). For $t\in\mathbb{R}$, define $S_t = \{k: f^k(n) - \frac{k}{2} = t\}$, so for each $k\in S_t$, there exists $\ell\in[1,M]$ such that $f^{k+2\ell}(n) - \frac{k+2\ell}{2} = f^k(n) - \frac{k}{2}$. Thus $S_t$ has (lower) density at least $\frac{1}{2M}$, and since the $S_t$ are pairwise disjoint, we can find $t_1,t_2,\ldots,t_{2M}$ such that $S_{t_1},\ldots,S_{t_{2M}}$ partition $\mathbb{N}$. But then $f^k(1) - \frac{k}{2} = O(1)$, contradicting the injectivity of $f^k(1)$.

See here for a harder (and open) version of the problem.

Assume a contradiction, so $k_i=O(1)$. Let $a_1=1$, and define $a_{r+1}=f(a_r)$. Note if for any $m<n$ we have $a_m=a_n$ then the sequence is eventually periodic and $a_i=O(1)$, contradicting that $\sup_{m>0, k>0}a_{m+2k}-a_m=\infty$. We say a term of the sequence $a_m$ is cured by $a_{m+2k}$ iff $k$ is minimal for the desired property $a_{m+2k}=a_m+k$ to hold. Note that any term of the sequence cures at most one term. Why? Because if it cures two earlier terms $a_r$ and $a_s$ where $r<s$, clearly $a_s$ actually cures $a_r$ but this contradicts the minimality assumption in the definition of cure. Let $f(s)$ be the number of uncured terms among $a_1, \cdots, a_s$. Note $f(s)$ is monotonically increasing. Furthermore, the earliest uncured term $a_m$ must be cured by some $a_{m+2k}$ with $m+2k>s$ and $k=O(1)$. Clearly $f(s) \le s-m+1$. But then $k>\frac{s-m}{2} \ge \frac{f(s)-1}{2}$ so $f(s) \le 2k+1=O(1)$. Thus, $f(s)$ is eventually constant, when $s \ge s_0$. Clearly, $a_j \le \frac{j}{2}+C$ for $j \le s_0$ and some large $C>9000$ as $s_0$ is a constant. But now, for any $s>s_0$, $a_1, \cdots, a_{s-1}$ and $a_1, \cdots, a_{s-1}, a_s$ have the same number of uncured terms, so $a_s$ cures some term $a_m$, and thus for some $m \le s$ and some $k$ we have $a_s=a_{m+2k}=a_m+k \le \frac{m}{2}+C+k=\frac{m+2k}{2}+C=\frac{s}{2}+C$. Hence by induction $a_s \le \frac{s}{2}+C$ for all natural $s$. But then for $N=4C$, $a_1, \cdots, a_N$ are $4C$ natural numbers which are all bounded by $\frac{N}{2}+C=3C$, so two of them are equal, a contradiction.

This is roughly equivalent to math154's solution, but anyways... Assume on the contrary that $M$ is an upper bound. Define $x_n = f^{2n-1}(1) - n$ and $y_n = f^{2n}(1) - n$. Observe that the condition now implies that for each $n$ there exists a $k \le M$ such that $x_{n+k} = x_n$. Similarly, there is a (probably different) $k \le M$ such that $y_{n+k} = y_n$. Observe that means that $(x_n)$ and $(y_n)$ can only contain finitely many different values; in particular they are bounded by some $X$ and $Y$. Now $\left\{ x_n+n \mid n=1,2,\dots,m \right\} \cup \left\{ y_n+n \mid n=1,2,\dots,m \right\}$ contains $2m$ distinct values for every $m$, due to injectivity of $f^n(1)$ in $n$. In particular the maximal element in this set must be at least $2m$. But for any $m > \max \{X,Y\}$, the maximal possible element is $\max\{X,Y\}+m < 2m$.

Would this work?

The assertion about $f^{2 \cdot \text{lcm}(\ldots)}$ isn't true because the $k$ can be different for each $n$.

Assume that that sequence is bounded, by the number $M$. By assuming $M=1$ one can easily complete the proof, and by assuming $M=2$ one can easily generate "sequences", which essentially partition $\mathbb{N}$, rearrange the pieces, and result in 2$\mathbb{N}$. From this, finding the proof for any $M$ is not hard. Then, for every $n$ there exists a $1 \le k \le M$ such that $f^{2k}(n)=n+k$. Now, consider the numbers $e_0, e_1, ...$ where $e_i = f^{2i}(1)$ and $e_0=1$. And consider the numbers $d_0, d_1, ...$ where $d_i=f^{2i+1}(1)$. Say $E=\{e_0, e_1, ...\}$ and define $D$ similarly. Clearly, $E \cap D$ is empty. Now, focus on $E$. For any positive integer $k$, we define $g(k)$ to be the smallest number such that $e_{k+g(k)}=e_k+g(k)$, and we know $g(k) < M$. We define a "pre-sequence" of numbers $a_1$, $a_2$, ..., to be such that $a_i+g(a_i)=a_{i+1}$ for all $i$. Now, we define a "sequence" of numbers $b_1$, $b_2$, ..., to be such that, for any $i$ and $j$, the two pre-sequences generated by $a_1=b_i$ (we will call this pre-sequence $A$) and $a_1=b_j$ (we will call this pre-sequence $a$) eventually "synchronize" (that is, there is some number $N$ and an integer constant $C$ such that for any $p>N$, $A_p=a_{p+C}$). It is easy to see that in a sequence $b_1$, $b_2$..., we have $b_i=i-1+b_1$ for any $i$. Now, we will partition $\mathbb{N}$ into different and disjoint infinite sequences. We don't know how many sequences result (yet), possibly infinite sequences are needed. But I will show that at most $M$ sequences are needed. Indeed, assume we have different, disjoint, "primitive" (that is, their initial value is the least initial value possible) sequences $B_1$, ..., $B_{M+1}$, and "order" them by their initial value, so that the initial value of $B_1$ is less than the initial value of $B_2$ that is less than the initial value of $B_3$, and so on. Now, take $b$ the initial value of $B_{M+1}$. Clearly $b \ge M+1$. Now, define $X$ to be the set of the $M-1$ consecutive integers $b-1$, ..., $b-M+1$. Clearly, there exists $1 \le q \le M$ such that $B_q$ has no elements in $X$. So take $b'$ the largest element of $B_q$ that is less than $b$. We know $b \ge b'+g(b') \in B_q$. And so $B_q$ either has an element in $X$, or $b$ is an element of $B_q$, or $g(b')=0$. All of these are impossible. Therefore, we can partition $\mathbb{N}$ into $U$ sequences, $E_1$, ..., $E_U$. Where $U \le M$. Similarly, we can partition $\mathbb{N}$ into $V$ sequences, $D_1$, ..., $D_V$. Where $U \le M$. And these $U+V$ sequences are disjoint. Define $F_i$ by substituting $j \in E_i$ by $e_j \in F_i$, and redefine $C_i$ by substituting $j \in D_i$ by $d_j \in C_i$. We know that $\mathbb{N}=E_1 \cup ... \cup E_U = D_1 \cup ... \cup D_V$ are partitions, and that there exists a set $Y$ such that $\mathbb{N}=F_1 \cup ... \cup F_U \cup C_1 \cup ... \cup C_V \cup Y$ is also a partition (namely, $Y$ is the set of numbers not expressible as $f^g(1)$ for a non-negative $g$). We know that the difference between two consecutive numbers in any of those $2(U+V)$ sets is at most $M$, and we know that $F_i$ is a "shifted" version of $E_i$ (add a constant, say $F_i=E_i+\mathbb{E}_i$, where $\mathbb{E}_i$ is a constant), and $C_i$ is a "shifted" version of $D_i$ ($C_i=D_i+\mathbb{D}_i$). Take any interval $Z$ with a sufficiently big length, such that the first integer in $Z$ is greater than the initial values of $F_1$, ..., $F_U$, $C_1$, ..., $C_V$. Call $Z'$ the interval that results by removing the last $\Omega = max\{ \mathbb{E}_1, ...,\mathbb{E}_U, \mathbb{D}_1, ..., \mathbb{D}_V \}$ integers from $Z$. We know $|F_i \cap Z| \ge |E_i \cap Z'|$ and $|C_i \cap Z| \ge |D_i \cap Z'|$. Therefore $|Z| = \sum_{i=1}^U |F_i \cap Z| + \sum_{i=1}^V |C_i \cap Z| \ge \sum_{i=1}^U |E_i \cap Z'| + \sum_{i=1}^V |D_i \cap Z'| = 2|Z'|$. So, $|Z| \ge 2(|Z|-\Omega) \Rightarrow 2 \Omega \ge |Z|$. But $\Omega$ is fixed. So by choosing a big enough $Z$, we can reach a contradiction. We are done.

Def: For a function $ h: \mathbb{N} \rightarrow\mathbb{N}$ call the graph of this function the oriented graph $G(V,E)$ where $V=\mathbb{N}$ and we have an oriented edge $ \rightarrow$ between $ a$ and $b$ if $h(a)=b$. For a set $S$ denote $D(S)= \liminf \frac{ (1,.....n \bigcap S)}{n}$ It is easy to notice that $D$ is additive on disjoint sets. Solution: Let $g(x)=f^{(2)}(x)$. The condition of the problem tells us that the graph of this function is the union of $l$ disjoint trees where $l\ge2$. (it is easy to notice that there are no cycles and we can't have just one tree). Assume by contradiction that the sequence is bounded by $M$. So there exists a maximal $m$, such the $g^{m}(x)=x+m$ for an infinity of x, where m is the minimal number such that $g^{m}(x)=x+m$. We can't have more than $m$ trees because if a tree $T$ contains big enough $x$ it will contain $x+n$ where $n \le m$ furthermore $D(T)\ge \frac{1}{m}$. Consider an arbitrary $x$ in a tree $T$, and lets look at the orbit of $x= \{ x,f(x), f(f(x))... \} $. We are going to color this orbit. Color by $C_1$ the set $f^{(l)}(x)$ where $f^{(l)}(x)=x+l$, after, pick the first uncolored number in this sequence call it $f^{(j_2)}(x)$ then color by $C_2$ the elements $f^{(u+j_2)}(x)=f^{(j_2)}(x) +u$ and continue so on. We can't have an element colored by two colors since otherwise $f^{(z)}(x)= f^{(j_p)}(x) +u_p= f^{(j_l)}(x)+ u_l$ where $j_p+u_p=j_l+u_l=z$ so one of $f^{(j_p)}(x)$ and $f^{(j_l)}(x)$ has been colored by the other, contradiction. We have by simmilar reasons that $D(C_i)\ge \frac{1}{m}$ so we have a finitie number of colors. in conclusion $f^{(q)}(x)=f^{(j_i+u)}(x)=f^{(j_i)}(x)+u< q+ N$, where N is big enought constant, valid for all colors. So $D(orb(x))=1$ contradiction since we have two trees hence at least two different orbits.

Thanks MellowMelon for pointing out the giant hole

Wolstenholme: see posts #7 and #8. That LCM assertion isn't true.

Lemma 1: For any positive integers $n,k$, the equality $f^k (n)=n$ never holds. Proof: Suppose this were the case and consider the minimal possible value of $k$. Consider $x = \text{max} \{ n, f(n), f^2 (n), ... f^{k-1} (n)\}$, and note that $f^{2k_x} (x) =x+k_x \in \{ x, f(x), f^2 (x), ... f^{k-1} (x)\}$, which is a clear contradiction as $x$ is maximal. Let $g(x)=f(f(x))$ and suppose $f(a)=b$ for some $a,b$. We'll consider the two sequences $\{ a, g(a), g^2 (a), ... \}, \{ b, g(b), g^2 (b), ... \}$, which both never repeat by lemma 1. For convenience, let $h(n) = n+k_n$ for each $n$. Lemma 2: $h(g^i (a)) \neq h(g^j (a))$ for any $i\neq j$. Proof: Suppose otherwise, so that both expressions equal $g^k (a)$ for some $k$, and WLOG $i>j$. Suppose $u=g^i (a), v=g^j (a)$ so that $k_u = k-i, k_v = k-j$. Then $h(g^i (a)) = h(g^j (b))$ yields that $u+(k-i) = v + (k-j) \implies u = v + (i-j)$, so that $f^{2(i-j)} (v) = v + (i-j)$. Then $i-j < k_v = k-j$, contardicting the minimality of $k_v$. Now suppose the sequence $\{k_i\}$ is bounded by a value $N$. We partition $\{ a, g(a), g^2 (a), ...\}$ into chains of the form $S_{a_i} = \{ a_i, h(a_i), h^2 (a_i), ...\}$ via a greedy algorithm: at each step, take the smallest number in $\{a, g(a), g^2 (a), ...\}$ which is not yet part of a chain and construct a chain with it. Lemma 3: There are at most $N$ such chains $S_{a_i}$ Proof: First of all, it's clear that each chain can be extended to have infinite length. Suppose there are more than $N$ chains, and take $N+1$ chains $S_{a_1}, S_{a_2}, ... S_{a_{N+1}}$. Choose some integer $m> \text{max} (a_1,a_2,...a_{N+1})$. Since $h(c)-c =k_c\le N$ for any $c$, no chain can "jump" by more than $N$, implying that each chain must contain an element of the set $\{m+1,m+2,...m+N\}$. But there are $N+1$ chains and only $N$ possible elements, so some two chains are not disjoint, a contradiction with lemma 2. Now suppose the only such chains are $S_{a_1}, S_{a_2}, ... S_{a_m}$ for some $m\le N$. Suppose $a_i = g^{b_i} (a)$ for each $i$. It's clear for any $g^k (a) \in S_{a_i}$ that $g^k (a) = g^{b_i} (a) +k-b_i = k + a_i-b_i$, which implies $g^k (a) \in \{ k+a_1-b_1, k+a_2-b_2, ... k+a_m-b_m\}$. In particular if $M = \text{max} (a_1-b_1, a_2-b_2,...a_m-b_m)$, then $g^k (a) \le k+M$. Similarly, we can find $M'$ with $g^k (b) \le k+M'$. But then it's clear that $\{ a, g(a), g^2 (a), ... g^k (a), b, g(b), ... g^k (b) \} \subseteq \{1,2,... k + M+M'\}$, and the former set has size $2k$ while the latter has size $k+M+M'$, a contradiction for large enough $k$, so we are done.

This can probably be worded better, but the underlying idea is pretty simple: that there are too few values to "fit" into $f$. Note that by the given condition, $f^i(n)$ grows arbitrarily large. Indeed, we can take the sequence $a_0=n$ and $a_{i+1}=a_i + k_{a_i}$; then inductively, $f^{2a_j - 2n}(n)=a_j$ for each $j$.Suppose that for distinct $k, k'$, we have $f^k(n)=f^{k'}(n)$ for some $n$. Then it follows that the sequence $n, f(n), f^2(n),...$ has only finitely many distinct terms, contradicting the fact that $f^i(n)$ grows arbitrarily large. Now, let $g(x)=f(f(x))$ and suppose $k_i\le K$ for all $i$ and some absolute constant $K$. Fix $n$. We define a $g$-sequence to be a sequence $x_i$ with $x_0=x$ and $x_{i+1}=x_i+k_{x_i}$. Then note that $g^{x_i-x}(x)=x_i$. We claim that $x_i$ contains all values $t$ such that $g^{t-x}(x)=t$. But this is easy to show inductively as well; indeed, if $x_i<t<x_{i+1}$ and $g^{t-x}(x)=t$, then we would actually have $t=x_i+k_{x_i}$, contradiction. Let $a_i=g^i(n)$. Let $G(i)$ denote the $g$-sequence that starts with $i$. We claim that we can partition $A=\{a_0, a_1,...\}$ into at most $K$ $g$-sequences $G(i_1),..., G(i_m)$ such that the $g$-sequences are disjoint and have union $A$. First, we show that if $G(i)$ and $G(i')$ have a common term and $i<i'$, then $G(i')\subset G(i)$. Let $s$ be this common value such that $s=g^{s-n}(n)$. Let $s'$ be the value before $s$ in $G(i')$; then $s'=g^{s'-n}(n)$. But then since $g(i)$ contains all values $t$ with $g^{t-n}(n)=t$, $s'\in G(i)$. Now, working backwards, we eventually show that the first term of $G(i')$ is in $G(i)$; moreover, any term beyond the first term of $G(i')$ must be in $G(i)$ by the recursive nature of $g$-sequences. This implies that for any two $g$-sequences, they are either completely disjoint, or one $g$-sequence is a subset of the other. Thus we can partition $A$ with recursively as follows: Start with $i_1=0$. Given $G(i_1),...,G(i_m)$, consider the smallest term $i_{m+1}$ of $A$ not in any of $G(i_1),...,G(i_m)$. Then add $G(i_{m+1})$ to the set of $g$-sequences. Suppose that it requires at least $K+1$ $g$-sequences to partition $A$ such each of the $g$-sequences are pairwise disjoint. Then take $X$ larger than the smallest term of $K+1$ of the $g$-sequences; consider the values $X,X+1,...,X+K-1$. Each of these is part of at most one $g$-sequence; thus by Pigeonhole, there is some $g$-sequence that contains none of $X,..., X+K-1$. Note that this means that there are consecutive elements $y$ and $y'$ in some $g$-sequence such that $y\le X-1$ and $y'\ge X+K$. But note that $y'-y=k_y\ge K+1$, contradicting that all the $k_i$ were bounded by $K$. Thus, at most $K$ $g$-sequences can partition $A$. Now, we claim that there is an absolute constant $c$ such that $|g^j(n)-n-j|\le c$. We prove this inductively. Let the $g$-sequences that partition $A$ have first terms $i_1<i_2<...<i_m$ with $m\le K$. For $j>i_m$, note that $g^j(n)$ belongs in some $g$-sequence that partitions $A$. Moreover, $g^j(n)$ is not the first term in said $g$-sequence. Thus, there is some $j'<j$ with $g^{j'}(n)=g^j(n)-j+j'$. Then $g^{j'}(n)-n-j'=g^j(n)-n-j$, so we can just use the inductive hypothesis on $j'$. Note that we can similarly arrive at the same condition if we replace $n$ with $f(n)$. In other words, there is some absolute constant $c'$ such that $|g^j(f(n))-f(n)-j|\le c'$. But then take some $r$ large and write $C=\max(c,c')$. Consider the values $X,X+1,...,X+r-1$. This set has $r$ values in it. Now, note that $g^{X-n+C}(n),..., g^{X-n+r-C-1}(n)$ must belong to this set by the bounded condition. Similarly, $g^{X-f(n)+C}(f(n)),..., g^{X-f(n)+r-C-1}(f(n))$ belong to this set. None of these values can be equal to each other as well; thus the set has at least $2(r-2C)$ values in it. But then the size of the set is $r$, so $r\ge 2(r-2C)$, an obvious contradiction for $r$ large. Thus it follows that $k_n$ must be unbounded.

Suppose the sequence $k_1, k_2, \cdots $is bounded by $M$, then for every $n$, there exist $1\le k_n\le M$ such that $f^{2k_n}(n)=n+k_n$. Note that the orbit $\{n,f(n),\cdots f^{2k_n}(n)=n+k, \cdots\}$, has distinct values, otheriwse it is periodic and bounded. But we can construct an infinite sequence $a_1, a_2, \cdots$, so that $f^{2a_1}(n)=n+a_1$, and for all $i\ge 2$, $f^{2a_i}(n+a_1+\cdots+a_{i-1})=n+a_1+\cdots+a_{i-1}+a_i$, then $$f^{2a_1+2a_2+\cdots +2a_i}(n)=f^{2a_2+\cdots+2a_i}(n+a_1)=\cdots=f^{2a_i}(n+a_1+\cdots+a_{i-1})=n+a_1+\cdots +a_i$$which is unbounded. This means that the orbit has distinct values for every $n$. Let $m\in \mathbb{N}$ and $g(i)=f^{2i}(1)-i$ for $i\in \mathbb{N}$. Construct a sequence $a_1,a_2,\cdots$ bounded by $M$, so that $f^{2a_1}(f^{2m}(1))=f^{2m}(1)+a_1$ and for all $i\ge 2$, $f^{2a_i}(f^{2m}(1)+a_1+\cdots+a_{i-1})=f^{2m}(1)+a_1+a_2+\cdots+a_i$. Denote $\ell_i=a_1+a_2+\cdots a_i$, we get $$f^{2m+2\ell_i}(1)=f^{2a_1+2a_2+\cdots 2a_i}(f^{2m}(1))=f^{2m}(1)+a_1+a_2+\cdots a_i=f^{2m}(1)+\ell_i$$which gives $g(m+\ell_i)+m+\ell_i=g(m)+m\ell_i \Rightarrow g(m+\ell_i)=g(m)$. Observe that $(m+\ell_{i+1})-(m+\ell_i)=a_{i+1}\le M$, so for any interval $[N+1,N+M]$ of size $M$, at least one of the terms $m, m+\ell_1, \cdots$ is in the interval. We claim that $g$ takes at most $M$ distinct values. Otherwise consider $g(m_1), g(m_2), \cdots, g(m_{M+1})$ to be distinct, then take an interval $[N+1,N+M]$ of size $M$, with $N>\max(m_1,m_2,\cdots m_{M+1})$. Then we can choose some $p_1, p_2, \cdots p_{M+1}$ so that $g(m_i)=g(m_i+p_i)$ and $m_i+p_i \in [N+1,N+M]$. So some two of $m_i+p_i$ must coincide by Pigeonhole Principle, say $m_i+p_i=m_j+p_j$ for $i\neq j$. But this cannot hold since $g(m_i)=g(m_i+p_i)=g(m_j+p_j)=g(m_j)$ while by definition $g(m_i)\neq g(m_j)$, false. So $g$ can take at most $M$ distinct values, hence bounded. Argue similarly, we define $h(i)=f^{2i-1}(1)-i$ and construct a sequence $a_1,a_2,\cdots$ bounded by $M$, with $f^{2a_1}(f^{2m-1}(1))=f^{2m-1}(1)+a_1$ and for all $i\ge 2$, $f^{2a_i}(f^{2m-1}(1)+a_1+\cdots+a_{i-1})=f^{2m-1}(1)+a_1+a_2+\cdots+a_i$. Then if $\ell_i=a_1+a_2+\cdots a_i$, we get $$f^{2m-1+2\ell_i}(1)=f^{2a_1+2a_2+\cdots 2a_i}(f^{2m-1}(1))=f^{2m-1}(1)+a_1+a_2+\cdots a_i=f^{2m-1}(1)+\ell_i$$which gives $h(m+\ell_i)+m+\ell_i=h(m)+m\ell_i \Rightarrow h(m+\ell_i)=h(m)$. So we deduce similarly that $h$ is bounded. Now, consider the orbit $\{f(1), \cdots, f^{2m}(1)\}$. From above, $\displaystyle A=\max_{j\in \mathbb{N}}g(j), B=\max_{j\in \mathbb{N}}h(j)$ exists. So for all $1\le i\le m$, $f^{2i}(1)\le i+A\le m+A, f^{2i-1}(1)\le i+B\le m+B$. So the values in the orbit are bounded by $m+\max(A,B)$. But the orbit has $2m$ distinct values, so $2m\le m+\max(A,B)$ for all positive integers $m$, false when $m>\max(A,B)$. This is a contradiction and so $k_1,k_2, \cdots$ must be unbounded. $\blacksquare$

To be more readable let us write $k(n)$ instead of $k_n$ . Suppose on the contrary $k(n)$ is bounded and $k(n)\leq k\,,\, \forall n\in \mathbb{N}$. Let $A$ be the set $\{1,f(1),f^2(1),f^3(1),\dots\}$. For any $a\in A$ let us consider the set $O(a) := \{a, f^{n_1}(a),f^{n_2}(a),\dots\}$, where $n_1 = 2k(a), n_2 := n_1+2k(f^{n_1}(a)), \dots,n_{j+1} := n_j+2k(f^{n_j}(a)),\dots $. We call $O(a)$ a partial orbit with a seed $a\in A$. It's easy to see that for any $a,b\in A$ either $O(a)\cap O(b)=\emptyset$ or one partial orbit is included in the other one. Note also that the (lower) density of the set $\{n\in\mathbb{N}\mid f^n(1)\in O(a)\}$ is at least $\frac{1}{2k}$. Thus, we can take some $a_1,a_2,\dots,a_m$ such that the corresponding partial orbits $O(a_j)$ are disjoint and the density of the union $M$ of the sets $M_j := \{n\in\mathbb{N}\mid f^n(1)\in O(a_j)\}$ is at least $1-\varepsilon$, for some small $\varepsilon>0$. The idea is that for some big $N\in \mathbb{N}$ the values $f^m(1), m\in M\cap[1..N]$ are confined in an interval that is roughly two times smaller than $|M\cap[1..N]|$, which would be impossible since they are pairwise different. Indeed, for any two consecutive elements $m_1,m_2$ of $M_j$ we have $f^{m_2}(1)-f^{m_1}(1)=(m_2-m_1)/2 $. It means: $\max \{f^m(1): m\in M_j\cap [1..N])\} \leq a_j+N/2$. Hence: \[\max \{f^m(1) : m\in M\cap[1..N]\} \leq \max (a_j) +N/2\]Since $|M\cap[1..N]|\geq (1-\varepsilon)N$ we come to a contradiction providing $N$ is big enough.

First, note that for all $n$ there does not exist $m$ with $f^m(n)=n$. Otherwise, if $f^i(n)$ is maximal over all $1\le i\le m$, then $f^{2k}(f^i(n))\le f^i(n)<f^i(n)+k$ for all $k$, a contradiction. Now, suppose that $k$ is bounded above by $m$. Let $g(x)=f(f(x))$, and consider the sequence $a,g(a),g(g(a)),\ldots$. We claim that this sequence contains all but finitely many positive integers. For every term $g^i(a)$ in this sequence, draw an arrow from it to $g^{i+k}(a)=g^m(a)+k$, where $k$ is minimal. Such a $k$ exists by the condition of the problem. Note that no term in the sequence can have two arrows going into it. Indeed, if $g^i(a)$ and $g^j(a)$ both point at $g^k(a)$ with $i<j$, then $g^i(a)$ would point at $g^j(a)$ instead. We claim that this now partitions the the sequence into at most $m$ chains, i.e. there are at most $m$ terms in the sequence with no arrows going into it. Indeed, each chain has density at least $\frac 1m$ in $\mathbb N$ as the difference between consecutive terms in each chain is bounded above by $m$. Now, let $f^{a_1}(a)=b_1,f^{a_2}(a)=b_2,\ldots,f^{a_i}(a)=b_i$ be the terms with no arrows going into it. Note that if the term $f^k(a)$ is in the chain starting with $f^{a_j}(a)$, then $f^k(a)=k+b_j-a_j$. In other words, the $k$th term of this sequence is at most $k+C$, where $C=\max(b_j-a_j)$, which implies the claim. Now, note that by the claim both of the sequences $1,f(f(1)),f(f(f(f(1)))),\ldots$ and $f(1),f(f(f(1))),f(f(f(f(f(1))))),\ldots$ contain all but finitely many positive integers. But this is a contradiction, as all the terms in the sequence $1,f(1),f(f(1)),\ldots$ are distinct by our first observation.

So this problem is actually pretty weak. Let $n$ be any integer, and let $a_i = f^i(n)$ with $n = a_0$. Let $m_i = k_{a_i}$. We will show that the $m_i$ are unbounded, which clearly finishes. We see that $f$ has the functional digraph: \[ a_0 \to a_1 \to \cdots \]Consider a new graph $G'$ whereby we draw an edge from $i$ to $i+2m_i$. We first claim that each vertex has indegree at most $1$. Suppose by contradiction that $i+2m_i = j+2m_j = x$ with $i < j$. Then, if $m_j < m_i$, let $k = m_i - m_j < m_i$. We see that \[ a_j = a_{j+2m_j} - m_j = a_x - m_j = a_x - m_i + k = a_i + k, \]so $a_{i+2k} = a_i+k$, contradicting minimality of $m_i$. So, the connected components are of the form \[ x_0 \to x_1 \to \cdots. \]Call $x_0$ the source of this component. Now suppose by contradiction that the $m_i$ are bounded above by $M$. Also, note that $x_{i+1} - x_i \leq 2M$, so we see that if there are $2M+1$ or more (possibly infinite) components, take any $2M+1$ of them with sources $s_0, \ldots, s_{2M}$, and for $N > \max(s_i)$ we see that each component must contain at least one of $N+1, \ldots, N+2M$, contradiction since no number can appear in multiple components. Thus, there are at most $2M$ components. Say there are $C$ of them, $C_1, \ldots, C_k$, with sources $r_1,\ldots, r_k$. Also, let $t_i = a_{r_i}$. Then, if $x$ appears in $C_i$, then \[ a_x = t_i + \frac{x-r_i}{2}. \]Also, let $m = \min (r_i - 2t_i)$. Let $N > \max(t_i)$. Say $x \leq 2N+m$ and $x$ appears in component $i$, then \[ a_x = t_i + \frac{x-r_i}{2} = \frac{x-r_i+2t_i}{2} \leq \frac{2N+m-r_i+2t_i}{2}\leq N. \]However, $x\to a_x$ must be injective, or else $a_x$ is eventually periodic and then we can pick $x$ so that $a_x$ is maximal and we need to draw an edge from $x$ to some $y$ with $a_y > a_x$, contradiction. So, of the $x\to a_x \colon \{0, 1, \ldots, 2N+m\} \to \{1,2,\ldots, N\}$ is injective, or $2N+m+1 \leq N$ for all $N$, which means $N \leq -m-1$ for all positive integers $N$, contradiction. Thus $m_i$ is unbounded and so is $k_i$. $\blacksquare$

Suppose the contrary, namely that $\{k_i\}$ is bounded above by $M$. Then, consider the sequence $S: 1, f(1), f^2(1), f^3(1),\ldots $. First, note that all terms in $S$ are distinct, or else we will have a cycle (i.e. $f^m(n)=n$ for some $m,n$), in which case the largest number in the cycle can't satisfy the condition. Define a leeky sequence to be a sequence $\{a_i\}$ such that $a_{i+1}=f^{2k_{a_i}}(n)$. Then, partition $S$ into a number of leeky sequences. Note that no two leeky sequences intersect, since this would imply we have 3 numbers $a<b<c$ such that $f^a(1)+\frac{c-a}{2}=f^b(1)+\frac{c-b}{2}=f^c(1)$ and $k_{f^a(1)}=\frac{c-a}{2}$. This is a contradiction, though, because $f^b(1)=\frac{b-a}{2}$, so $k_{f^a(1)}\le \frac{b-a}{2}<\frac{c-a}{2}$. Furthermore, note that, in our partition, there are a bounded amount of leeky sequences (in fact, at most $2M$.) This is because each jump in a leeky sequence is at most $2M$, so the density of each leeky sequence in $S$ is at least $\frac{1}{2M}+o\left(\frac{1}{M}\right)$, implying the result. Now, for a leeky sequence $f^{x_i}(1)$, note that all the $x$s have the same parity, so it makes sense to split $S$ into $\{a_i\}=\left\{f^{2i}(1)\right\}$ and $\{b_i\}=\left\{f^{2i-1}(1)\right\}$. For $a_i$, suppose the starts of the leeky sequences it is partitioned into are $f^{A_1}(1),f^{A_2}(1),\ldots, f^{A_n}(1)$. Define $x_1=f^{A_1}(1)-A_1,$ etc. Then, for sufficiently large $i$, we have that $a_i=x_k+i$, for some $k$. So, for sufficiently large $i$, the first $i$ terms of $a$ are bounded by $i+\max(x_k)$, and the density of $\{a_i\}$ approaches $\lim_{i\to\infty}\frac{i+\max(x_k)}{i}=1$. However, the density of $\{b_i\}$ is also 1 by the same logic. As they are disjoint, we have a contradiction.

Let $g=f^2$, and suppose for sake of contradiction that the sequence $k_1,k_2,\ldots$ is bounded above by $M$ (we'll take the liberty to assume that $M$ is in fact much larger than all the $k_i$s). We'll derive a pretty strong structural result for $g$. As usual, we'll be considering the arrow diagram of $g$, i.e. a directed graph with vertex set $\mathbb{N}$ and edges $x\mapsto g(x)$. The first claim is that the arrow diagram doesn't contain any cycles. Indeed, suppose we reached a cycle \[x_1\mapsto x_2\mapsto\cdots\mapsto x_n\mapsto x_1.\]WLOG, suppose that $x_1$ is the largest element of the cycle. We know that there exists some $k\ge 1$ such that $g^k(x_1)=x_1+k$, contradicting the maximality of $x_1$. Thus, we can be assured that the arrow diagram contains the infinite chain \[1=g^0(1)\mapsto g^1(1)\mapsto g^2(1)\mapsto\cdots\]with no repeated elements. We have the following killer claim. Claim: As $a$ varies over the nonnegative integers, $g^a(1)-a$ takes only finitely many different values. Proof: Consider the directed graph with vertex set $\mathbb{Z}_{\ge 0}$ and edges $a\mapsto a+k_{g^a(1)}$. Note that this partitions $\mathbb{Z}_{\ge 0}$ into many chains (here the chains may contain some finite tree-like structure in their beginning, but this is irrelevant for our argument). The key point is that in each chain, the consecutive elements are separated by at most the maximum value of $k$, so at most say $M/100$. We claim that there are at most $M$ chains. Indeed, suppose we had $M+1$ chains. Taking $\{1,2,\ldots,N\}$ where $N$ is much larger than the smallest elements of each of the chains, we see that each chain takes up at most $N/M$ of the set, so we have a contradiction, since the chains are disjoint. Now, say we have an edge $a\mapsto b$. We see that $g^b(1)=g^a(1)+b-a$ by the condition of the problem, so $g^a(1)-a=g^b(1)-b$. Therefore in each chain, the value of $g^a(1)-a$ is constant. We established above that there were only finitely many chains, so the proof of the claim is complete. $\blacksquare$ Suppose that $g^a(1)-a$ takes the distinct values $\beta_1,\ldots,\beta_r\le\alpha$, and let $T_i$ be the set of $a$ such that $g^a(1)-a=\beta_i$. Note that the $T_i$s partition $\mathbb{Z}_{\ge 0}$. Furthermore, all the sets $T_i+\beta_i$ are disjoint, since $T_i+\beta_i=\{g^a(1):a\in T_i\}$. Note that \[|(T_i+\beta_i)\cap[N+\alpha]|=|T_i\cap[N+\alpha-\beta_i]|\ge|T_i\cap[N]|,\]so summing over $i$, we get that \[\sum_{i=1}^r|(T_i+\beta_i)\cap[N+\alpha]|\ge N.\]Thus, the sets $T_i+\beta_i$ miss at most $\alpha$ of the numbers in $[N+\alpha]$. This means that the sets $T_i+\beta_i$ miss at most $\alpha$ of the numbers in $\mathbb{N}$ (if they missed more, take $N$ bigger than all the numbers missed). As we mentioned above, the sets $T_i+\beta_i$ partition the chain \[1=g^0(1)\mapsto g^1(1)\mapsto g^2(1)\mapsto\cdots,\]so this chain contains all but finitely many elements of $\mathbb{N}$. We're now in a position to finally solve the problem. Note that $f$ can't have any cycles, since a cycle in $f$ implies a cycle in $g$. Therefore, we have the infinite chain \[1=f^0(1)\mapsto f^1(1)\mapsto f^2(1)\mapsto\cdots\]of distinct natural numbers. Yet we showed above that if we just look at every other number, we get all but finitely many of the natural numbers. This is a contradiction, as this implies that the set $\{f^1(1),f^3(1),f^5(1),\ldots,\}$ is finite. Thus, we have the desired contradiction, so the problem is solved.

Suppose that the sequence is bounded by some $M$. Note that $f$ is cyclefree (by considering the maximal element of some cycle). Let $S=\{1,f(1),f^2(1),\ldots\}$, and consider the graph with the elements of $S$ as vertices, and draw a directed edge connecting $n$ to $n+k_n$ where $n$ is a vertex. Note that every vertex has outdegree 1, and it must have indegree at most 1 as well, since if $x,y \to a$ and $x<y$, so $k_x=a-x$, taking $k=y-x<a-x$ works as well, contradicting the minimality of $k_x$. Since the graph is also cycle-free, it follows that it is the union of disjoint "infinite chains". If we can find $M+1$ chains, with maximal starting element $N$, then the set $S=\{N,\ldots,N+M-1\}$ overlaps with some element of every chain, as the difference between consecutive elements of a chain is at most $M$. But since chains are disjoint, we need $|S|\geq M+1$ which is clearly false. Thus we have at most $M$ chains—the exact value doesn't matter, just that it's finite. Now, note that $f^i(1)-i/2$ is constant for all $i$ such that $f^i(1)$ is in a given chain, so $f^n(1)$ is bounded above by $n/2+C$ for some fixed $C$. On the other hand, the set $\{f^0(1),f^1(1),f^2(1),\ldots,f^{n}(1)\}$ contains $n+1$ distinct elements, so one must be at least $n+1$. But for sufficiently large $n$, we have $n+1>n/2+C$, which is a contradiction. $\blacksquare$

Take $a, f^2(a), f^4(a), \ldots$ and $f(a), f^3(a), \ldots$. Let $s$ be an integer upper bound on $k_n$. Notice both sequences have an asymptotic density of at least $\frac{1}{s}$. Furthermore notice that if there exists some fixed $m$ such that $m = f^{2k}(a)-k$ for some $k$, then the set of such $k$ has an asymptotic density at least $\frac{1}{s}$. Thus there are finitely many such values of $m$, so there exists $M$ such that $f^{2k}(a) \leq M+k$ for all $k$. However the same applies to the sequence taking $f(a)$ as the new $a$, so there exists another $M$ such that $f^k(a) \leq M+\frac{k}{2}$ for all $k$. However this is impossible since $\max_k{f^k(a)} \geq k$, so we are done.

\[\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow \rightarrow \rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\] Suppose $(k_i)$ was bounded by a constant $M$. Claim: $f$ cannot have any cycles Proof: Suppose $f$ had a cycle, let $a$ be the largest element of the cycle. We have $f^{2k}(a) \le a$, which means $n + k \le a$, absurd. $\square$ Thus, $f^x(n) = f^y(n)$ for any nonnegative integers $x,y$ and positive integer $n$ implies $x=y$. Let $g(n) = n + k_n$. Claim: If $g(f^a(1)) = g(f^b(1))$ then $a = b$. Proof: Suppose $g(f^a(1)) = g(f^b(1))$ and $a\ne b$. Let $i= f^a(1)$ and $j= f^b(1)$. WLOG $k_i >k_j$. We have $i + k_i = j + k_j$. We also have $f^{2k_i}(i) = f^{2k_j}(j)$, so $f^{2k_i + a }(1) = f^{2k_j + b}(1)$, which means $2k_i + a = 2k_j + b$, so $b-a = 2k_i - 2k_j$. Hence \[f^{2(k_i - k_j)}(i) = f^{b-a}(i) = j = i + k_i - k_j,\]which is a contradiction because $k_i$ is supposed to be minimal. $\square$ Draw an arrow going from $n$ to $n + k_n$ for all positive integers $n$. Now we can partition $\{1, f(1), f(f(1)), \ldots, \}$ into disjoint infinite chains of arrows. Claim: There are at most $M$ chains. Proof: Suppose not and we had more than $M$ chains. Notice that to go from one value to the next through an arrow, we add by at most $M$, which means that for each chain and sufficiently large $N$, there exists a number in the chain in the interval $[N , N + 1, \ldots, N + M)$, which shows there can be at most $M$ chains due to the chains being disjoint. $\square$ We see that for each positive integer $a$, $f^{a}(1) \le \frac{a}{2} + C$, where $C$ is the largest starting term of a chain (this is true because $f^{a}(1) - a/2$ is constant over all $a$ in a given chain). Now, for any large positive integer $X$, we note that $\{1, f(1), f(f(1)), \ldots, f^{X}(1)\}$ has to have some element greater than or equal to $X + 1$, but this is impossible because $f^n(1) \le X/2 + C < X + 1$ for any $n\le X$. Thus, $(k_i)$ must be unbounded.

Beautiful! Assume for contradiction that the sequence is bounded by some $M \ge 1$. For a function $h$, let $G_h$ be the digraph on $\mathbb{N}$ induced by $h$. Claim: $G_f$ has no cycles. Proof. Assume not. Then consider some cycle $\mathcal{C}$, and let its largest element be $R$. Then $f^{2k_R}(R)=R+k_R>R$, a contradiction. Let $g(n)=n+k_n$, and draw $G_g$. Note that each vertex of $G_g$ has outdegree exactly 1, and each vertex has indegree exactly 1, otherwise, if $x+k_x=y+k_y$ where $k_x > k_y$ (WLOG), then $k_x=a-x$, but $k=y-x<g(x)-x$ works too, a contradiction. Thus $G_g$ is the union of multiple disjoint chains. It follows from the original condition that the interval $I=[N, N+M)$ has a nonempty intersection with each chain, and thus there are at most $M$ chains. In particular, $G_g$ is the union of only a finite number of disjoint chains. Over all $k$ such that $f^{k}(1)$ is in a chain, $f^k(1)-k/2$ is constant, so $f^n(1)>n/2+C$ for some constant $C$. However, since $(1, f(1), f^2(1), \ldots, f^n(1))$ is increasing, it contains exactly $n+1$ distinct elements. However, for $n \ge 2C$, $n/2+C<n+1$, a contradiction.

Very classic arrows flavor. Set $S = \{f^k(1) \mid k \geq 0\}$ and define $g(n) = n+k_n$ for each $n \in S$. Draw arrows corresponding to the graph of $G$. Claim. $g$ is injective. Proof. Suppose otherwise. Then $i+k_i = j+k_j$ and furthermore $f^{2k_i}(i) = f^{2k_j}(j)$ for some $i, j$. But then as $f$ is injective in $S$, it follows that $$f^{2k_i}(i) = f^{2k_j-2k_i}(j) \text{ and } i = j+(k_j-k_i).$$This contradicts minimality. $\blacksquare$ Now assume for the sake of contradiction that $\{k_n\}$ is bounded, i.e. $k_i < C$ for all $i$. Then consider partitioning the graph on $G$ into distinct chains of arrows. Notice that there are at most $C$ such chains (consider any $C$ consecutive elements in $S$), so there exists a finite $R$, the maximum value among all the first elements of the chains. Now, pick the chain indexed $c$ with starting value $R$, and let the lengths of the arrows (or the corresponding $k_i$) be $a_1, a_2, \dots$. Pick a large $N > 0$ such that $a_1+a_2+\cdots + a_N > R$. Finally, consider the numbers $f^k(1)$ up to $k = a_1+a_2+\cdots+a_N +c$. The maximum value of $f$ on this interval is $R+a_1+a_2+\cdots + a_N < 2(a_1+a_2+\cdots+a_N) + c$, which means that two values of $f$ coincide on this interval. This is obviously impossible.

I put the dense in density FTSOC suppose that $k_n \le N$ for all $n$ and fixed $N$. Claim: $f$ is acyclic. Proof. Any cycle must contain a maximum element $m$, however then $f^{2k_m}(m)$ is larger, contradiction. $\blacksquare$ Define $g = f^2$. Let a g-chain be a chain $n, g(n), g^2(n), \dots$ and let a jump chain be the chain $n. g^{k_n}(n) = n + k_n, n + k_n + k_{n + k_n}, \dots$. Then g-chains can be partitioned into jump chains. Claim: There are at most $N$ jump chains total. Proof. Each jump chain takes up $\frac{1}{N} - o(1)$ of the first $n$ numbers. $\blacksquare$ Claim: The density of a jump chain of length $N$ approaches the density in first $N$ integers. Proof. Follows since $g^{k_n}(n) = n + k_n$, so the density are the same up to $O\left(\frac{C}{n}\right)$ for some $C$. $\blacksquare$ It must follow that there is exactly one $g$-chain, or that $g(x) = x + 1$. This is impossible.

Let $S = \{1, f(1), f^2(1), \dots \}$. We'll prove $f$ is injective on $S$. Assume the contrary, $f(f^i(1)) = f(f^j(1))$ for some $i, j$. Then $f^{i+1}(1) = f^{j+1}(1)$, which means $S$ contains finite number of integers. But for all $n$, there exists $k$ such that $f^{2k}(n) = n + k$, hence $S$ contains infinite numbers, a contradiction. Now let $g(n) = n + k_n$. Consider the following claim: Claim: $g$ is injective on $S$. Proof. Assume the contrary, $g(a) = g(b)$ for some $a, b \in S$. WLOG, assume $a > b$. Then since $a + k_a = b + k_b$, we have $k_a < k_b$. Since $f^{2k_a}(a) = a + k_a = b + k_b = f^{2k_b}(b)$ and $f$ is injective on $S$, we get $b + k_b - k_a = a = f^{2k_b - 2k_a}(b)$, contradicting $k_b$ is the minimum. $\blacksquare$ Note that $g(S) \subseteq S$, so $g$ is made from some chains. Now assume there exists $C$ such that $k_n \le C$ for all positive integer $n$. Claim: The number of chains in $g$ does not exceed $C$. Proof. Assume there were at least $C + 1$ chains. Note that for every positive integer $k$, every chain meets interval $k + 1, k + 2, \dots k + C$ at least once, so taking $k$ large would give a contradiction. $\blacksquare$ Let $x_i = k_{f^i(1)}$. Draw a red arrow from $i$ to $i + 2x_i$ for all nonnegative integer $i$. Call this graph $H$. Then since $f^{2x_i}(f^i(1)) = f^i(1) + x_i = f^i(1) + k_{f^i(1)}$, hence $H$ is made from chains. Moreover, the number of chain in $H$ is exactly same as the number of chains in graph of $g$. But the chains in $H$ grows approximately 2 times faster than the chains in $g$, this gives an evident contradiction. Therefore the sequence $k_1, k_2, \dots $ is unbounded. $\blacksquare$

MellowMelon wrote: See here for a harder (and open) version of the problem. this link doesn't work. Does anyone have the harder version of the problem?

Let's prove this by contradiction. Suppose, for the sake of contradiction, that the sequence \(k_1, k_2, \ldots\) is bounded, meaning there exists a positive integer \(M\) such that \(k_n \leq M\) for all \(n \in \mathbb{N}\). Consider the function \(f^{2M}(n) = n + M\). Since \(k_n\) is the smallest such \(k\) satisfying \(f^{2k}(n) = n + k\), it follows that \(k_n \geq M\). This implies that for every \(n\), there exists a \(k \geq M\) such that \(f^{2k}(n) = n + k\). Now, consider the case when \(n = M + 1\). According to our previous observation, there exists a \(k \geq M\) such that \(f^{2k}(M + 1) = M + 1 + k\). However, since \(k \geq M\), we have \(M + 1 + k > M + M + 1\), which means \(f^{2k}(M + 1) > f^{2M}(M + 1)\). This contradicts the fact that \(f^{2M}(n) = n + M\) for all \(n\). Therefore, our assumption that the sequence \(k_1, k_2, \ldots\) is bounded must be false. Hence, the sequence \(k_1, k_2, \ldots\) is unbounded.

Kingsbane2139 wrote: this link doesn't work. Does anyone have the harder version of the problem? I've edited the post and fixed the link. It should have gone here.

Assume toward a contradiction there exists $N$ such that $k_1, k_2,\dots < N$. Claim: \[1, f(1), f^2(1),\dots\]are distinct. Proof: Assume toward a contradiction that $f^a(1) = f^b(1)$ for some $a<b$. Choose $r\in [a, b]$ such that $f^r(1)$ is maximized. Then, for some $k$, $f^{2k}(f^r(1)) = f^r(1) + k > f^r(1)$. However, $f^{2k}(f^r(1)) \in \{f^a(1), f^{a+1}(1),\dots, f^b(1)\}$, which contradicts $f^r(1)$ being maximal. Claim: $f^k(1)-\frac k2$ is unbounded Proof: Assume toward a contradiction there exists $S$ such that $f^k(1)-\frac k2<S$ for all $k\in \mathbb{Z}_{\ge 0}$. Then, \[1, f(1), \dots, f^{2S}(1) < 2S.\]By pigeonhole, this contradicts the first claim. Claim: Let $M\in \mathbb{N}$. Let $k<M$. There exists $j\in [M+1, M+2N]$ such that $f^j(1) - \frac j2 = f^k - \frac k2$. Proof: Let $k'$ be the maximum value such that $k'\le M$ and $f^{k'}(1) - \frac {k'}2 = f^k-\frac k2$. Then, there exists $m<N$ such that \[f^{k'+2N}(1) - N - \frac{k'}2 = f^{k'}(1)-\frac{k'}2 = f^k-\frac k2.\]Then, $M< k'+2N \le M+2N$. Let $M$ be an integer such that $f^k(1)-\frac k2$ achieves at least $2N+1$ different values for $k<M$. Then, there are at least $2N+1$ different values in $\{f^{M+1}(1), f^{M+2}(1), \dots, f^{M+2N}(1)\}$, a contradiction.

This is more like C than A Suppose for the sake of contradiction that the statement is false, aka there is some $K$ such that $k_i < K$ for all $i$. Pick any integer $n$ and define the sequence $a_i$ with $a_0 = n$ and $a_{k+1} = f(a_k)$ We will start by noting some facts: $(1): a_{i+2k_i} = i+k_i$ $\textbf{proof:}$ this is by definition $(2): \textit{the sequence is uniquely defined forwards}$ $\textbf{proof:}$ this is obvious by definition $(3): \textit{the sequence grows arbitrarely large}$ $\textbf{proof:}$ we have that $n+k_n$ is a member of the sequence, we also know that $n+k_n + k_{n+k_n} > n+k_n$ is a member of the sequence, by continuing this chain, the sequence attains arbitrarely large values $(4): \textit{all members of the sequence are distinct}$ $\textbf{proof:}$ this is clear from $(2)$ and $(3)$ now we assign to each member of the sequence $a_i$ the point $P_i = (i,a_i)$ in the plane. Additionally, to each point we assign the line $l_i$ that passes through $P_i$ and has slope $\frac 12$. additionally, we also assign to each $P_i$ the line $w_i$ that passes through $P_i$ and has slope $0$. By definition of $l_i$ we know that $P_i$ lies on it, we also know that $P_{i+2k_i}$ lies on that line, hence there are an infinite number of points on each line $l_i$. From this it follows directly that the total number of lines $l_i$ is bounded above by $2K$, suppose there were more than $2K$ lines, then considering by pigeonhole there exists a line $l_j$ which does not contain a point for at least $2K+2$ iterations of the sequence. This is a contradiction since that implies that there is a $k_j > K$ which contradicts that assumption. Now from $(4)$ we can conclude that every line $w_i$ contains exactly one Point, if it were to contain two distinct points $P_i$ and $P_j$, then we would have $a_i = a_j$ and hence the sequence would be periodic. Now finally we make use of the fact that the lines have slope $\frac 12$: consider a reference line $L:y=\frac 12 x$, then since the total number of lines is bounded, the vertical distance from $P_i$ to $L$ is bounded. since both lines have slope $\frac 12$, this strip in the plane where our points (which have integer coordinates) live, gains an extra slot every 2 steps to the right, but from the condition on the $w_i$, it loses one slot every 1 step to the right, hence there are eventually no spots for the $P_i$ to go, which is a contradiction to such a bound $K$ existing, hence the $k_i$'s are unbounded.

It seems quite natural to wonder whether such a function $f$ actually exists, so I'm surprised this question isn't answered in the official solutions, nor in any of the posts in this forum(unless I missed it). Maybe people thought it's too easy to be mentioned... An example of a function $f$ that satisfies the problem condition is:

Of course this is no solution to the problem, but I think it's always good to see that the problem condition can actually hold, because it would feel kinda bad if we were all actually working under an impossible condition.

For any $n$, let $W_n$ denote the set of all numbers $k$ for which $f^{2k}(n)=n+k$. We first show that $W_n$ is infinite. Note that if $k\in W_n$ and $k'\in W_{n+k}$, then $k+k'\in W_n$, as $f^{2k}(n)=n+k$ and $f^{2k+2k'}(n)=f^{2k'}(n+k)=n+k+k'$. Taking $k''\in W_{n+k}$ and so on, we get that $W_n$ is infinite. We showed that if $a\in W_n$ and $b\in W_{n+a}$, then $a+b\in W_n$. We now show that if $a,c\in W_{n}$ and $c>a$, then $c-a\in W_{n+a}$. This is because $n+c=f^{2c-2a}(f^{2a}(n))=f^{2c-2a}(n+a)=n+a+c-a$. Hence, $c-a\in W_{n+a}$. So, we have a bijection between $W_n$ and $W_{n+a}$. It follows that $W_{n+a}=a+W_n$, that is $x\in W_n\Longleftrightarrow x+a\in W_{n+a}$. So, we have $\min(W_{n+a})=a+\min(W_n)$, or basically $k_{n+a}=a+k_{n}$. Since there are infinitely many $a$, it follows that $(k_n)_{n\geq1}$ is bounded. $\blacksquare$

Firstly, we assume FTSOC that $k_i$ are bounded from above by an integer $M$. So lets take a look at the set $S= \{f(1), f(f(1)), \dots \} $, we can't have two elements equal to each others, in other words we cant have a cycle, this is because assume there is a cycle $C$ in $S$. So let the cycle be this below. \[f(1)\rightarrow f(f(1))\cdots\rightarrow f^{X}(1) \rightarrow f(1)\] Assume that $f^{Y}(1)$ be the maximal element of $C$, but we know that if we let $u= f^{Y}(1)$ then taking $f^{2k_u}(u)= u+k_u$ contradicting it's maximality, hence we get that $f$ is acyclic. Now consider a graph $G$ with the elements of $S$ being the vertices, then draw a directed edge from $n$ to $n+k_n$, where $n$ is a vertex. In this graph every vertex has an outdegree $1$ Every vertex has indegree of $1$ Because if there exists $n,m \rightarrow A$ and assume WLOG $n > m$ then we have that $k_m = A-m$, but if we take $k= n-m $ this also works, but $n-m < A-m$ contradicting the minimality of $k_m$. Hence each vertex has an indegree $1$. So now as this graph doesn't have cycles, so it's made of disjoint infinite chains. So assume at some point all chains are at a point that is less than $N$, then if we look at the next elements we see that they all don't exceed $N+M$ this is because the maximal increase is $M$, so we get that at some point all elements of the chains are in the interval $[N, N+M)$, but since the chains are disjoint, hence we can have at most $M$ chains. Now note that we have $f^{i}(n)-i/2$ is constant for all $i$ in same chain, but this means that $f^{n}(1) \leq n/2+C$ for some $C$, but if look at $\{f(1),f(f(1)), \dots f^n(1) \}$ there are $n+1$ distinct elements, so for a sufficiently large $n$ ($n\geq 2C$) we get $n/2+C <n+1$, hence a contradiction.