CN-TST 2022 Problem 17

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.