# Spanning Difference Sets of near optimal size

Let $n$ be an integer ($n>1$). Show that there exists a proper subset $A$ of $\{1,2,\cdots, n\}$ such that the following holds:

1. the numbers of elements of $A$ is no more than $2[\sqrt n]$+1. ([x] means the greatest integer which is no more than x).

2. $\{\mid x-y\mid: x,y\in A, x\neq y\}=\{1,2,\cdots, n-1\}$

-
That can't be true. If $n$ is 100, then no element in $A$ can be more $21$ (otherwise it would break the bound for the sum all by itself). And there's no way to get 99 as a difference of two numbers between 0 and 21. If instead of "sum of elements" you say "number of elements", then the statement would have a fighting chance of being true. – Henning Makholm Sep 15 '11 at 1:54
And "the least integer which is no more than x" is not meaningful. – Henning Makholm Sep 15 '11 at 2:05
Presumably $[x] = \lfloor x \rfloor$, the floor of $x$, which is the greatest integer that is no more than $x$. – Brian M. Scott Sep 15 '11 at 2:09
It would be a good idea to rephrase this as a question instead as a command, as in "how do I show ...?" At least then it seems more likely that you want a hint instead of a full response as to how to do your homework exactly. We can't tell why you're asking the question you know. – Doug Spoonwood Sep 15 '11 at 2:17
Guys, Chen is a new user and might not be aware of this site's etiquette. Besides, this does not look like a homework problem to me. I am guessing Chen is just posting some of his favourites. – Aryabhata Sep 15 '11 at 3:30

If $n$ is a square, $n=m^2$, then you can take $$A=\lbrace\,1,2,3,\dots,m,2m,3m,\dots,m^2\,\rbrace$$ I suppose that if $n$ is not a square you can fiddle with this construction.