Progetto Olimpiadi della Matematica

Solution:

The answer is $37$. Suppose $x = y$. Then we get $x^2 + 1$ even, hence $x$ odd. But $2x$ with $x$ odd is a power of two if and only if $x = 1$.

Now we just need to count all the pairs $(x, y)$ that satisfy the hypotheses with $x < y$. This means that there exist two positive integers $a$ and $b$ such that $x + y = 2^a$ and $x y + 1 = 2^b$. Since $(x-1)(y-1) \geq 0$, we have $b \geq a$.

From the second equation we deduce that both numbers are odd, so there exists an odd $k$ such that $x = 2^{a-1} - k$ and $y = 2^{a-1} + k$. Substituting into the second equation we obtain $2^{2a-2} - k^2 + 1 = 2^b$. Since $k = 2m + 1$ we have $4m(m+1) = 2^{2a-2} - 2^b = 2^b (2^{2a-2-b} - 1)$ which implies $m(m+1) = 2^{b-2}(2^{2a-2-b} - 1)$.

At this point if $m = 0$ we get that the pairs of the form $(2^{a-1} - 1, 2^{a-1} + 1)$, together with their symmetric counterparts, satisfy the requirements. They number $2 \cdot 10 = 20$, because the exponents $a$ between $2$ and $11$ work.

Alternatively we have $m \geq 1$. The factors $m$ and $m+1$ are coprime, so one of the two is divisible by $2^{b-2}$. In both cases we have that $m \geq 2^{b-2} - 1$. But then $2^{b-2}(2^{2a-2-b} - 1) = m(m+1) \geq 2^{b-2}(2^{b-2} - 1)$ and thus $2a-2-b \geq b-2$ which implies $a \geq b$. But we had already observed that $b \geq a$, hence $a = b$, that is $(x-1)(y-1) = 0$ and so the pairs are of the type $(1, 2^a - 1)$, together with their symmetric counterparts. They are $2 \cdot 10 - 1 = 19$, since the exponents $a$ between $1$ and $10$ work, but we must count $(1, 1)$ only once, hence the $-1$.

However we must be careful that we have counted some solutions both in this family and in the previous one, namely $(1, 3)$ and $(3, 1)$. The total number of pairs satisfying the requirements is therefore $20 + 19 - 2 = 37$.