AlgebraDifficulty 7.8National olympiad, round 2Find the answer
6. 135 Let N be the set of all positive integers, and f a function from N to N itself, such that for any s and t in N, the following holds: f(t2f(s))=s(f(t))2
Determine the smallest possible value of f(1998) among all such functions f.
A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.
Solution
(1) Let t=1, we get f(f(s))=s(f(1))2. (2) Let s=1, substitute into (1) to get f(t2(f(1))=(f(t))2. (3) Let f(1)=K, then (2) and (3) become f(f(s))=K2s, (4) f(Kt2)=(f(t))2 (5) Let s=1, substitute into (4) to get f(K)=K2. Let s=f(K), substitute into (1) to get f(t2K3)=K2f(t)2. On the other hand, from (5) we have f(t2K3)=f(K(Kt)2)=(f(Kt))2,
Comparing the above two equations, we have (f(Kt))2=K2(f(t))2f(Kt)=Kf(t)
Substitute (6) into (5) Kf(t2)=(f(t))2
In the above equation, replace t with t2,t4,⋯,ttm−1, respectively, to get Kf(t4)=(f(t2))2Kf(t8)=(f(t4))2⋯⋯Kf(tmm)=(f(t2m−1))2
Square the first equation and compare with the second to get K3f(t)4=(f(t))4,
Square again and compare with the third equation to get K7f(t8)=(f(t))8,
Proceeding in this manner, we finally get K2m−1f(t2m)=(f(t))2m
Here m is any positive integer. Take any prime factor p of K, and let pαK,pβf(t). From (7) we get α(2m−1)⩽β⋅2m
Thus, αβ⩾2m2m−1, Taking the limit on both sides, we get □ αβ⩾m→∞lim2m2m−1=1,
i.e., β⩾α. From the above inequality and the arbitrariness of p, we know K∣f(t)
Thus, let g(t)=Kf(t).
Clearly, g(t) is also a function from N to N. From (6) and the definition of g(t), we have f(t2f(s))s(f(t))2=f(t2⋅Kg(s))=Kf(t2g(s))=K2g(t2g(s))=K2s(g(t))2
From (1) and the above two equations, we get g(t2g(s))=s(g(t))2
This shows that g is also a function that satisfies the conditions of the problem, and g(1)=1. Therefore, all the results about the function f apply to g, with the note that K=g(1)=1.
From (4) and (5) we get g(g(s))=sg(t2)=(g(t))2 (9) (10) In (8), replace s with g(s), we have g(t2s)=g(s)(g(t))2
Using (11) and (1), we know: for any a,b∈N, (g(ab))2=g(a2b2)=g(a2)⋅(g(b))2=(g(a))2⋅(g(b))2
i.e., g(ab)=g(a)⋅g(b). (11)
From (9), we know that g is injective. In particular, for all a=1, g(a)=1. From (12), we know that if a is composite, then g(a) must be composite. Also, from g(g(p))=p, we know that if p is prime, then g(p) must be prime. Since 1998=2×33×37, we have f(1998)=Kg(1998)=K⋅g(2)⋅(g(3))3⋅g(37)⩾(23⋅3⋅5)⋅K=120K⩾120
On the other hand, define the function f as follows: f(1)=1f(2)=3f(3)=2,f(5)=37f(37)=5f(p)=p(p is any other prime )f(n)=(f(p1))a1⋅(f(p2))a2⋯(f(pl))al
where the standard factorization of n is n=p1a1⋅p2a2⋯p1a1. Under the above definition, it is easy to verify that such an f satisfies the conditions of the problem, and f(1998)=120. In conclusion, the minimum value of f(1998) is 120.
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: NuminaMath-1.5,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.