IMO 2016 Shortlisted Problems

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),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-xy-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)uv+(v^2-4a)=0$$ By Vieta's Theorem, the number $z=\frac{v^2-4a}{u}$ satisfies $$v^2-(4k-2)vz+(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⩽x<\sqrt{a}$. Clearly, $y\ne 0$ and we may assume $y$ is positive. Since $a$ is not a square, we have $k>1$. Hence, we get $0⩽x<y<\sqrt{a}$. Define $$x_1=\frac{1}{2}\left|x-y+\frac{(x-y{)}^2-4a}{x+y}\right|,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⩾-\frac{1}{2}\left(x-y+\frac{(x-y{)}^2-4a}{x+y}\right)=\frac{2a+x(y-x)}{x+y}⩾\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|,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⩽\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⩽x_1<\sqrt{a}$, which means $k\in B$ so that $A\subset B$.

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

---

Alternative solution.

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{array}{rl}& 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{array}$$ If (2) is satisfied for some $0⩽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+2ky,y_1=(2k-1)y+2(k-1)x.$$ It satisfies $x_1⩾(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-2ky|,y_1=(2k-1)y-2(k-1)x.$$ From (2), we get $\sqrt{k}y>\sqrt{k-1}x$. This implies $ky>\sqrt{k(k-1)}x>(k-1)x$ and hence $(2k-1)x-2ky<x$. On the other hand, the relation (1) implies $x>y$. Then it is clear that $(2k-1)x-2ky>-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⩽x<\sqrt{a}$. This shows $A\subset B$.

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

---

Alternative solution.

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\ne 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⩾0$. Let $u=x+y$ and $v=x-y$. Then $u⩾v$ and (1) becomes $$k=\frac{(u+v{)}^2-4a}{4uv}$$ This is the same as $$v^2+(2u-4ku)v+u^2-4a=0$$ Let $v_1=4ku-2u-v$. Then $u+v_1=4ku-u-v⩾8u-u-v>u+v$. By Vieta's Theorem, $v_1$ satisfies $$v_1^2+(2u-4ku)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⩾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-4kv)u+v^2-4a=0$$ Let $u_2=4kv-2v-u$. By Vieta's Theorem, we have $u{u}_2=v^2-4a$ and $$u_2^2+(2v-4kv)u_2+v^2-4a=0$$ By $u>0,u+v>2\sqrt{a}$ and (3), we have $v>0$. If $u_2⩾0$, then $v{u}_2⩽u{u}_2=v^2-4a<v^2$. This shows $u_2<v⩽u$ and $0<u_2+v<u+v$. If $u_2<0$, then $(u_2+v)+(u+v)=4kv>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.