Maths Olympiad Prep

Library / /106 of 115

Algebra Difficulty 7.8 National olympiad, round 2 Find the answer

Find all functions f :Z+Z+f : \mathbb{Z}^+ \to \mathbb{Z}^+ (where Z+\mathbb{Z}^+ is the set of positive integers) such that f(n!)=f(n)!f(n!) = f(n)! for all positive integers nn and such that mnm - n divides f(m)f(n)f(m) - f(n) for all distinct positive integers mm , nn .

A number or a short expression. Spacing and $ signs are ignored.

Solution

By the first condition we have f(1)=f(1!)=f(1)!f(1)=f(1!)=f(1)! and f(2)=f(2!)=f(2)!f(2)=f(2!)=f(2)! , so f(1)=1f(1)=1 or 22 and similarly for f(2)f(2) . By the second condition, we have nn!=(n+1)!n!f(n+1)!f(n)!(1)n\cdot n!=(n+1)!-n! \mid f(n+1)!-f(n)! \qquad \qquad (1) for all positive integers nn .
Suppose that for some n2n \geq 2 we have f(n)=1f(n) = 1 . We claim that f(k)=1f(k)=1 for all knk\ge n . Indeed, from Equation (1) we have f(n+1)!1modnn!f(n+1)!\equiv 1 \mod n\cdot n! , and this is only possible if f(n+1)=1f(n+1)=1 ; the claim follows by induction.
We now divide into cases:
Case 1: f(1)=f(2)=1f(1)=f(2)=1
This gives f(n)=1f(n)=1 always from the previous claim, which is a solution.
Case 2: f(1)=2,f(2)=1f(1)=2, f(2)=1
This implies f(n)=1f(n)=1 for all n2n\ge 2 , but this does not satisfy the initial conditions. Indeed, we would have 31f(3)f(1)3-1 \mid f(3)-f(1) and so 212\mid -1 , a contradiction.
Case 3: f(1)=1f(1)=1 , f(2)=2f(2)=2
We claim f(n)=nf(n)=n always by induction. The base cases are n=1n = 1 and n=2n = 2 . Fix k>1k > 1 and suppose that f(k)=kf(k)=k . By Equation (1) we have that f(k+1)!k!modkk!.f(k+1)! \equiv k! \mod k\cdot k! . This implies f(k+1)<2kf(k+1)<2k (otherwise f(k+1)!0modkk!f(k+1)!\equiv 0 \mod k\cdot k! ). Also we have (k+1)1f(k+1)f(1)(k+1)-1 \mid f(k+1)-f(1) so f(k+1)1modkf(k+1)\equiv 1 \mod k . This gives the solutions f(k+1)=1f(k+1)=1 and f(k+1)=k+1f(k+1)=k+1 . The first case is obviously impossible, so f(k+1)=k+1f(k + 1) = k + 1 , as desired. By induction, f(n)=nf(n) = n for all nn . This also satisfies the requirements.
Case 4: f(1)=f(2)=2f(1)=f(2)=2
We claim f(n)=2f(n)=2 by a similar induction. Again if f(k)=2f(k)=2 , then by (1) we have f(k+1)2modkk!f(k+1)\equiv 2 \mod k\cdot k! and so f(k+1)<2kf(k+1)<2k . Also note that k+11f(k+1)2k+1-1 \mid f(k+1)-2 and k+12f(k+1)2k+1-2 \mid f(k+1)-2 so f(k+1)2modk(k1)f(k+1)\equiv 2 \mod k(k-1) . Then the only possible solution is f(k+1)=2f(k+1)=2 . By induction, f(n)=2f(n) = 2 for all nn , and this satisfies all requirements.
In summary, there are three solutions: f(n)=1,f(n)=2,f(n)=n\boxed{f(n)=1, f(n)=2, f(n)=n} .

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.