IMO 1979 SL 21

Origin: USS

Problem

Let N be the number of integral solutions of the equation x2 −y2 = z3 −t3 satisfying the condition 0 \leqx, y, z, t \leq106, and let M be the number of integral solutions of the equation x2 −y2 = z3 −t3 + 1 satisfying the condition 0 \leqx, y, z, t \leq106. Prove that N > M.

Solution

Let f(n) be the number of different ways n \inN can be expressed as x2+y3 where x, y \in{0, 1, . . ., 106}. Clearly f(n) = 0 for n < 0 or n > 1012+1018. The first equation can be written as x2 + t3 = y2 + z3 = n, whereas the second equation can be written as x2 + t3 = n + 1, y2 + z3 = n. Hence we obtain the following formulas for M and N: M = m  i=0 f(i)2, N = m−1  i=0 f(i)f(i + 1) . Using the AM–GM inequality we get N = m−1  i=0 f(i)f(i + 1) \leq m−1  i=0 f(i)2 + f(i + 1)2 = f(0)2 + m−1  i=1 f(i)2 + f(m)2 < M . The last inequality is strong, since f(0) = 1 > 0. This completes our proof.