Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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\}$

share|cite|improve this question
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

I believe you are looking for something like a Golomb Ruler. The term minimal spanning ruler as described in the pdf here: seems to fit the bill. The pdf also has a construction (page 53).

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.