Olympiad Maths Prep

Library / /17 of 29

Algebra Difficulty 6.4 National olympiad Prove it Iran

Find all functions f:NNf : \mathbb{N} \to \mathbb{N} such that for any distinct positive integers xx, yy, zz, x+y+zx + y + z is a perfect square if and only if f(x)+f(y)+f(z)f(x) + f(y) + f(z) is a perfect square.

Solution

Claim i. f(x)f(x) is injective.
Proof. Assume there exist two natural numbers x1x_1 and x2x_2 such that f(x1)=f(x2)f(x_1) = f(x_2) and x1x2x_1 \neq x_2. Now choose yy and zz such that y+z=t2x1y + z = t^2 - x_1 then we have
f(y)+f(z)+f(x1)=a2 f(y) + f(z) + f(x_1) = a^2
for some natural number aa. Therefore,
f(y)+f(z)+f(x1)=f(y)+f(z)+f(x2)=a2, f(y) + f(z) + f(x_1) = f(y) + f(z) + f(x_2) = a^2,
so y+z+x2y + z + x_2 must be square of some natural number ss. Hence
x1x2=t2s20 |x_1 - x_2| = |t^2 - s^2| \neq 0
and we have
t2s22t1. |t^2 - s^2| \geq 2|t| - 1.
If we choose tt large enough it gives us a contradiction.

Claim ii. For any x,yNx, y \in \mathbb{N} we have f(x+1)f(x)=f(y+1)f(y)f(x + 1) - f(x) = f(y + 1) - f(y).
Proof. Assume some arbitrary x0x_0 and y0y_0 with x02x_0 \geq 2, and choose z=t2x0y0z = t^2 - x_0 - y_0 for some large tt. Then
f(x0)+f(y0)+f(z)=a2, f(x_0) + f(y_0) + f(z) = a^2,
and
f(x01)+f(y0+1)+f(z)=b2. f(x_0 - 1) + f(y_0 + 1) + f(z) = b^2.
So we have
f(x0)+f(y0)f(x01)+f(y0+1)=a2b2. |f(x_0) + f(y_0) - f(x_0 - 1) + f(y_0 + 1)| = |a^2 - b^2|.
Assume that f(x0)+f(y0)f(x01)+f(y0+1)0f(x_0) + f(y_0) - f(x_0 - 1) + f(y_0 + 1) \neq 0. If we choose zz large enough, f(z)f(z) is a large number too (it's trivial because of the injectivity). But we know
f(x0)+f(y0)f(x01)+f(y0+1)=a2b22a1. |f(x_0) + f(y_0) - f(x_0 - 1) + f(y_0 + 1)| = |a^2 - b^2| \geq 2|a| - 1.
That means f(z)f(z) has an upper bound. Contradiction.

Claim ii implies that f(x)f(x) is a linear function so f(x)=ax+bf(x) = a x + b and
a(x+y+z)+3b, a(x + y + z) + 3b,
becomes a perfect-square if and only if
x+y+z, x + y + z,
does. That means at2+3ba t^2 + 3b is a perfect-square for any tNt \in \mathbb{N}. In particular a(at2+3b)+3b=t2a(a t^2 + 3b) + 3b = t'^2 hence
3ba+a=t2t2, 3ba + a = t'^2 - t^2,
which is a contradiction unless 3ba+3b=03ba + 3b = 0 (because the left hand side is either 0 or very big for big tt). Now obviously a>0a > 0 and we get b=0b = 0, a=n2a = n^2.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.