## Problem B3

$\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


## Solution

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 \mathrm{h}$ for $\mathrm{n}=1,2, \ldots, \mathrm{M}-\mathrm{m}-1$ and $\mathrm{f}^{\mathrm{M}-\mathrm{m}}(\mathrm{h})=\mathrm{h}$. Note that the ratio $(\mathrm{M}-\mathrm{m}) / \mathrm{h}$ is worst (smallest) for $\mathrm{h}=\mathrm{M}$.

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

## 11th Iberoamerican 1996

