Maths Olympiad Prep

Library / /2 of 27

Algebra Difficulty 4.6 AIME Prove it Croatia

Let f:N→Nf: N \to N be a function such that
f(ab)=f(a+b) f(ab) = f(a+b)
for all positive integers a≥4a \ge 4 and b≥4b \ge 4.
Prove that f(n)=f(8)f(n) = f(8) for all positive integers n≥8n \ge 8.

Solution

Let n≥8n \ge 8 be a positive integer. The problem condition implies that
f(n)=f(4+(n−4))=f(4(n−4))=f(2(n−4)+2(n−4))=f(4(n−4)(n−4))=f(4(n−4)+(n−4))=f(5(n−4))=f(5+n−4)=f(n+1). \begin{aligned} f(n) &= f(4 + (n-4)) = f(4(n-4)) = f(2(n-4) + 2(n-4)) \\ &= f(4(n-4)(n-4)) = f(4(n-4) + (n-4)) \\ &= f(5(n-4)) = f(5 + n - 4) \\ &= f(n+1). \end{aligned}
Therefore, by the principle of mathematical induction, we conclude that f(n)=f(8)f(n) = f(8) for all n≥8n \ge 8.

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 and solution reproduced as published; topic and difficulty added by this site.