Maths Olympiad Prep

Library / /5 of 10

Algebra Difficulty 8.8 Shortlist Prove it United States

Let N\mathbb{N} be the set of positive integers. Find all functions f:NNf : \mathbb{N} \to \mathbb{N} that satisfy the equation
fabca(abc)+fabcb(abc)+fabcc(abc)=a+b+c f^{abc-a}(abc) + f^{abc-b}(abc) + f^{abc-c}(abc) = a + b + c
for all a,b,c2a, b, c \ge 2.
(Here f1(n)=f(n)f^1(n) = f(n) and fk(n)=f(fk1(n))f^k(n) = f(f^{k-1}(n)) for every integer kk greater than 1.)

Solution

Clearly if f(n)=n1f(n) = n - 1 for n>1n > 1, the desired identity will be satisfied. In fact one can easily check that the value of f(2)f(2) is also irrelevant, so any ff such that f(n)=n1f(n) = n - 1 for all n>2n > 2 will work. We show that these are the only such functions.
Plug in a=b=ca = b = c to obtain fa3a(a3)=af^{a^3-a}(a^3) = a for all aa. Using this twice, fa9a(a9)=af^{a^9-a}(a^9) = a. Then, b=c=a4b = c = a^4 gives fa9a4(a9)=a4f^{a^9-a^4}(a^9) = a^4. Meanwhile b=a3,c=a5b = a^3, c = a^5 gives fa9a5(a9)=a5f^{a^9-a^5}(a^9) = a^5; consequently, we get fa5a4(a5)=a4f^{a^5-a^4}(a^5) = a^4.

fbcb(bc)+fbcc(bc)=b+c.(19) f^{bc-b}(bc) + f^{bc-c}(bc) = b + c. \qquad (19)
Now fix a large number NN, and for all divisors dNd \mid N with 1<d<N1 < d < N, define g(d)g(d) by g(d)=fNd(N)dg(d) = f^{N-d}(N)-d. We claim that g(bc)=g(b)+g(c)g(bc) = g(b) + g(c) whenever bcbc is still a proper divisor of NN. Proof: put a=N/bca = N/bc, and write
g(bc)=fabcbc(abc)bc=(a+bcfabca(abc))bc(by (19))=afabca(abc)=fabcb(abc)b+fabcc(abc)c=g(b)+g(c). \begin{aligned} g(bc) &= f^{abc-bc}(abc) - bc \\ &= (a + bc - f^{abc-a}(abc)) - bc \quad (\text{by (19)}) \\ &= a - f^{abc-a}(abc) \\ &= f^{abc-b}(abc) - b + f^{abc-c}(abc) - c \\ &= g(b) + g(c). \end{aligned}
This holds for any NN. In particular, fix any b2b \ge 2, and put N=(br(b+1)s)3N = (b^r(b+1)^s)^3, where r,sr, s are any relatively prime integers both greater than b+1b+1. Repeatedly using the multiplicative property of gg defined above, we get
rg(b)+sg(b+1)=g(br(b+1)s)=0. rg(b) + sg(b+1) = g(b^r(b+1)^s) = 0.
The only solution to this with integers g(b),g(b+1)g(b), g(b+1) satisfying g(b)bg(b) \ge -b and g(b+1)(b+1)g(b+1) \ge -(b+1) is g(b)=g(b+1)=0g(b) = g(b+1) = 0. Hence,
fNb(N)=b,fN(b+1)(N)=b+1 f^{N-b}(N) = b, \quad f^{N-(b+1)}(N) = b+1
and comparing gives f(b+1)=bf(b+1) = b, which is what we set out to prove.

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.