$\mathrm{f}$ is a function defined on the positive integers with positive integer values. Use $\mathrm{f}^{\mathrm{m}}(\mathrm{n})$ to mean $\mathrm{f}(\mathrm{f}(\ldots \mathrm{f}(\mathrm{n}) \ldots))=\mathrm{n}$ where $\mathrm{f}$ is taken $\mathrm{m}$ times, so that $\mathrm{f}^{2}(\mathrm{n})=\mathrm{f}(\mathrm{f}(\mathrm{n}))$, for example. Find the largest possible $0<k<1$ such that for some function $\mathrm{f}$, we have $\mathrm{f}^{\mathrm{m}}(\mathrm{n}) \neq \mathrm{n}$ for $\mathrm{m}=1,2, \ldots$, $[\mathrm{kn}]$, but $\mathrm{f}^{\mathrm{m}}(\mathrm{n})=\mathrm{n}$ for some $\mathrm{m}$ (which may depend on $\left.\mathrm{n}\right)$.

## Answer

we can get $\mathrm{k}$ arbitrarily close to 1
The basic idea is to take a block of integers $m+1, m+2, \ldots, M$ and to define $f(m+1)=m+2$, $f(m+2)=m+3, \ldots, f(M-1)=M, f(M)=m+1$. Then for any integer $h$ in the block we have $f^{n}(h)$ $\neq h$ for $n=1,2, \ldots, M-m-1$ and $f^{M-m}(h)=h$. Note that the ratio $(M-m) / h$ is worst (smallest) for $h=M$.

For example, take the first block to be $1,2, \ldots, N$, the second block to be $N+1, \ldots, N^2$, the third block, $N^2+1, \ldots, N^3$ and so on. Then for any integer $n$ we have $f^{m}(n) \neq n$ for $m<kn$ where $k=1-1/N$.