For a positive integer $n$, and a non empty subset $A$ of $\{1,2,...,2n\}$, call $A$ good if the set $\{u\pm v|u,v\in A\}$ does not contain the set $\{1,2,...,n\}$. Find the smallest real number $c$, such that for any positive integer $n$, and any good subset $A$ of $\{1,2,...,2n\}$, $|A|\leq cn$.
This is a problem I do not know how to attack. There is a solution on AOPS, but I don't like its approach. It seems like probabilistic methods would do, but I'm not sure.
On
This is my attempt: too simple to be correct, just a bound as pointed out by the OP, but can be improved and might be of interest to better fellow StackExchangers. Let us denote $$ C(A) = \{ u \pm v \rvert u,v \in A \} $$ Let is consider the set $$ a_i = \{ 1, 2, … 2n \} $$ the largest possible candidate $A$, and further the sets $$b_{i,j} = a_i + a_j $$ and $$c_{i,j} = a_i - a_j $$ $i,j$ running over $\{1,2...2n\}$.
These could be simply visualized by the grid below as follows ($n=3$): the white region on top represents $c$, and the lower represent $b$
Let us also note that a set $A$ is “good” if $C(A)$ does not contain $$ \{ 1, 2, … n \} $$ as a subset. For this condition to be verified, it is sufficient that one only element only of $ \{ 1, 2, … n \} $ is not present in $C(A)$. If more elements of $ \{ 1, 2, … n \} $ were not present in $C(A)$, the cardinality of A would be smaller: and we are looking for the largest $A$.
Namely, the plan is now to eliminate elements from $$ a_i = \{ 1, 2, … 2n \} $$ in such a way that nowhere in the related grid one chosen element of $$ \{ 1, 2, … n \} $$ appears.
Each element of the set appears along a diagonal, identifying two elements that must not be present in $A$. The grid and the diagonal trend (wanted to say, “diagonal argument”, but “Domine, non sum dignus”) suggests that the optimal element not to be present in $C(a)$ (in order for $A$ to be as large as possible), is $n$, if the choice is made (this is sub-optimal) to eliminate all the pairs along the diagonal.
Hence, given any $n$, the largest "good" set $A$ is $ \{ n+1, n+2, …2n \} $.
As a result, the constant $c$ is bounded below by 1.
Let $A$ be good, say $m\notin A$ with $1\le m\le n$. Write $n=qm+r$ with $0\le r<m$.
For $1\le k\le 2r$, consider the $2q+1$ numbers $k+im$, $0\le i\le 2q$ (note that $k+2qm=k+2n-2r\le 2n < k+(2q+1)m$). We cannot have any consecutives in $A$ because that would give $m$ as a difference. Hence, at most $q+1$ of these numbers are $\in A$, and if $k\notin A$ then there are at most $q$ of them.
Likewise, for $2r<k< m$, we can have at most $q$ of the $2q$ numbers $k+im$, $0\le i\le 2q-1$ in $A$ (note that $k+(2q-1)m=k+2n-2r-m\le 2n<k+2qm$).
Also note that for $1\le k\le\frac m2$, we can have at most one of the $k$, $m-k$ in $A$, or else we have $m$ as a sum.
We conclude that for at most $\min\{2r,\frac m2\}$ numbers $k\in\{1,\ldots, m\}$, we have $q+1$ numbers $\equiv k\pmod m$ in $A$, and for the rest we have at most $q$ numbers $\equiv k\pmod m$ in $A$. Therefore, $$|A|\le \min\{2r,\tfrac m2\} +qm = n+\min\{r,\tfrac m2-r\}$$ for all good $A$, and by following the above, we can in fact construct $A$ that makes this inequality sharp. We conclude that $$ c=\sup\{\,1+\tfrac1{qm+r}\min\{r,\tfrac m2-r\}\mid 0\le r<m, q\ge1\,\}.$$ Obviously, we need only consider $q=1$. If $m\ge 4r$, we have $$1+\frac1{m+r}\min\{r,\tfrac m2-r\}=1+\frac r{m+r}\le 1+\frac1{5}$$ (with equality for $m=4r$) and if $m<4r$, say $m=\alpha r$ with $1<\alpha<4$, we have $$\begin{align}1+\frac1{m+r}\min\{r,\tfrac m2-r\}&=1+\frac{m/2-r}{m+r} \\&=1+\frac{\alpha-2}{2\alpha +2} \\&=\frac32-\frac3{2\alpha+2}\\&<\frac32-\frac{3}{10}=\frac 65\end{align}$$ We conclude that $$ c=\frac 65.$$