IMO 2019 Shortlisted Problems

First, observe that if $n$ is a positive integer, then $n\in H$ exactly when $$\left\{\frac{n}{\sqrt{2}}\right\}>1-\frac{1}{\sqrt{2}}\text{\hspace{1em}(1)}$$ To see why, observe that $n\in H$ if and only if $0<i\sqrt{2}-n<1$ for some $i\in {\mathbb{Z}}_{>0}$. In other words, $0<i-n/\sqrt{2}<1/\sqrt{2}$, which is equivalent to (1).

Now, write $A=\{a_1<a_2<\cdots <a_k\}$, where $k=|A|$. Observe that the set of differences is not altered by shifting $A$, so we may assume that $A\subseteq \{0,1,\dots ,n-1\}$ with $a_1=0$.

From (1), we learn that $\left\{a_i/\sqrt{2}\right\}<1-1/\sqrt{2}$ for each $i>1$ since $a_i-a_1\notin H$. Furthermore, we must have $\left\{a_i/\sqrt{2}\right\}<\left\{a_j/\sqrt{2}\right\}$ whenever $i<j$; otherwise, we would have $$-\left(1-\frac{1}{\sqrt{2}}\right)<\left\{\frac{a_j}{\sqrt{2}}\right\}-\left\{\frac{a_i}{\sqrt{2}}\right\}<0$$ Since $\left\{\left(a_j-a_i\right)/\sqrt{2}\right\}=\left\{a_j/\sqrt{2}\right\}-\left\{a_i/\sqrt{2}\right\}+1$, this implies that $\left\{\left(a_j-a_i\right)/\sqrt{2}\right\}>1/\sqrt{2}>1-1/\sqrt{2}$, contradicting (1).

Now, we have a sequence $0=a_1<a_2<\cdots <a_k<n$, with $$0=\left\{\frac{a_1}{\sqrt{2}}\right\}<\left\{\frac{a_2}{\sqrt{2}}\right\}<\cdots <\left\{\frac{a_k}{\sqrt{2}}\right\}<1-\frac{1}{\sqrt{2}}$$ We use the following fact: for any $d\in \mathbb{Z}$, we have $$\left\{\frac{d}{\sqrt{2}}\right\}>\frac{1}{2d\sqrt{2}}\text{\hspace{1em}(2)}$$ To see why this is the case, let $h=\lfloor d/\sqrt{2}\rfloor$, so $\{d/\sqrt{2}\}=d/\sqrt{2}-h$. Then $$\left\{\frac{d}{\sqrt{2}}\right\}\left(\frac{d}{\sqrt{2}}+h\right)=\frac{d^2-2h^2}{2}⩾\frac{1}{2}$$ since the numerator is a positive integer. Because $d/\sqrt{2}+h<2d/\sqrt{2}$, inequality (2) follows.

Let $d_i=a_{i+1}-a_i$, for $1⩽i<k$. Then $\left\{a_{i+1}/\sqrt{2}\right\}-\left\{a_i/\sqrt{2}\right\}=\left\{d_i/\sqrt{2}\right\}$, and we have $$1-\frac{1}{\sqrt{2}}>\sum _i\left\{\frac{d_i}{\sqrt{2}}\right\}>\frac{1}{2\sqrt{2}}\sum _i\frac{1}{d_i}⩾\frac{(k-1{)}^2}{2\sqrt{2}}\frac{1}{{\sum }_i{d}_i}>\frac{(k-1{)}^2}{2\sqrt{2}}\cdot \frac{1}{n}.\text{\hspace{1em}(3)}$$ Here, the first inequality holds because $\left\{a_k/\sqrt{2}\right\}<1-1/\sqrt{2}$, the second follows from (2), the third follows from an easy application of the AM-HM inequality (or Cauchy-Schwarz), and the fourth follows from the fact that ${\sum }_i{d}_i=a_k<n$.

Rearranging this, we obtain $$\sqrt{2\sqrt{2}-2}\cdot \sqrt{n}>k-1$$ which provides the required bound on $k$.

---

Alternative solution.

Let $\alpha =2+\sqrt{2}$, so $(1/\alpha )+(1/\sqrt{2})=1$. Thus, $J=\{\lfloor i\alpha \rfloor :i\in {\mathbb{Z}}_{>0}\}$ is the complementary Beatty sequence to $H$ (in other words, $H$ and $J$ are disjoint with $H\cup J={\mathbb{Z}}_{>0}$ ). Write $A=\{a_1<a_2<\cdots <a_k\}$. Suppose that $A$ has no differences in $H$, so all its differences are in $J$ and we can set $a_i-a_1=\lfloor \alpha b_i\rfloor$ for $b_i\in {\mathbb{Z}}_{>0}$.

For any $j>i$, we have $a_j-a_i=\lfloor \alpha b_j\rfloor -\lfloor \alpha b_i\rfloor$. Because $a_j-a_i\in J$, we also have $a_j-a_i=\lfloor \alpha t\rfloor$ for some positive integer $t$. Thus, $\lfloor \alpha t\rfloor =\lfloor \alpha b_j\rfloor -\lfloor \alpha b_i\rfloor$. The right hand side must equal either $\lfloor \alpha (b_j-b_i)\rfloor$ or $\lfloor \alpha (b_j-b_i)\rfloor -1$, the latter of which is not a member of $J$ as $\alpha >2$. Therefore, $t=b_j-b_i$ and so we have $\lfloor \alpha b_j\rfloor -\lfloor \alpha b_i\rfloor =\lfloor \alpha (b_j-b_i)\rfloor$.

For $1⩽i<k$ we now put $d_i=b_{i+1}-b_i$, and we have $$\lfloor \alpha \sum _i{d}_i\rfloor =\lfloor \alpha b_k\rfloor =\sum _i\lfloor \alpha d_i\rfloor$$ that is, ${\sum }_i\{\alpha d_i\}<1$. We also have $$1+\lfloor \alpha \sum _i{d}_i\rfloor =1+a_k-a_1⩽a_k⩽n$$ so ${\sum }_i{d}_i⩽n/\alpha$.

With the above inequalities, an argument similar to (3) (which uses the fact that $\{\alpha d\}=\{d\sqrt{2}\}>1/(2d\sqrt{2})$ for positive integers $d$ ) proves that $1>\left((k-1{)}^2/(2\sqrt{2})\right)(\alpha /n)$, which again rearranges to give $$\sqrt{2\sqrt{2}-2}\cdot \sqrt{n}>k-1$$

---

Alternative solution.

Again, define $J={\mathbb{Z}}_{>0}\backslash H$, so all differences between elements of $A$ are in $J$. We start by making the following observation. Suppose we have a set $B\subseteq \{1,2,\dots ,n\}$ such that all of the differences between elements of $B$ are in $H$. Then $|A|\cdot |B|⩽2n$.

To see why, observe that any two sums of the form $a+b$ with $a\in A,b\in B$ are different; otherwise, we would have $a_1+b_1=a_2+b_2$, and so $|a_1-a_2|=|b_2-b_1|$. However, then the left hand side is in $J$ whereas the right hand side is in $H$. Thus, $\{a+b:a\in A,b\in B\}$ is a set of size $|A|\cdot |B|$ all of whose elements are no greater than $2n$, yielding the claimed inequality.

With this in mind, it suffices to construct a set $B$, all of whose differences are in $H$ and whose size is at least $C^{\prime }\sqrt{n}$ for some constant $C^{\prime }>0$.

To do so, we will use well-known facts about the negative Pell equation $X^2-2Y^2=-1$; in particular, that there are infinitely many solutions and the values of $X$ are given by the recurrence $X_1=1,X_2=7$ and $X_m=6X_{m-1}-X_{m-2}$. Therefore, we may choose $X$ to be a solution with $\sqrt{n}/6<X⩽\sqrt{n}$.

Now, we claim that we may choose $B=\{X,2X,\dots ,\lfloor (1/3)\sqrt{n}\rfloor X\}$. Indeed, we have $$\left(\frac{X}{\sqrt{2}}-Y\right)\left(\frac{X}{\sqrt{2}}+Y\right)=\frac{-1}{2}$$ and so $$0>\left(\frac{X}{\sqrt{2}}-Y\right)⩾\frac{-3}{\sqrt{2n}},$$ from which it follows that $\{X/\sqrt{2}\}>1-(3/\sqrt{2n})$. Combined with (1), this shows that all differences between elements of $B$ are in $H$.

---

Alternative solution.

As in Solution 3, we will provide a construction of a large set $B\subseteq \{1,2,\dots ,n\}$, all of whose differences are in $H$.

Choose $Y$ to be a solution to the Pell-like equation $X^2-2Y^2=\pm 1$; such solutions are given by the recurrence $Y_1=1,Y_2=2$ and $Y_m=2Y_{m-1}+Y_{m-2}$, and so we can choose $Y$ such that $n/(3\sqrt{2})<Y⩽n/\sqrt{2}$. Furthermore, it is known that for such a $Y$ and for $1⩽x<Y$, $$\{x\sqrt{2}\}+\{(Y-x)\sqrt{2}\}=\{Y/\sqrt{2}\}\text{\hspace{1em}(4)}$$ if $X^2-2Y^2=1$, and $$\{x\sqrt{2}\}+\{(Y-x)\sqrt{2}\}=1+\{Y/\sqrt{2}\}\text{\hspace{1em}(5)}$$ if $X^2-2Y^2=-1$. Indeed, this is a statement of the fact that $X/Y$ is a best rational approximation to $\sqrt{2}$, from below in the first case and from above in the second.

Now, consider the sequence $\{\sqrt{2}\},\{2\sqrt{2}\},\dots ,\{(Y-1)\sqrt{2}\}$. The Erdős-Szekeres theorem tells us that this sequence has a monotone subsequence with at least $\sqrt{Y-2}+1>\sqrt{Y}$ elements; if that subsequence is decreasing, we may reflect (using (4) or (5)) to ensure that it is increasing. Call the subsequence $\{y_1\sqrt{2}\},\{y_2\sqrt{2}\},\dots ,\{y_t\sqrt{2}\}$ for $t>\sqrt{Y}$.

Now, set $B=\{\lfloor y_i\sqrt{2}\rfloor :1⩽i⩽t\}$. We have $\lfloor y_j\sqrt{2}\rfloor -\lfloor y_i\sqrt{2}\rfloor =\lfloor (y_j-y_i)\sqrt{2}\rfloor$ for $i<j$ (because the corresponding inequality for the fractional parts holds by the ordering assumption on the $\{y_i\sqrt{2}\}$ ), which means that all differences between elements of $B$ are indeed in $H$. Since $|B|>\sqrt{Y}>\sqrt{n}/\sqrt{3\sqrt{2}}$, this is the required set.