Track / Stage 4 / 51 of 340 #311 of 1964

Problem 311

AMC 12 late, AIME early

Number theory Difficulty 4.6 Find the answer

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

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official 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 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$ .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.