Is it true 2020 C shortlist has 10 problems? Let $a_i = \lfloor i\sqrt{2}\rfloor$ and $b_i = \{i \sqrt{2}\}$. Lemma 1: There is a constant $c_1$ such that for all positive integers $k$, there exists $i$ with $b_i < \frac{1}{k}$ and $i \le c_1k$. Proof: Consider the Pell equation $x^2 - 2y^2 = -1$. Let $(x_i, y_i)$ be the sequence of solutions, so $(x_1, y_1) = (7, 5)$. Due to well-known properties of Pell equations, we will have $y_i \sim (7+5\sqrt{2})^{2i}$, so in particular we can find $c_1$ such that for any $k$ there exists $j$ with $k \le y_j \le c_1k$. Then for such $y_j$, $$a_{y_i} = \lfloor y_i \sqrt{2}\rfloor = \lfloor \sqrt{x_i^2+1}\rfloor = x_i$$and $$b_{y_i} = y_i\sqrt{2} - x_i = \frac{1}{y_i\sqrt{2}+x_i} < \frac{1}{y_i}$$ so the lemma is proven. Now, pick arbitrary $d > 2$. Take $k = \lceil \frac{\sqrt{n}}{d}\rceil$ in the lemma to get that there exists some $i$ with $b_i < \frac{1}{\lceil \frac{\sqrt{n}}{d} \rceil}$ and $i \le c_1\lceil\frac{\sqrt{n}}{d}\rceil$. Let $m = \lceil \frac{\sqrt{n}}{d}\rceil$ for convenience. Then observe that clearly $$b_{ij} = jb_i \quad (j \le m)$$so $$b_i < b_{2i} < \ldots < b_{mi} < \frac{1}{2}$$ But clearly this implies that for any $1 \le j_1 < j_2 \le m$, we have both $a_{(j_1+j_2)i} = a_{j_1i} + a_{j_2}i$ and $a_{(j_2-j_1)i} = a_{j_2i} - a_{j_1i}$. Thus if we set $S = \{a_i, a_{2i}, \ldots, a_{mi}\}$, then for any $x > y$ in $S$, $x \pm y \in A$. Note that every element of $S$ is at most $a_{mi} < mi\sqrt{2} < \frac{n}{2}$ for $n$ sufficiently large. Suppose we have a subset $A \subseteq [n]$ not containing two elements whose difference is in $H$. For every $x \in A$, color every $y \in [n]$ such that $|x-y| \in S$ red. By the above, at least $|S||A|$ numbers are colored. They are all distinct, due to the hypothesis that no two elements of $A$ have their difference in $H$. Thus $|A| \le \frac{n}{|S|} \le d\sqrt{n}$ for all sufficiently large $n$, and we are done.

This problem was proposed by Rodrigo Sanches Angelo from Brazil.

Fix $C=7$. For any $m\geq 0$ define the positive integers $x_m$ and $y_m$ such that \[(1+\sqrt{2})^{2m+1}=x_m+y_m\sqrt{2}.\]Clearly we also have $(1-\sqrt{2})^{2m+1}=x_m-y_m\sqrt{2}$, hence $x_m^2-2y_m^2=-1$. Therefore, for any $m$, and any $1\leq k<x_m$, we have \[kx_m<\sqrt{2}(ky_m)=k\sqrt{x_m^2+1}<kx_m+\frac{k}{x_m}<kx_m+1,\]hence $kx_m=\lfloor \sqrt{2}(ky_m)\rfloor\in H$. Note that $y_m\leq x_m$, and \[x_{m+1}+y_{m+1}\sqrt{2}=(x_m+y_m\sqrt{2})(3+2\sqrt{2})\,\,\Rightarrow\,\, x_{m+1}=3x_m+4y_m\leq 7x_m,\]there must exist $m$ such that $\sqrt{n}\leq x_m< 7\sqrt{n}$. Now, suppose $A\subset\{1,2,\cdots,n\}$ and $|A|\geq 7\sqrt{n}$, then by Pigeonhole Principle there must exist $a,b\in A$ such that $a>b$ and $x_m|a-b$. Let $a-b=kx_m$, then $0<kx_m<n\leq x_m^2$, therefore $1\leq k<x_m$, so by the above we know $a-b=kx_m\in H$, as desired.

Lemma: Let $q$ be a postive integer with $q\notin H$. There is a positive integer $k$ with $q=\lfloor (2+\sqrt{2})k\rfloor$. Proof: Suppose there is no $i$ with $q=\lfloor \sqrt{2}i\rfloor$ and no $k$ with $q=\lfloor (2+\sqrt{2})k\rfloor$. The the is an $i$ and a $k$ with $(i-1)\sqrt{2}<q<q+1<i\sqrt{2}$ and $(k-1)(2+\sqrt{2})<q<q+1<k(2+\sqrt{2})$. We get \begin{align*} i-1<\frac{q}{\sqrt{2}}<\frac{q+1}{\sqrt{2}}<i\\ k-1<\frac{q}{2+\sqrt{2}}<\frac{q+1}{2+\sqrt{2}}<k\\ i+k-2<q\left(\frac{1}{\sqrt{2}}+\frac{1}{2+\sqrt{2}}\right)<(q+1)\left(\frac{1}{\sqrt{2}}+\frac{1}{2+\sqrt{2}}\right)<i+k\\ i+k-2<q<q+1<i+k \end{align*} $i,k$ and $q$ are integers. $i+k-2<q<q+1<i+k$ is a contradiction. Let $B$ be a set of positive integers satisfying for all $a,b\in B$ with $b>a$ the condition $b-a\notin H$. Let $C$ be the set defined by $C:=\{a\in B/\{\min(B)\}|a-\min B\}$. We have $|C|=|B|-1$. Any element of $C$ and any positive difference between elements of $C$ is not in $H$. These numbers can be written as $\lfloor (2+\sqrt{2})k\rfloor$. Let $0<c_1<c_2<\cdots<c_{|C|}$ be the elements of $C$. For $i=1,2,\cdots,|C|$, let $n_i$ be the unique positive integer with $c_i=\lfloor (2+\sqrt{2})n_i\rfloor$. For $1\leq i<j\leq |C|$, there exists a positive interger $k$ satisfying $\lfloor (2+\sqrt{2})n_j\rfloor=\lfloor (2+\sqrt{2})n_i\rfloor+\lfloor (2+\sqrt{2})k\rfloor$. We get: \begin{align*} (2+\sqrt{2})n_j>\lfloor (2+\sqrt{2})n_j\rfloor=\lfloor (2+\sqrt{2})n_i\rfloor+\lfloor (2+\sqrt{2})k\rfloor>(2+\sqrt{2})(n_i+k)-2\\ n_j-n_i-k>\frac{-2}{2+\sqrt{2}}>-1\\ (2+\sqrt{2})n_j-1<\lfloor (2+\sqrt{2})n_j\rfloor=\lfloor (2+\sqrt{2})n_i\rfloor+\lfloor (2+\sqrt{2})k\rfloor<(2+\sqrt{2})(n_i+k)\\ n_j-n_i-k<\frac{1}{2+\sqrt{2}}<1\\ k=n_j-n_i \end{align*} Suppose there are $i<j$ with $\mbox{frac}((2+\sqrt{2})n_i)>\mbox{frac}((2+\sqrt{2})n_j)$. Then we have $\lfloor (2+\sqrt{2})n_j\rfloor-\lfloor (2+\sqrt{2})n_i\rfloor>(2+\sqrt{2})(n_j-n_i)>\lfloor (2+\sqrt{2})(n_j-n_i)\rfloor$. This contradicts $\lfloor (2+\sqrt{2})n_j\rfloor-\lfloor (2+\sqrt{2})n_i\rfloor=\lfloor (2+\sqrt{2})(n_j-n_i)\rfloor$. Wet get $\mbox{frac}((2+\sqrt{2})n_i)<\mbox{frac}((2+\sqrt{2})n_j)$ for $i<j$. Let $d_1:=n_1$ and $d_{i+1}:=n_{i+1}-n_i$ for $i=1,2,\cdots,|C|-1$. We have $\sum_{i=1}^{|C|}d_i=n_{|C|}$. We have $\mbox{frac}((2+\sqrt{2})d_1)=\mbox{frac}((2+\sqrt{2})n_1)$. $\mbox{frac}((2+\sqrt{2})n_i)<\mbox{frac}((2+\sqrt{2})n_{i+1})$ implies $\mbox{frac}((2+\sqrt{2})d_{i+1})=\mbox{frac}((2+\sqrt{2})n_{i+1})-\mbox{frac}((2+\sqrt{2})n_i)$. We get $\sum_{i=1}^{|C|}\mbox{frac}((2+\sqrt{2})d_i)=\mbox{frac}((2+\sqrt{2})n_{|C|})<1$. We have \begin{align*} \mbox{frac}((2+\sqrt{2})d_i)=(2+\sqrt{2})d_i-\lfloor(2+\sqrt{2})d_i\rfloor\\ =\sqrt{2}d_i-\lfloor\sqrt{2}d_i\rfloor\\ =\frac{(\sqrt{2}d_i-\lfloor\sqrt{2}d_i\rfloor)(\sqrt{2}d_i+\lfloor\sqrt{2}d_i\rfloor)}{\sqrt{2}d_i+\lfloor\sqrt{2}d_i\rfloor}\\ =\frac{2d_i^2-\lfloor\sqrt{2}d_i\rfloor^2}{\sqrt{2}d_i+\lfloor\sqrt{2}d_i\rfloor}\geq\frac{1}{\sqrt{2}d_i+\lfloor\sqrt{2}d_i\rfloor}>\frac{1}{2\sqrt{2}d_i}\\ \frac{1}{2\sqrt{2}}\sum_{i=1}^{|C|}\frac{1}{d_i}<\sum_{i=1}^{|C|}\mbox{frac}((2+\sqrt{2})d_i)<1 \end{align*} By Cauchy-Schwarz, we have: \[ |C|^2=\left(\sum_{i=1}^{|C|}\frac{1}{\sqrt{d_i}}\cdot\sqrt{d_i}\right)^2\leq\left(\sum_{i=1}^{|C|}\frac{1}{d_i}\right)\left(\sum_{i=1}^{|C|}d_i\right) \] We get: \begin{align*} \frac{|C|^2}{2\sqrt{2}}\leq\frac{1}{2\sqrt{2}}\left(\sum_{i=1}^{|C|}\frac{1}{d_i}\right)\left(\sum_{i=1}^{|C|}d_i\right)<\sum_{i=1}^{|C|}d_i=n_{|C|}\\ \frac{2+\sqrt{2}}{2\sqrt{2}}|C|^2<(2+\sqrt{2})n_{|C|}<c_{|C|}+1=\max(C)+1\\ \frac{2+\sqrt{2}}{2\sqrt{2}}(|B|-1)^2<\max(B)\\ |B|<\sqrt{\frac{2\sqrt{2}}{2+\sqrt{2}}}\cdot\sqrt{\max(B)}+1=\sqrt{2\sqrt{2}-2}\cdot\sqrt{\max(B)}+1\\ |B|<\left(\sqrt{2\sqrt{2}-2}+1\right)\sqrt{\max(B)} \end{align*} We can choose the constant $\lambda=\sqrt{2\sqrt{2}-2}+1$. For any $A\subseteq\{1,2,\cdots,n\}$ satisfying $|A|\geq\lambda\sqrt{n}$, we have $|A|\geq\lambda\sqrt{n}\geq\lambda\sqrt{\max(A)}$. $A$ does not satisfy $|A|<\lambda\sqrt{\max(A)}$. There must be an $a\in A$ and a $b\in A$ with $b-a\in H$. Note: Let $X,Y$ be positive integers satisfying $X^2-2Y^2=-1$. It is possible to proof that the set $B=\{1,1+(X+2Y),1+2(X+2Y),\cdots,1+2X(X+2Y)\}$ satifies $b-a\notin H$ for any $a,b\in B$. Using these sets, you can proof that in $|B|<\sqrt{2\sqrt{2}-2}\cdot\sqrt{\max(B)}+1$ neither the $\sqrt{2\sqrt{2}-2}$ nor the $1$ can be replaced by a better constant. Note: $|B|<\sqrt{2\sqrt{2}-2}\cdot\sqrt{\max(B)}+1$ implies that for large values of $\max(B)$, the quotient $\frac{|B|}{\sqrt{\max(B)}}$ can only be small above $\sqrt{2\sqrt{2}-2}$. It is possible to proof that the quotient $\frac{|B|}{\sqrt{\max(B)}}$ is maximal for $B=\{1,4,7\}$.

This is good ANT problem and very nice solution of @pi_quadrat_sechstel. Of course it is much more number theory than combinatorics. As for me, solution of the problem by contradiction consists of two things. Firstly, we recognize Beatty sequence (https://en.wikipedia.org/wiki/Beatty_sequence) and got that every number in $A-A$ is equal to $[(2+\sqrt{2})j]$ for some j. Secondly, we order elements of $A$ like this $a_0<a_1<\dots<a_k$ and denote $b_i=a_i-a_{i-1}$. After considering sums of $b_i$ it becomes clear that $\sum_{i=1}^k \{(2+\sqrt{2})b_i\}<1$. After that we can estimate fractional parts from below as @above did and easily understand that $k$ should be something like $c\sqrt{n}$, no more.

It suffices to prove that ${y/\sqrt{2}}$ has only monotone sequences of length $O(\sqrt{n})$ up to $n$. In fact, it suffices to prove the same for ${x\sqrt{2}}$ because we can split the cases $y=2x$ and $y=2x+1$ of from each other, the first gives directly ${x\sqrt{2}}$ and the second gives ${x\sqrt{2}+\sqrt{2}}$. Call our sequence ${a_1\sqrt{2}}, \cdots, {a_k\sqrt{2}}$ and we want to show $k=O(\sqrt{n})$. But this is easy because $\sqrt{2}$ is badly approximable. If $|a_{i+1}\sqrt{2}-a_i\sqrt{2}|_{\mathbb{R}/\mathbb{Z}}=O(1/\sqrt{n})$ (which happens for most $a_{i+1}-a_i$ in our sequence) then I claim we must have $a_{i+1}-a_i=\Omega(\sqrt{n})$, which clearly sufficient. To show this it suffices to prove that for all positive $m$, $|{m\sqrt{2}}|_{\mathbb{R}/\mathbb{Z}}=\Omega(1/m)$. Then this is exactly the badly approximable property, and we can prove it by say, noting that for all integers $m,n$ we have $m\sqrt{2}-n=\frac{2m^2-n^2}{m\sqrt{2}+n}$ which is $\Omega(1/m)$ in magnitude.

Suppose we have a set $ A$ of natural numbers $ 1\le a_1<a_2<\dots<a_m\le n$ such that $ |a-b|\notin H$ for any $ a,b\in A$. For every $ i=1,2,\dots,m$ we construct a set $ \mathcal{I}_i$ of intervals $ \left[a_i+j\sqrt{2}-1, a_1+j\sqrt{2}\right], j=1,2,\dots $ (the red ones in figure 1 below). Clearly, $ \displaystyle a_{i+1}\notin \bigcup_{j=1}^i \mathcal{I}_j$ It's natural to estimate how much $ \bigcup_{j=1}^i \mathcal{I}_j$ increases after each step. Since the red pattern in figure 1 is periodical with period $ \sqrt{2}$ we wind it up on $ [0,\sqrt{2}]$ assuming $ 0$ and $ \sqrt{2}$ are glued. For a real number $ x$ we denote by $ t(x)$ the unique point on $ \left[0,\sqrt{2}\right)$ such that $ x-t(x)=j\sqrt{2}$ for some $ j\in\mathbb{Z}$. Thus $ 1,2,\dots,n$ are mapped to $ t(1),t(2),\dots,t(n)$ on $ \left[0,\sqrt{2}\right]$. For any $ a_i$ the red pattern on figure 1 is mapped to $ [t(a_i)-1,t(a_i)]$, with the convention $ 0$ and $ \sqrt{2}$ are glued, i.e. if $ t(a_i)-1<0$ we continue drawing the red pattern jumping from $0$ to $\sqrt{2}$ and then from $ \sqrt{2}$ to the left (see figure 2). At each step, the next point $ t(a_{i+1})$ is outside the red set, hence at each step the measure of the red set increases by $ t(a_{i+1})-t(a_i)$. We'll prove, it cannot be too small. We know, $ t(a_i)=a_i-k\sqrt{2}, t(a_{i+1})=a_{i+1}-\ell\sqrt{2}$ for some $ k,\ell\in\mathbb{N}$. Thus, $$\displaystyle t(a_{i+1})-t(a_i)=a_{i+1}-a_{i}-(\ell-k)\sqrt{2}.$$Since $ \sqrt{2}$ is an algebraic number of degree $ 2$, Liouville's theorem (lower bound for diophantine approximation) says, there exists an absolute constant $ C$ such that $$ \displaystyle \left|\sqrt{2}-\frac{p}{q}\right|\ge \frac{C}{q^2}$$It implies $$ \displaystyle t(a_{i+1})-t(a_i)\ge \frac{C}{a_{i+1}-a_i}.$$Jensen's inequality for the convex function $ \frac{1}{x}$ yields $$ \displaystyle \sum_{i=1}^{m-1} t(a_{i+1})-t(a_i)\ge C \frac{(m-1)^2}{a_m-a_1}\ge C\frac{(m-1)^2}{n}.$$Finally, if $ m>C_1\sqrt{n}$, for some constant $ C_1,$ we obtain $ \displaystyle \sum_{i=1}^{m-1} t(a_{i+1})-t(a_i)>\sqrt{2}$, which shows some $ a_i$ should hit the red set, and the result follows. $ \blacksquare$ Comment. There are more details about the motivation and other stuff in my blog.

Lemma: For all $n\in\mathbb{N}$, $n\not\in H$ iff $\lfloor n\sqrt{2} \rfloor$ is even and $\lfloor (n+1)\sqrt{2} \rfloor$ is odd. Proof: $n\not\in H$ iff there exist $a\in\mathbb{N}$ such that $a\sqrt{2}<n<n+1<(a+1)\sqrt{2}$. This is equivalent to $2a<n\sqrt{2}<2a+1<(n+1)\sqrt{2}<2a+2$ and hence the lemma is proved. Let $1\leq x_1<x_2<\cdots<x_k\leq n$ be elements of $A$ which satisfying for any $a,b\in A$ then $a-b\not\in H$. We will prove that $k<C\sqrt{n}$ for some fixed $C\in\mathbb{R}$. By lemma, if $a<b<c$ are elements of $A$ then $\lfloor (c-a)\sqrt{2} \rfloor,\lfloor (c-b)\sqrt{2} \rfloor,\lfloor (b-a)\sqrt{2} \rfloor$ are all even. Since $\lfloor x+y \rfloor$ is equal to either $\lfloor x\rfloor+\lfloor y\rfloor$ or $\lfloor x\rfloor+\lfloor y\rfloor+1$, we must have $\lfloor (c-a)\sqrt{2} \rfloor=\lfloor (c-b)\sqrt{2} \rfloor+\lfloor (b-a)\sqrt{2} \rfloor$. This implies that $\{(c-a)\sqrt{2}\}=\{(c-b)\sqrt{2}\}+\{(b-a)\sqrt{2}\}$ where $\{x\}$ denotes the decimal part of $x$. Therefore, $\{(x_k-x_1)\sqrt{2}\}=\{(x_2-x_1)\sqrt{2}\}+\{(x_3-x_2)\sqrt{2}\}+\cdots+\{(x_k-x_{k-1})\sqrt{2}\}$. We know that $\{m\sqrt{2}\}=m\sqrt{2}-\lfloor m\sqrt{2} \rfloor=\frac{1}{m\sqrt{2}+\lfloor m\sqrt{2}\rfloor }>\frac{1}{2\sqrt{2}m}$. Hence, by AM-HM inequality, $$1>\{(x_k-x_1)\sqrt{2}\}>\frac{1}{2\sqrt{2}}\left(\frac{1}{x_2-x_1}+\frac{1}{x_3-x_2}+\cdots+\frac{1}{x_k-x_{k-1}}\right)\geq\frac{(k-1)^2}{2\sqrt{2}(x_k-x_1)}.$$ Because $x_k-x_1<n$, we obtain that $k<\sqrt{2\sqrt{2}n}+1$ as desired.

Solved with nukelauncher. Suppose no \(a\), \(b\) exist with \(a-b\in H\); we will show \(|A|\le O(\sqrt n)\). To this end, we cite the following famous result: Lemma: [Beatty] If \(\frac1a+\frac1b=1\) for \(a,b>1\) and \(a,b\notin\mathbb Q\), then \(\{\lfloor na\rfloor:n\in N\}\) and \(\{\lfloor nb\rfloor:n\in\mathbb N\}\) partition \(\mathbb N\). It follows that for all \(a,b\in A\), we have \(|a-b|\in\{\lfloor i(2+\sqrt2)\rfloor:i\in\mathbb N\}\). Let \(A=\{a_1<a_2<\cdots<a_k\}\). Let \(\lfloor i_{pq}(2+\sqrt2)\rfloor=a_q-a_p\) whenever \(p<q\). I claim: Claim: For all \(p<q<r\), we have \(\{i_{pr}\sqrt2\}=\{i_{pq}\sqrt2\}+\{i_{qr}\sqrt2\}\). Proof. The possible values of \(\{i_{pq}\sqrt2\}+\{i_{qr}\sqrt2\}-\{i_{pr}\sqrt2\}\) are in the interval \((-1,2)\). But since \((a_r-a_p)=(a_q-a_p)+(a_r-a_q)\), i.e.\ \(\lfloor i_{pr}(2+\sqrt2)\rfloor=\lfloor i_{pq}(2+\sqrt2)\rfloor+\lfloor i_{qr}(2+\sqrt2)\rfloor\), we know \begin{align*} (-1,2)&\ni\{i_{pq}\sqrt2\}+\{i_{qr}\sqrt2\}-\{i_{pr}\sqrt2\}\\ &=\{i_{pq}(2+\sqrt2)\}+\{i_{qr}(2+\sqrt2)\}-\{i_{pr}(2+\sqrt2)\}\\ &=i_{pr}(2+\sqrt2)-i_{pq}(2+\sqrt2)-i_{qr}(2+\sqrt2)\\ &=(i_{pr}-i_{pq}-i_{qr})(2+\sqrt2). \end{align*}Since \(i_{pr}-i_{pq}-i_{qr}\in\mathbb Z\), we must have \(i_{pr}-i_{pq}-i_{qr}=0\). The claim follows. \(\blacksquare\) Repeatedly applying the claim, we deduce \[\{i_{12}\sqrt2\}+\{i_{23}\sqrt2\}+\cdots+\{i_{k-1,k}\sqrt2\}=\{i_{1k}\sqrt2\}<1.\]I contend: Claim: For \(x\in\mathbb N\), we have \(\{x\sqrt2\}\ge\frac1{2\sqrt2x}\). Proof. Assume for contradiction \(\{x\sqrt2\}<\frac1{2\sqrt2x}\). Then for some integer \(y<x\sqrt2\), \[0<-y+x\sqrt2<\frac1{2\sqrt2x}.\]Multiplying by \(y+x\sqrt2\), we have \[0<2x^2-y^2<\frac{y/x+\sqrt2}{2\sqrt2}<\frac{2\sqrt2}{2\sqrt2}=1,\]contradiction. \(\blacksquare\) Finally, employing the obvious bounds \[i_{pq}<\frac{a_q-a_p+1}{2+\sqrt2}\quad\text{and}\quad\sum_{j=1}^{k-1}(a_{j+1}-a_j+1)=(a_k-a_1)+(k-1)\le n+k-2,\]we conclude (by Jensen) that \[1>\sum_{j=1}^{k-1}\{i_{j-1,j}\sqrt2\}\ge\frac1{2\sqrt2}\sum_{j=1}^{k-1}\frac1{i_{j-1,j}}>\frac{2+\sqrt2}{2\sqrt2}\sum_{j=1}^{k-1}\frac1{a_{j+1}-a_j+1}\ge\frac{2+\sqrt2}{2\sqrt2}\frac{(k-1)^2}{n+k-2}.\] This readily rearranges to \(k\le O(\sqrt n)\), and we are done.

I think I proved clog(n) for this problem. Is this bound true? Basically just the strong continued fraction representation of sqrt 2 and Beatty's theorem forces strict increase in fractional parts of slightly shifted multiples of sqrt 2. Maxes occur at or next to the result of a continued dual recursion, specifically floor((3+2sqrt(2))^n/(2sqrt(2))) being the integer corresponding to the permitted multiple of sqrt(2). EDIT: This is false, just see below.

I guess I'll write out the proof: Clearly by Beatty's all diffs are in the set of $\lfloor n(2+\sqrt{2}) \rfloor$. Since these are all diffs, we can simply shift the entire set of $A$ between 1 and n to between 0 and n-1 with the minimal element equal to $0$. Then the property still holds, and from taking the difference with the smallest number in the set, which is $0$, every other element must be a distinct element of the set $\lfloor n(2+\sqrt{2}) \rfloor$. Since $2+\sqrt{2} > 1$, each element $s$ in the set of $\lfloor n(2+\sqrt{2}) \rfloor$ has a unique integer $t$ such that $s = \lfloor t(2+\sqrt{2}) \rfloor$, and furthermore since $2+\sqrt{2} > 2$, neither $s-1$ nor $s+1$ can be in the set. Now, consider two nonzero elements of $A$, which are $\lfloor a(2+\sqrt{2}) \rfloor > \lfloor b(2+\sqrt{2}) \rfloor$. Since $\lfloor a(2+\sqrt{2}) \rfloor - \lfloor b(2+\sqrt{2}) \rfloor = \lfloor ((a-b)(2+\sqrt{2}) \rfloor - 1$ or $ \lfloor ((a-b)(2+\sqrt{2}) \rfloor$, and since the later is in the set, the former isn't, so specifically it must be that $\lfloor a(2+\sqrt{2}) \rfloor - \lfloor b(2+\sqrt{2}) \rfloor = \lfloor ((a-b)(2+\sqrt{2}) \rfloor$. This implies that for two nonzero elements in $A$, the greater number must also have greater fractional part. This implies $A$ consists of $0$ and a sequence of elements with both strictly increasing integer parts and strictly increasing fractional parts. Now consider the difference between such elements. It's fractional part is in the set of $\{n(2+\sqrt{2}) \}$ and cannot cause the fractional part to overflow. I claim the minimal fractional part of every element in the set such that $n \leq d$ for some constant $d$ can be found in a simple closed-form. We owe this favor to the fact that $\sqrt{2}$ is a quadratic irrational, meaning its continued fraction is repeating. In particular, consider an algorithm that stores both $\text{minimal fractional part}$ and $1-\text{maximal fractional part}$ in the sequence up to some $n$, call then $a_n$ and $b_n$, and let $a(n)$ be the index of the term which has minimal fractional part up to the nth term, and let $b(n)$ be the index of the term which has maximal fractional part up to the nth term. If $0 < b_{n+1} < b_n$, then the term with index $b(n+1)-b(n)$ and fractional part $b_n-b_{n+1}$ must have fractional part at least $a_n$ by definition, so $a_n < b_n$. Similarly, if $a_{n+1} < a_n$, then the term with index $a(n+1)-a(n)$ and fractional part $1-(a_n-a_{n+1})$ must be at most $1-b_n$ by definition, so $a_n > b_n$. Furthermore, we know in fact that $a_n-a_{n+1}$ would be precisely $b_n$, since from when the last index $t = b(n)$ that $b$ changed, $b_n < a_n < a_t < b_t = b_{n-1}$. Similarly, we know that $b_n-b_{n+1}$ must have been precisely $a_n$ since from the last index $t = a(n)$ that $a$ changed, $a_n < b_n < b_t < a_t = a_{n-1}$. It follows that the sequences of $a, b$ follow a sort of euclidean algorithm, where the greater one appearing at index $i$ is decremented by the lesser one appearing at index $j$ at exactly index $i+j$, and take turns doing so, since clearly $a_n < b_n$ and $a_n > b_n$ cannot both occur at the same time. Notice that the sequence of decrements can be completely described by the euclidean interpretation of the continued fraction representation of $\frac{2-\sqrt{2}}{\sqrt{2}-1} = \sqrt{2}$, where $\sqrt{2}-1$ comes from $a_1$ and $2-\sqrt{2}$ comes from $b_1$. Specifically, $\sqrt{2} =1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2+ \ldots}}}}$ This tells us the exactly order of change in the sequences is precisely $b, a, a, b, b, a, a, b, b, a, a, \ldots$. Now, applying the earlier condition with $i$ and $j$, and letting $(A_{1_x}, A_{2_x})$ and $(B_{1_x}, B_{2_x})$ denote the ordered pairs $(\alpha, \beta)$ of the xth distinct number's index and value in the sequences of $a_n$ and $b_n$ as $n$ increases, we know that $A_{1_{2x}} = 2B_{1_{2x-1}}+A_{1_{2x-2}}, A_{2_{2x}} = A_{2_{2x-2}}-2B_{2_{2x-1}}$, $B_{1_{2x+1}} = 2A_{1_{2x}}+B_{1_{2x-1}}, B_{2_{2x+1}} = B_{2_{2x-1}}-2A_{2_{2x}}$, so either by dual or intertwining recursion on $A_1, B_1$, as well as either dual or intertwining recursion on $A_2, B_2$, we know that $A_{1_{2x}} = \left\lceil \frac{(3+2\sqrt{2})^x(1+\sqrt{2})}{2\sqrt{2}} \right\rceil, B_{1_{2x-1}} = \left\lfloor \frac{(3+2\sqrt{2})^x}{2\sqrt{2}} \right\rfloor$ and $A_{2_{2x}} = (\sqrt{2}-1)(3-2\sqrt{2})^x, B_{2_{2x-1}} = (3-2\sqrt{2})^x$. Anyways, the main point is that $A_{2_{x}} = \Theta \frac{1}{A_{1_{x}}}$. It is necessary that representing the set of differences, we must have $A_{1_{p_1}}+\ldots +A_{1_{p_q}} \leq n$ where $|A| = q+1$ and $\frac{1}{A_{1_{p_1}}}+\ldots +\frac{1}{A_{1_{p_q}}} \leq c$, so by cauchy-schwarz inequality, $|A|^2 \leq cn$, so $|A| \leq c\sqrt{n}$. So although exponents appear, the bound is tightest as $c\sqrt{n}$ and cannot be $c\log{n}$. And also I am aware there were many better ways to prove the last part, which have been described before this solution.

sketch: By Beatty's theorem, for all $a>b, a,b\in A$ there exists $n$ such that $a-b=\lfloor (2+\sqrt{2})n \rfloor$. Let $A=\{a_1,\cdots,a_m\}$, then let $\lfloor (2+\sqrt{2})t_j \rfloor= a_j-a-{j-1}$. We can use induction to prove that $$\{ (2+\sqrt{2})t_2\} + \cdots + \{(2+\sqrt{2})t_m\} <1$$ We can also prove that $\{\sqrt{2}t\} > \frac{1}{2\sqrt{2}t}$. Therefore, by Cauchy-Schwartz, $$n\ge a_m-a_1+1 > (2+\sqrt{2})(t_2+\cdots+t_m) > (2+\sqrt{2}) \frac{(m-1)^2}{\frac{1}{t_2}+\cdots+\frac{1}{t_m}} > (2+\sqrt{2}) \frac{(m-1)^2}{2\sqrt{2}}$$ As desired.

Let $k=|A|$, and define $I=\{2i + \lfloor i\sqrt{2} \rfloor : i \in \mathbb{Z}_{>0}\}$. Notice that $H$ and $I$ partition $\mathbb{Z}_{>0}$ because they are Beatty sequences with $\frac{1}{\sqrt{2}}+ \frac{1}{2+\sqrt{2}}=1$. Suppose that for all $a,b \in A$, $a-b \notin H$, i.e. $a-b \in I$. Next, let the elements of $A$ be $a_1 < a_2 < \cdots < a_k$. Define the differences $d_1=a_2-a_1, d_2=a_3-a_2, \cdots d_{k-1}=a_k-a_{k-1}$. By the assumption, $d_1,d_2, \cdots d_{k-1} \in I$, so we may write $d_1= 2x_1+\lfloor x_1\sqrt{2}\rfloor, d_2= 2x_2+\lfloor x_2\sqrt{2}\rfloor, \cdots d_{k-1}= 2x_{k-1}+\lfloor x_{k-1}\sqrt{2}\rfloor$. Claim: $\{x_1\sqrt{2}\}+ \{x_2\sqrt{2}\} + \cdots \{x_{k-1}\sqrt{2}\} < 1$ Proof: Suppose otherwise, and let $j$ be the smallest index such that $\{x_1\sqrt{2}\}+ \{x_2\sqrt{2}\} + \cdots \{x_{j}\sqrt{2}\} \ge1$. By the minimality of $j$ and the fact that each $\{x_i\sqrt{2}\} <1$, we must have that $1 \le \{x_1\sqrt{2}\}+ \{x_2\sqrt{2}\} + \cdots \{x_{j}\sqrt{2}\} < 2$. Consider the following: \begin{align*} a_{j+1}-a_1 &= d_1+d_2 + \cdots + d_j \\ &= 2(x_1+x_2+\cdots +x_j) + \lfloor x_1\sqrt{2}\rfloor + \lfloor x_2\sqrt{2}\rfloor + \cdots \lfloor x_j \sqrt{2}\rfloor \\ &= 2(x_1+x_2+\cdots +x_j) + \sqrt{2}(x_1+x_2+\cdots x_j) -\{x_1\sqrt{2}\}+ \{x_2\sqrt{2}\} + \cdots \{x_{j}\sqrt{2}\} \\ &= 2(x_1+x_2+\cdots +x_j) + \lfloor \sqrt{2}(x_1+x_2+\cdots x_j) \rfloor - 1 \end{align*}This means $a_{j+1}-a_1$ is $1$ less than an element of $I$, so it can't be in $I$ as any two elements of $I$ clearly differ by at least $2$. This is a contradiction and we are done. Now, observe that $d_i > 2x_i$ for each $i$, so $a_k-a_1=d_1+d_2 + \cdots d_{k-1}< n \implies x_1+x_2+\cdots x_{k-1} < \frac{n}{2}$. Furthermore, by Liouville's theorem, there exists a constant $r$ such that for all integers $p,q$, $|\sqrt{2}-\frac{p}{q}| > \frac{r}{q^2} \implies |q\sqrt{2} - p| > \frac{r}{q} \implies \{q\sqrt{2}\}>\frac{r}{q}$ Hence, we have the following by Cauchy-Schwartz: \begin{align*} \frac{n}{2} &> (\{x_1\sqrt{2}\}+ \{x_2\sqrt{2}\} + \cdots \{x_{k-1}\sqrt{2}\}) \cdot (x_1+x_2+\cdots x_{k-1}) \\ &> (\frac{r}{x_1} + \frac{r}{x_2} + \cdots + \frac{r}{x_{k-1}}) \cdot (x_1+x_2+\cdots x_{k-1}) \\ &> (r(k-1))^2 \end{align*}From this we can see that if $k=C\sqrt{n}$, where $C$ is a large enough constant, the RHS of the inequality will exceed the LHS. This is a contradiction so our assumption that $a-b \in I$ for all $a,b \in A$ was false, as desired.

Let $a_i = \lfloor i\sqrt{2}\rfloor, b_i = \lfloor i(2 + \sqrt{2})\rfloor = 2i + a_i$ and $B = \{b_i : i \in \mathbb{N}\}$. Take a set $A \subseteq [n]$ such that all differences are not in $H$. There are $\ge |A|/2$ either odd or even elements; remove the elements of the opposite parity and replace $A$ with this set. Note that if we can prove this new set has cardinality at most $C\sqrt{n}$, then $A$ has cardinality at most $2C\sqrt{n}$ which suffices. Since $\frac{1}{\sqrt{2}} + \frac{1}{2 + \sqrt{2}} = 1$ and $\sqrt{2}$ is irrational, by Beatty sequences we get $H \cap B = \O, H \cup B = \mathbb{N}$, hence all differences are in $B$. Furthermore, all differences are even. Let the elements of $A$ be $x_1 < x_2 < ... < x_k$ in ascending order. Suppose $x_j - x_i = b_m = 2m + \lfloor m\sqrt{2}\rfloor$. Now we cannot have $x_i + 2m \in A$ otherwise $x_j - (x_i + 2m) = \lfloor m\sqrt{2}\rfloor \in H$. In this way, let pair $(i, j)$ 'block' $x_i + 2m$, i.e. prevent it from being in $A$. Note that $x_i \le x_i + 2m \le x_i + 2m + \lfloor m\sqrt{2}\rfloor = x_j$, hence $x_i + 2m \in [n]$. Claim 1: $\lfloor a\rfloor + \lfloor b\rfloor$ equals either $\lfloor a+b\rfloor$ or $\lfloor a+b\rfloor - 1$. Proof: Note that this follows from $\{a\} + \{b\}$ equals $\{a+b\}$ or $\{a+b\}+1$. $\square$ Claim 2: If $b_p + b_q = b_r$, then $p + q = r$. Proof: $2p + 2q + \lfloor p\sqrt{2}\rfloor + \lfloor q\sqrt{2}\rfloor = 2r + \lfloor r\sqrt{2}\rfloor$. Thus, $2r + \lfloor r\sqrt{2}\rfloor \le 2p + 2q + \lfloor (p+q)\sqrt{2}\rfloor$ by Claim 1, hence $b_r \le b_{p+q}$. Furthermore, $2p + 2q - 2 + \lfloor (p+q-1)\sqrt{2}\rfloor \le 2p + 2q - 2 + \lfloor (p+q)\sqrt{2}\rfloor - 1 < 2p + 2q + \lfloor p\sqrt{2}\rfloor + \lfloor q\sqrt{2}\rfloor = 2r + \lfloor r\sqrt{2}\rfloor$. Hence $b_{p+q-1} < b_r$. Since $b_i$ is strictly increasing, $b_{p+q-1} < b_r \le b_{p+q} \Rightarrow b_r = b_{p+q} \Rightarrow r = p+q$. $\square$ Claim 3: Every pair $(i, j)$ blocks a unique number. Proof: Assume FTSOC not, and WLOG $(s, 1), (t, 2)$ block the same number. Note that $(i, j), (i, k)$ cannot block the same number: if $i < j, k$, then $x_i + 2u = x_i + 2v \Rightarrow u = v \Rightarrow b_u = b_v \Rightarrow j = k$, if $j, k < i$, then $x_i - \lfloor u\sqrt{2} \rfloor = x_i - \lfloor v\sqrt{2} \rfloor \Rightarrow u = v \Rightarrow j = k$, if $j < i < k$, then the blocked numbers are between $j, i$ and $i, k$ respectively hence cannot be the same. Then $x_2 - x_1 = b_p$, $x_s - x_1 = b_r$, $x_t - x_2 = b_q$, and $x_1 + 2r = x_2 + 2q \Rightarrow 2(q - r) = x_1 - x_2$. Hence $r = q + \frac{1}{2} (x_2 - x_1) = q + \frac{1}{2} b_p$. \begin{align*} x_s - x_t &= (x_s - x_1) - (x_2 - x_1) - (x_t - x_2) \\ &= b_{q + \frac{1}{2}b_p} - b_p - b_q \\ &= 2q + 2p + \lfloor p\sqrt{2}\rfloor + \lfloor q\sqrt{2} + p\sqrt{2} + \frac{\lfloor p\sqrt{2}\rfloor}{\sqrt{2}}\rfloor - 2p - \lfloor p\sqrt{2}\rfloor - 2q - \lfloor q\sqrt{2}\rfloor \\ &= \lfloor q\sqrt{2} + p\sqrt{2} + \frac{\lfloor p\sqrt{2}\rfloor}{\sqrt{2}}\rfloor - \lfloor q\sqrt{2}\rfloor. \end{align*}By Claim 1, this equals $\lfloor p\sqrt{2} + \frac{\lfloor p\sqrt{2}\rfloor}{\sqrt{2}}\rfloor$ or $\lfloor p\sqrt{2} + \frac{\lfloor p\sqrt{2}\rfloor}{\sqrt{2}}\rfloor + 1$. Note that the former equals $\lfloor (p + \frac{\lfloor p \sqrt{2} \rfloor}{2}) \sqrt{2} \rfloor \in H$ (since all differences are even), hence it must be the latter. Yet alternatively, we have by Claim 2, $x_s - x_2 = b_{q + \frac12 b_p} - b_p = b_{q + \frac12 b_p - p}$ and $x_s - x_t = b_{q + \frac12 b_p - p} - b_q = b_{\frac12 b_p - p} = \lfloor p\sqrt{2} \rfloor + \lfloor \frac{\lfloor p\sqrt{2} \rfloor}{\sqrt{2}} \rfloor$. Now we get $\lfloor p\sqrt{2} + \frac{\lfloor p\sqrt{2}\rfloor}{\sqrt{2}}\rfloor + 1 = \lfloor p\sqrt{2} \rfloor + \lfloor \frac{\lfloor p\sqrt{2} \rfloor}{\sqrt{2}} \rfloor$ which is a contradiction by Claim 1. $\square$ There are $k$ elements of $A$ hence ${k \choose 2}$ distinct blocked numbers, each in $[n]$. Clearly no element of $A$ is blocked either. Thus, $k + {k \choose 2} \le n \Rightarrow \frac{k^2 + k}{2} \le n \Rightarrow k \le \sqrt{2n}$.

Key Lemma: Let $a,b\in H$. Then $a+b\not\in H$ implies $\{a\}+\{b\}>1$. Proof: If this is not the case, let $a=\lfloor c\sqrt2\rfloor, b=\lfloor d\sqrt2\rfloor$. Then, $\lfloor a+b\rfloor =\lfloor a\rfloor + \lfloor b\rfloor$, then $$\left\{c\sqrt2\right\} +\left\{d\sqrt 2\right\}<1\implies \lfloor a+b\rfloor =\lfloor (c+d)\sqrt 2\rfloor$$so $a+b\in H$, a contradiction. Let the differences between consecutive elements of $A$ be $d_1, d_2,\ldots, d_m$. We prove that there exists constant $D$ such that $d_1+\cdots+d_m>Dm^2$. We now define $s_{k,i}=d_{k-1}+d_{k-2}+\cdots +d_i$ for $1\leq i\leq k-1$. For any positive integer $x\not\in H$, then $x+1,x-1\in H$ because $\sqrt 2<2$ and $x\geq 3$. Thus, we can define $x^+$ and $x^-$ to be: \begin{itemize} \item Let $c\in\mathbb N$ so that $\lfloor c\sqrt 2\rfloor = x+1$. Then let $x^+=c\sqrt 2$; \item Let $d\in\mathbb N$ so that $\lfloor d\sqrt 2\rfloor = x-1$. Then let $x^-=d\sqrt 2$. \end{itemize} Claim: $\{d_k^-\}+\{s_{k,i}^+\}>1$ for all $1\leq i\leq k-1<m$. Proof: This follows from the key lemma - otherwise $\lfloor s_{k+1, i}\rfloor =\lfloor d_k^- + s_{k,i}^+\rfloor\in H$, a contradiction. By Liouville's theorem, it is well-known that any number that can be expressed as a continued fraction has an irrationality measure of $2$. Thus, there exists constant $G$ such that: $$\left\lvert \sqrt 2-\frac{p}{q}\right\rvert\geq \frac{G}{q^2}$$for all positive integers $p,q$. We have $\{q\sqrt 2\}\leq 1-\frac{G}{q}$ for all $q\in\mathbb N$. From the lemma, we must have: $$\{d_k^-\}+\{d_{k-1}^-\}+\cdots+\{d_1^-\}> k-1$$Thus, if we let $d_i^-=y_i\sqrt 2$ then $d_i> d_i^-=y_i\sqrt 2$: $$k-1<\sum_{i=1}^k \{d_i^-\}\leq \sum_{i=1}^k \left(1-\frac{G}{y_i}\right)$$so $$\sum_{i=1}^k \frac{G}{y_i} <1$$By Cauchy-Schwarz: $$\left(\sum_{i=1}^m y_i\right)\left(\sum_{i=1}^m \frac{G}{y_i}\right)\geq Gm^2$$so $$\sum_{i=1}^m d_i >\sqrt 2\sum_{i=1}^m y_i \geq G\sqrt 2 m^2$$as needed. Therefore, $n>\sum_{i=1}^m d_i \geq G\sqrt 2 m^2=G\sqrt 2(\lvert A\rvert -1)^2$. so if $\lvert A\rvert \geq \left(\frac{1}{\sqrt{G\sqrt 2}}+1\right)\sqrt n$ then by the contrapositive, there exist $a,b\in A$ such that $a-b\in H$.

seventy years of the imo and this is what we managed to produce? fascinating We first prove the following lemma. Lemma: Let $x$ be a positive integer. Then $\{x\sqrt{2}\}\geq \frac{1}{2\sqrt{2}x}$. Proof: Since $x\sqrt{2}$ is not an integer, $$x\sqrt{2}-\lfloor x\sqrt{2}\rfloor \geq \sqrt{2x^2}-\sqrt{2x^2-1}=\frac{1}{\sqrt{2x^2}+\sqrt{2x^2-1}} \geq \frac{1}{2\sqrt{2}x}.~\blacksquare$$ Fix $C=2\sqrt{\frac{\sqrt{2}}{2+\sqrt{2}}}$. I claim that for sufficiently large $n$, if $|A|=\lceil C\sqrt{n}\rceil+1$, then we can find $a,b \in A$ with $a-b \in H$, which clearly finishes. Define $G=\{\lfloor (2+\sqrt{2})i\rfloor \mid i \in \mathbb{Z}^+\}$. Since $\frac{1}{\sqrt{2}}+\frac{1}{2+\sqrt{2}}=1$, by Beatty the sets $G$ and $H$ partition $\mathbb{Z}^+$, so suppose that $A-A \subset G$. Let the elements of $A$ be $a_0<a_1<\cdots<a_k$, so $k=\lceil C\sqrt{n}\rceil$. For $1 \leq i \leq k$, let $d_i$ be defined (uniquely) as the positive integer such that $\lfloor (2+\sqrt{2})d_i\rfloor=a_i-a_{i-1}$. Define the partial sums $p_0,\ldots,p_k$ with $$p_i=\sum_{j=1}^i \{(2+\sqrt{2})d_i\}=\sum_{j=1}^i \{d_i\sqrt{2}\}.$$By our lemma, $\{d_i\sqrt{2}\}\geq \frac{1}{2\sqrt{2}d_i}$. Furthermore, for large enough $n$, since $$\sum_{i=1}^k \lfloor (2+\sqrt{2})d_i\rfloor=a_n-a_0<n \implies \sum_{i=1}^k (2+\sqrt{2})d_i<2n \implies \sum_{i=1}^k d_i<\frac{2n}{2+\sqrt{2}},$$we have by Cauchy-Schwarz that $$(2\sqrt{2}p_k)\left(\sum_{i=1}^k d_i\right)\geq k^2\geq C^2n \implies p_k \geq \frac{C^2n}{\frac{4\sqrt{2}n}{2+\sqrt{2}}}=1.$$Since $p_0=0$ and $p_j-p_{j-1}<1$ for all $j \geq 1$, by discrete continuity there must exist some index $i$ such that $1 \leq p_i<2$. Then we should have $$a_i-a_0=(2+\sqrt{2})\left(\sum_{j=1}^i d_i\right)-p_i \in G.$$Observe that $\left\lfloor (2+\sqrt{2})\left(\sum_{j=1}^i d_i\right)\right\rfloor \in G$, and that $a_i-a_0$ is either $1$ or $2$ less than this quantity due to how $p_i$ was selected. However, since $2+\sqrt{2}>3$, if $x \in G$ then $x-1,x-2 \not \in G$, hence $a_i-a_0 \not \in G$: contradiction. $\blacksquare$

First define $G=\mathbb Z_{>0}\setminus H$. By Beatty, this is the set $\{\lfloor i(2+\sqrt2)\rfloor\mid i\in\mathbb Z_{>0}\}$ as $(\sqrt2)^{-1}+(2+\sqrt2)^{-1}=1$. We let $2+\sqrt2=\alpha$ for brevity. The contrapositive is equivalent to: "Prove that there exists a constant $C$ such that for any $A\subset\{1,2,\ldots,n\}$, if $a-b\in G$ for all $a\neq b\in A$, we have $m=|A|<C\sqrt n$." Let the elements of $A$ be $a_1<a_2<\dots<a_m$. We can express $a_i=a_1+\lfloor b_i\alpha\rfloor$ for each $i$.

I didn't expect $\sqrt2$ to be useful for the final bounding so I tried for a while to solve the problem with $\alpha$ being an arbitrary irrational greater than $2$. Is the $O(\sqrt n)$ bound tight? And if $\sqrt2$ is replaced by some arbitrary irrational/transcendental number, would it still be possible to bound the size of $|A|$ in a similar way?

Let $G = \mathbb Z_{>0} / H$. By Beatty's theorem, we have $G = \{ \lfloor i(2+\sqrt{2})\rfloor : i \in \mathbb Z_{>0}\} = \{3,6,10,13,17,\dots \}$. Let $|A|=m$. Suppose that for any $a,b\in A$, we have that $a-b\notin H$. Then, $a-b\in G$. Note that if $\lfloor x(2+\sqrt{2})\rfloor+\lfloor y(2+\sqrt{2})\rfloor\in H$, then $\{x\sqrt2\}+\{y\sqrt2\}<1$. Let $A=\{a_1, a_2, \ldots, a_m\}$. Then, each of the differences $a_2-a_1, a_3-a_2, \ldots, a_m-a_{m-1}\in H$. In fact, if $a_i-a_{i-1}=\lfloor t_i(2+\sqrt2)\rfloor$, then we have \[\left\{t_1\sqrt2\right\}+\left\{t_2\sqrt2\right\}+\cdots+\left\{t_{m-1}\sqrt2\right\}<1\]It is well-known that for any positive integer $x$, we have $\left\{x\sqrt2\right\}\geq\frac1{2\sqrt2x}$. Substituting, we have \[\frac1{t_1}+\frac1{t_2}+\cdots+\frac1{t_{m-1}}<2\sqrt2\]From Cauchy-Schwarz Inequality, we have \[(m-1)^2\leq (t_1+t_2+\cdots+t_{m-1})\left(\frac1{t_1}+\frac1{t_2}+\cdots+\frac1{t_{m-1}}\right)<2\sqrt2(t_1+t_2+\cdots+t_{m-1}) \ \ \ \ \ (\star)\]However, note that \[n-1\geq a_m-a_1=(a_2-a_1)+(a_3-a_2)+\cdots +(a_m-a_{m-1})\]\[=\lfloor {t_1(2+\sqrt2)}\rfloor+\lfloor {t_2(2+\sqrt2)}\rfloor+\cdots+\lfloor t_{m-1}(2+\sqrt2)\rfloor > (t_1+t_2+\cdots+t_{m-1})(2+\sqrt2)-m\]\[\Longrightarrow t_1+t_2+\cdots+t_{m-1}<\frac{m+n-1}{2+\sqrt2}\]Substituting this in $(\star)$ gives \[(2+\sqrt2)(m-1)^2<2\sqrt{2}(m+n-1)\]Hence, clearly, $m<C\sqrt{n}$ for some $C$.