Problem

Source: 2022 China TST, Test 3 P5

Tags: number theory, Perfect Squares



Show that there exist constants $c$ and $\alpha > \frac{1}{2}$, such that for any positive integer $n$, there is a subset $A$ of $\{1,2,\ldots,n\}$ with cardinality $|A| \ge c \cdot n^\alpha$, and for any $x,y \in A$ with $x \neq y$, the difference $x-y$ is not a perfect square.