Maths Olympiad Prep

Library / /17 of 299

Number theory Difficulty 5.4 AIME, harder Prove it Iran

For a function f:NNf : \mathbb{N} \to \mathbb{N} define P(n)=f(1)f(n)P(n) = f(1) \cdots f(n). Find all functions ff such that for all positive integers aa and bb, we have
P(a)+P(b)a!+b! P(a) + P(b) \mid a! + b!

Solution

Plugging (a,b)=(1,1)(a, b) = (1, 1) to obtain f(1)=1f(1) = 1. We can then inductively prove that f(n)=nf(n) = n. Assume that it has already been held for all positive integers less than nn. Plugging (a,b)=(n,1)(a, b) = (n, 1), then after a simple algebra it follows that f(n)nf(n) \le n and (n1)!f(n)+1(n1)!(nf(n))(n-1)!f(n) + 1 \mid (n-1)!(n - f(n)). Since gcd((n1)!,1+f(n)(n1))=1\gcd((n-1)!, 1 + f(n)(n-1)) = 1 it follows that (n1)!f(n)+1nf(n)(n-1)!f(n) + 1 \mid n - f(n). Thus, nf(n)(n1)!f(n)+1|n - f(n)| \ge (n-1)!f(n) + 1. Assume on the contrary that f(n)nf(n) \ne n then nf(n)n1<(n1)!(n1)<1+(n1)!f(n)|n - f(n)| \le n - 1 < (n-1)!(n-1) < 1 + (n-1)!f(n), a contradiction. Thus, f(n)=nf(n) = n and we are done.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.