IMO Shortlist, 2016

We first prove the following preliminary result.
- Claim. For fixed $k$, let $x, y$ be integers satisfying (1). Then the numbers $x_{1}, y_{1}$ defined by
$$x_{1} = \frac{1}{2}\left(x - y + \frac{(x - y)^{2} - 4a}{x + y}\right), \quad y_{1} = \frac{1}{2}\left(x - y - \frac{(x - y)^{2} - 4a}{x + y}\right)$$
are integers and satisfy (1) (with $x, y$ replaced by $x_{1}, y_{1}$ respectively).

Proof. Since $x_{1} + y_{1} = x - y$ and
$$x_{1} = \frac{x^{2} - x y - 2a}{x + y} = -x + \frac{2(x^{2} - a)}{x + y} = -x + 2k(x - y),$$
both $x_{1}$ and $y_{1}$ are integers. Let $u = x + y$ and $v = x - y$. The relation (1) can be rewritten as
$$u^{2} - (4k - 2) u v + (v^{2} - 4a) = 0$$
By Vieta's Theorem, the number $z = \frac{v^{2} - 4a}{u}$ satisfies
$$v^{2} - (4k - 2) v z + (z^{2} - 4a) = 0$$
Since $x_{1}$ and $y_{1}$ are defined so that $v = x_{1} + y_{1}$ and $z = x_{1} - y_{1}$, we can reverse the process and verify (1) for $x_{1}, y_{1}$.

We first show that $B \subset A$. Take any $k \in B$ so that (1) is satisfied for some integers $x, y$ with $0 \leqslant x < \sqrt{a}$. Clearly, $y \neq 0$ and we may assume $y$ is positive. Since $a$ is not a square, we have $k > 1$. Hence, we get $0 \leqslant x < y < \sqrt{a}$. Define
$$x_{1} = \frac{1}{2}\left|x - y + \frac{(x - y)^{2} - 4a}{x + y}\right|, \quad y_{1} = \frac{1}{2}\left(x - y - \frac{(x - y)^{2} - 4a}{x + y}\right).$$
By the Claim, $x_{1}, y_{1}$ are integers satisfying (1). Also, we have
$$x_{1} \geqslant -\frac{1}{2}\left(x - y + \frac{(x - y)^{2} - 4a}{x + y}\right) = \frac{2a + x(y - x)}{x + y} \geqslant \frac{2a}{x + y} > \sqrt{a}.$$
This implies $k \in A$ and hence $B \subset A$.

Next, we shall show that $A \subset B$. Take any $k \in A$ so that (1) is satisfied for some integers $x, y$ with $x > \sqrt{a}$. Again, we may assume $y$ is positive. Among all such representations of $k$, we choose the one with smallest $x + y$. Define
$$x_{1} = \frac{1}{2}\left|x - y + \frac{(x - y)^{2} - 4a}{x + y}\right|, \quad y_{1} = \frac{1}{2}\left(x - y - \frac{(x - y)^{2} - 4a}{x + y}\right).$$
By the Claim, $x_{1}, y_{1}$ are integers satisfying (1). Since $k > 1$, we get $x > y > \sqrt{a}$. Therefore, we have $y_{1} > \frac{4a}{x + y} > 0$ and $\frac{4a}{x + y} < x + y$. It follows that
$$x_{1} + y_{1} \leqslant \max \left\{x - y, \frac{4a - (x - y)^{2}}{x + y}\right\} < x + y$$
If $x_{1} > \sqrt{a}$, we get a contradiction due to the minimality of $x + y$. Therefore, we must have $0 \leqslant x_{1} < \sqrt{a}$, which means $k \in B$ so that $A \subset B$.

The two subset relations combine to give $A = B$.

The relation (1) is equivalent to
$$k y^{2} - (k - 1) x^{2} = a$$
Motivated by Pell's Equation, we prove the following, which is essentially the same as the Claim in Solution 1.
- Claim. If $(x_{0}, y_{0})$ is a solution to (2), then $((2k - 1)x_{0} \pm 2k y_{0}, (2k - 1)y_{0} \pm 2(k - 1)x_{0})$ is also a solution to (2).

Proof. We check directly that
$$\begin{aligned} & k\left((2k - 1)y_{0} \pm 2(k - 1)x_{0}\right)^{2} - (k - 1)\left((2k - 1)x_{0} \pm 2k y_{0}\right)^{2} \\ = & \left(k(2k - 1)^{2} - (k - 1)(2k)^{2}\right) y_{0}^{2} + \left(k(2(k - 1))^{2} - (k - 1)(2k - 1)^{2}\right) x_{0}^{2} \\ = & k y_{0}^{2} - (k - 1) x_{0}^{2} = a. \end{aligned}$$
If (2) is satisfied for some $0 \leqslant x < \sqrt{a}$ and nonnegative integer $y$, then clearly (1) implies $y > x$. Also, we have $k > 1$ since $a$ is not a square number. By the Claim, consider another solution to (2) defined by
$$x_{1} = (2k - 1)x + 2k y, \quad y_{1} = (2k - 1)y + 2(k - 1)x.$$
It satisfies $x_{1} \geqslant (2k - 1)x + 2k(x + 1) = (4k - 1)x + 2k > x$. Then we can replace the old solution by a new one which has a larger value in $x$. After a finite number of replacements, we must get a solution with $x > \sqrt{a}$. This shows $B \subset A$.

If (2) is satisfied for some $x > \sqrt{a}$ and nonnegative integer $y$, by the Claim we consider another solution to (2) defined by
$$x_{1} = |(2k - 1)x - 2k y|, \quad y_{1} = (2k - 1)y - 2(k - 1)x.$$
From (2), we get $\sqrt{k} y > \sqrt{k - 1} x$. This implies $k y > \sqrt{k(k - 1)} x > (k - 1)x$ and hence $(2k - 1)x - 2k y < x$. On the other hand, the relation (1) implies $x > y$. Then it is clear that $(2k - 1)x - 2k y > -x$. These combine to give $x_{1} < x$, which means we have found a solution to (2) with $x$ having a smaller absolute value. After a finite number of steps, we shall obtain a solution with $0 \leqslant x < \sqrt{a}$. This shows $A \subset B$.

The desired result follows from $B \subset A$ and $A \subset B$.

It suffices to show $A \cup B$ is a subset of $A \cap B$. We take any $k \in A \cup B$, which means there exist integers $x, y$ satisfying (1). Since $a$ is not a square, it follows that $k \neq 1$. As in Solution 2, the result follows readily once we have proved the existence of a solution ($x_{1}, y_{1}$) to (1) with $|x_{1}| > |x|$, and, in case of $x > \sqrt{a}$, another solution ($x_{2}, y_{2}$) with $|x_{2}| < |x|$.

Without loss of generality, assume $x, y \geqslant 0$. Let $u = x + y$ and $v = x - y$. Then $u \geqslant v$ and (1) becomes
$$k = \frac{(u + v)^{2} - 4a}{4u v}$$
This is the same as
$$v^{2} + (2u - 4k u)v + u^{2} - 4a = 0$$
Let $v_{1} = 4k u - 2u - v$. Then $u + v_{1} = 4k u - u - v \geqslant 8u - u - v > u + v$. By Vieta's Theorem, $v_{1}$ satisfies
$$v_{1}^{2} + (2u - 4k u)v_{1} + u^{2} - 4a = 0$$
This gives $k = \frac{(u + v_{1})^{2} - 4a}{4u v_{1}}$. As $k$ is an integer, $u + v_{1}$ must be even. Therefore, $x_{1} = \frac{u + v_{1}}{2}$ and $y_{1} = \frac{v_{1} - u}{2}$ are integers. By reversing the process, we can see that $(x_{1}, y_{1})$ is a solution to (1), with $x_{1} = \frac{u + v_{1}}{2} > \frac{u + v}{2} = x \geqslant 0$. This completes the first half of the proof.

Suppose $x > \sqrt{a}$. Then $u + v > 2\sqrt{a}$ and (3) can be rewritten as
$$u^{2} + (2v - 4k v)u + v^{2} - 4a = 0$$
Let $u_{2} = 4k v - 2v - u$. By Vieta's Theorem, we have $u u_{2} = v^{2} - 4a$ and
$$u_{2}^{2} + (2v - 4k v)u_{2} + v^{2} - 4a = 0$$
By $u > 0, u + v > 2\sqrt{a}$ and (3), we have $v > 0$. If $u_{2} \geqslant 0$, then $v u_{2} \leqslant u u_{2} = v^{2} - 4a < v^{2}$. This shows $u_{2} < v \leqslant u$ and $0 < u_{2} + v < u + v$. If $u_{2} < 0$, then $(u_{2} + v) + (u + v) = 4k v > 0$ and $u_{2} + v < u + v$ imply $|u_{2} + v| < u + v$. In any case, since $u_{2} + v$ is even from (4), we can define $x_{2} = \frac{u_{2} + v}{2}$ and $y_{2} = \frac{u_{2} - v}{2}$ so that (1) is satisfied with $|x_{2}| < x$, as desired. The proof is thus complete.