IMO 1998 Problem B3 Consider all functions f from the set of all positive integers into itself satisfying f(t 2 f(s)) = s f(t) 2 for all s and t. Determine the least possible value of f(1998).
120 Solution Let f(1) = k. Then f(kt 2 ) = f(t) 2 and f(f(t)) = k 2 t. Also f(kt) 2 = 1·f(kt) 2 = f(k 3 t 2 ) = f(1 2 f(f(kt 2 ))) = k 2 f(kt 2 ) = k 2 f(t) 2 . Hence f(kt) = k f(t). By an easy induction k n f(t n+1 ) = f(t) n+1 . But this implies that k divides f(t). For suppose the highest power of a prime p dividing k is a > b, the highest power of p dividing f(t). Then a > b(1 + 1/n) for some integer n. But then na > (n + 1)b, so k n does not divide f(t) n+1 . Contradiction. Let g(t) = f(t)/k. Then f(t 2 f(s)) = f(t 2 kg(s)) = k f(t 2 g(s) = k 2 g(t 2 g(s)), whilst s f(t) 2 = k 2 s f(t) 2 . So g(t 2 g(s)) = s g(t) 2 . Hence g is also a function satisfying the conditions which evidently has smaller values than f (for k > 1). It also satisfies g(1) = 1. Since we want the smallest possible value of f(1998) we may restrict attention to functions f satisfying f(1) = 1. Thus we have f(f(t) = t and f(t 2 ) = f(t) 2 . Hence f(st) 2 = f(s 2 t 2 ) = f(s 2 f(f(t 2 ))) = f(s) 2 f(t 2 ) = f(s) 2 f(t) 2 . So f(st) = f(s) f(t). Suppose p is a prime and f(p) = m·n. Then f(m)f(n) = f(mn) = f(f(p)) = p, so one of f(m), f(n) = 1. But if f(m) = 1, then m = f(f(m)) = f(1) = 1. So f(p) is prime. If f(p) = q, then f(q) = p. Now we may define f arbitarily on the primes subject only to the conditions that each f(prime) is prime and that if f(p) = q, then f(q) = p. For suppose that s = p 1 a 1 ...p r a r and that f(p i ) = q i . If t has any additional prime factors not included in the q i , then we may add additional p's to the expression for s so that they are included (taking the additional a's to be zero). So suppose t = q 1 b 1 ...q r b r .Then t 2 f(s) = q 1 2b 1 +a 1 ...q r 2b r +a r and hence f(t 2 f(s) = p 1 2b 1 +a 1 ...p r 2b r +a r = s f(t) 2 . We want the minimum possible value of f(1998). Now 1998 = 2.3 3 .37, so we achieve the minimum value by taking f(2) = 3, f(3) = 2, f(37) = 5 (and f(37) = 5). This gives f(1998) = 3·2 3 5 = 120. 39th IMO 1998 © John Scholes jscholes@kalva.demon.co.uk 26 Oct 1998 Last corrected/updated 20 Aug 03