Maths Olympiad Prep

Library / /508 of 520

Algebra Difficulty 7.8 National olympiad, round 2 Find the answer

6. 135 Let NN be the set of all positive integers, and ff a function from NN to NN itself, such that for any ss and tt in NN, the following holds:
f(t2f(s))=s(f(t))2f\left(t^{2} f(s)\right)=s(f(t))^{2}

Determine the smallest possible value of f(1998)f(1998) among all such functions ff.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

(1)
Let t=1t=1, we get
f(f(s))=s(f(1))2f(f(s))=s(f(1))^{2}.
(2)
Let s=1s=1, substitute into (1) to get
f(t2(f(1))=(f(t))2f\left(t^{2}(f(1))=(f(t))^{2}\right..
(3)
Let f(1)=Kf(1)=K, then (2) and (3) become
f(f(s))=K2sf(f(s))=K^{2} s,
(4)
f(Kt2)=(f(t))2f\left(K t^{2}\right)=(f(t))^{2}
(5)
Let s=1s=1, substitute into (4) to get
f(K)=K2f(K)=K^{2}.
Let s=f(K)s=f(K), substitute into (1) to get
f(t2K3)=K2f(t)2f\left(t^{2} K^{3}\right)=K^{2} f(t)^{2}.
On the other hand, from (5) we have
f(t2K3)=f(K(Kt)2)=(f(Kt))2,f\left(t^{2} K^{3}\right)=f\left(K(K t)^{2}\right)=(f(K t))^{2},

Comparing the above two equations, we have
(f(Kt))2=K2(f(t))2f(Kt)=Kf(t)\begin{array}{l} (f(K t))^{2}=K^{2}(f(t))^{2} \\ f(K t)=K f(t) \end{array}

Substitute (6) into (5)
Kf(t2)=(f(t))2K f\left(t^{2}\right)=(f(t))^{2}

In the above equation, replace tt with t2,t4,,ttm1t^{2}, t^{4}, \cdots, t^{t^{m-1}}, respectively, to get
Kf(t4)=(f(t2))2Kf(t8)=(f(t4))2Kf(tmm)=(f(t2m1))2\begin{array}{l} K f\left(t^{4}\right)=\left(f\left(t^{2}\right)\right)^{2} \\ K f\left(t^{8}\right)=\left(f\left(t^{4}\right)\right)^{2} \\ \cdots \cdots \\ K f\left(t^{m^{m}}\right)=\left(f\left(t^{2^{m-1}}\right)\right)^{2} \end{array}

Square the first equation and compare with the second to get
K3f(t)4=(f(t))4,K^{3} f(t)^{4}=(f(t))^{4},

Square again and compare with the third equation to get
K7f(t8)=(f(t))8,K^{7} f\left(t^{8}\right)=(f(t))^{8},

Proceeding in this manner, we finally get
K2m1f(t2m)=(f(t))2mK^{2^{m}-1} f\left(t^{2^{m}}\right)=(f(t))^{2^{m}}

Here mm is any positive integer.
Take any prime factor pp of KK, and let pαK,pβf(t)p^{\alpha}\left\|K, p^{\beta}\right\| f(t).
From (7) we get
α(2m1)β2m\alpha\left(2^{m}-1\right) \leqslant \beta \cdot 2^{m}

Thus, βα2m12m\frac{\beta}{\alpha} \geqslant \frac{2^{m}-1}{2^{m}},
Taking the limit on both sides, we get \square
βαlimm2m12m=1,\frac{\beta}{\alpha} \geqslant \lim _{m \rightarrow \infty} \frac{2^{m}-1}{2^{m}}=1,

i.e., βα\beta \geqslant \alpha.
From the above inequality and the arbitrariness of pp, we know
Kf(t)K \mid f(t)

Thus, let
g(t)=f(t)K.g(t)=\frac{f(t)}{K} .

Clearly, g(t)g(t) is also a function from NN to NN.
From (6) and the definition of g(t)g(t), we have
f(t2f(s))=f(t2Kg(s))=Kf(t2g(s))=K2g(t2g(s))s(f(t))2=K2s(g(t))2\begin{aligned} f\left(t^{2} f(s)\right) & =f\left(t^{2} \cdot K g(s)\right) \\ & =K f\left(t^{2} g(s)\right)=K^{2} g\left(t^{2} g(s)\right) \\ s(f(t))^{2} & =K^{2} s(g(t))^{2} \end{aligned}

From (1) and the above two equations, we get
g(t2g(s))=s(g(t))2g\left(t^{2} g(s)\right)=s(g(t))^{2}

This shows that gg is also a function that satisfies the conditions of the problem, and g(1)=1g(1)=1. Therefore, all the results about the function ff apply to gg, with the note that K=g(1)=1K=g(1)=1.

From (4) and (5) we get
g(g(s))=sg(t2)=(g(t))2\begin{array}{l} g(g(s))=s \\ g\left(t^{2}\right)=(g(t))^{2} \end{array}
(9)
(10)
In (8), replace ss with g(s)g(s), we have
g(t2s)=g(s)(g(t))2g\left(t^{2} s\right)=g(s)(g(t))^{2}

Using (11) and (1), we know: for any a,bNa, b \in N,
(g(ab))2=g(a2b2)=g(a2)(g(b))2=(g(a))2(g(b))2\begin{aligned} (g(a b))^{2} & =g\left(a^{2} b^{2}\right) \\ & =g\left(a^{2}\right) \cdot(g(b))^{2}=(g(a))^{2} \cdot(g(b))^{2} \end{aligned}

i.e., g(ab)=g(a)g(b)g(a b)=g(a) \cdot g(b).
(11)

From (9), we know that gg is injective. In particular, for all a1a \neq 1, g(a)1g(a) \neq 1. From (12), we know that if aa is composite, then g(a)g(a) must be composite.
Also, from g(g(p))=pg(g(p))=p, we know that if pp is prime, then g(p)g(p) must be prime. Since 1998=2×33×371998=2 \times 3^{3} \times 37, we have
f(1998)=Kg(1998)=Kg(2)(g(3))3g(37)(2335)K=120K120\begin{aligned} f(1998) & =K g(1998)=K \cdot g(2) \cdot(g(3))^{3} \cdot g(37) \\ & \geqslant\left(2^{3} \cdot 3 \cdot 5\right) \cdot K=120 K \geqslant 120 \end{aligned}

On the other hand, define the function ff 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\begin{array}{l} f(1)=1 \\ f(2)=3 \\ f(3)=2, \\ f(5)=37 \\ f(37)=5 \\ f(p)=p \quad(p \text { is any other prime }) \\ f(n)=\left(f\left(p_{1}\right)\right)^{a_{1}} \cdot\left(f\left(p_{2}\right)\right)^{a_{2}} \cdots\left(f\left(p_{l}\right)\right)^{a_{l}} \end{array}

where the standard factorization of nn is n=p1a1p2a2p1a1n=p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \cdots p_{1}^{a_{1}}.
Under the above definition, it is easy to verify that such an ff satisfies the conditions of the problem, and f(1998)=120f(1998)=120.
In conclusion, the minimum value of f(1998)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.