IMO 2012 Shortlist A1

Category: Algebra

Problem

Find all the functions f : Z → Z such that f(a)2

f(b)2
f(c)2 = 2f(a)f(b) + 2f(b)f(c) + 2f(c)f(a) for all integers a, b, c satisfying a + b + c = 0. Solution. The substitution a = b = c = 0 gives 3f(0)2 = 6f(0)2 , hence f(0) = 0. (1) The substitution b = −a and c = 0 gives ((f(a) − f(−a))2 = 0. Hence f is an even function: f(a) = f(−a) for all a ∈ Z. (2) Now set b = a and c = −2a to obtain 2f(a)2
f(2a)2 = 2f(a)2
4f(a)f(2a). Hence f(2a) = 0 or f(2a) = 4f(a) for all a ∈ Z. (3) If f(r) = 0 for some r ≥ 1 then the substitution b = r and c = −a−r gives (f(a+r)−f(a))2 = 0. So f is periodic with period r, i. e. f(a + r) = f(a) for all a ∈ Z. In particular, if f(1) = 0 then f is constant, thus f(a) = 0 for all a ∈ Z. This function clearly satisfies the functional equation. For the rest of the analysis, we assume f(1) = k 6= 0. By (3) we have f(2) = 0 or f(2) = 4k. If f(2) = 0 then f is periodic of period 2, thus f(even) = 0 and f(odd) = k. This function is a solution for every k. We postpone the verification; for the sequel assume f(2) = 4k 6= 0. By (3) again, we have f(4) = 0 or f(4) = 16k. In the first case f is periodic of period 4, and f(3) = f(−1) = f(1) = k, so we have f(4n) = 0, f(4n+1) = f(4n+3) = k, and f(4n+2) = 4k for all n ∈ Z. This function is a solution too, which we justify later. For the rest of the analysis, we assume f(4) = 16k 6= 0. We show now that f(3) = 9k. In order to do so, we need two substitutions: a = 1,b = 2,c = −3 =⇒ f(3)2 − 10kf(3) + 9k2 = 0 =⇒ f(3) ∈ {k,9k}, a = 1,b = 3,c = −4 =⇒ f(3)2 − 34kf(3) + 225k2 = 0 =⇒ f(3) ∈ {9k,25k}. Therefore f(3) = 9k, as claimed. Now we prove inductively that the only remaining function is f(x) = kx2 , x ∈ Z. We proved this for x = 0,1,2,3,4. Assume that n ≥ 4 and that f(x) = kx2 holds for all integers x ∈ [0,n]. Then the substitutions a = n, b = 1, c = −n−1 and a = n−1, b = 2, c = −n − 1 lead respectively to f(n + 1) ∈ {k(n + 1)2 ,k(n − 1)2 } and f(n + 1) ∈ {k(n + 1)2 ,k(n − 3)2 }. Since k(n − 1)2 6= k(n − 3)2 for n 6= 2, the only possibility is f(n + 1) = k(n + 1)2 . This completes the induction, so f(x) = kx2 for all x ≥ 0. The same expression is valid for negative values of x since f is even. To verify that f(x) = kx2 is actually a solution, we need to check the identity a4
b4
(a + b)4 = 2a2 b2
2a2 (a + b)2
2b2 (a + b)2 , which follows directly by expanding both sides.9 Therefore the only possible solutions of the functional equation are the constant function f1(x) = 0 and the following functions: f2(x) = kx2 f3(x) = 0 x even k x odd f4(x) =    0 x ≡ 0 (mod 4) k x ≡ 1 (mod 2) 4k x ≡ 2 (mod 4) for any non-zero integer k. The verification that they are indeed solutions was done for the first two. For f3 note that if a + b + c = 0 then either a,b,c are all even, in which case f(a) = f(b) = f(c) = 0, or one of them is even and the other two are odd, so both sides of the equation equal 2k2 . For f4 we use similar parity considerations and the symmetry of the equation, which reduces the verification to the triples (0,k,k), (4k,k,k), (0,0,0), (0,4k,4k). They all satisfy the equation. Comment. We used several times the same fact: For any a,b ∈ Z the functional equation is a quadratic equation in f(a + b) whose coefficients depend on f(a) and f(b): f(a + b)2 − 2(f(a) + f(b))f(a + b) + (f(a) − f(b))2 = 0. Its discriminant is 16f(a)f(b). Since this value has to be non-negative for any a,b ∈ Z, we conclude that either f or −f is always non-negative. Also, if f is a solution of the functional equation, then −f is also a solution. Therefore we can assume f(x) ≥ 0 for all x ∈ Z. Now, the two solutions of the quadratic equation are f(a + b) ∈ p f(a) + p f(b) 2 , p f(a) − p f(b) 2 for all a,b ∈ Z. The computation of f(3) from f(1), f(2) and f(4) that we did above follows immediately by setting (a,b) = (1,2) and (a,b) = (1,−4). The inductive step, where f(n+ 1) is derived from f(n), f(n− 1), f(2) and f(1), follows immediately using (a,b) = (n,1) and (a,b) = (n − 1,2).10