Putnam 1994/B5 solution

Putnam 1994

Problem B5

For any real α define f_α(x) = [αx]. Let n be a positive integer. Show that there exists an α such that for 1 ≤ k ≤ n, f_α^k(n²) = n² - k = f_α^k(n²), where f_α^k denotes the k-fold composition of f_α.

Solution

Answer: α = e^-1/n².

Fairly easy.

We require α(n² - k) < n² - k, so α < 1. We also require α(n² - k) ≥ n² - (k + 1), so α ≥ 1 - 1/(n² - k). This suggests trying a value near 1 - 1/n². However, we also need [α^kn²] = n² - k, so we would like an α such that α^k is easy to work with. This suggests trying e^-1/n². Certainly 1 > e^-1/n² > 1 - 1/n², so it follows immediately that [α(n² - k)] = n² - (k+1) and hence that f_α^k(n²) = n² - k for 1 ≤ k ≤ n.

For 0 < x < 1, the Taylor series for e^-x has decreasing terms of alternating sign, so 1 - x < e^-x < 1 - x + x²/2. Hence, in particular: 1 - k/n² < α^k < 1 - k/n² + k²/(2n⁴). Hence α^k lies between n² - k and n² - k + k²/(2n²), so [α^kn²] = n² - k, as required.

Putnam 1994