0
$\begingroup$

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

  • 3
    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.2011-09-15
  • 0
    And "the least integer which is no more than x" is not meaningful.2011-09-15
  • 0
    Presumably $[x] = \lfloor x \rfloor$, the *floor* of $x$, which is the *greatest* integer that is no more than $x$.2011-09-15
  • 0
    @Brian, or it may be the least integer that is no _less_ than x.2011-09-15
  • 1
    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.2011-09-15
  • 0
    @Henning: Doubtful: the notation $[x]$ for floor is pretty standard in older and lower-level texts.2011-09-15
  • 1
    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.2011-09-15
  • 0
    Doesn't look like algebraic number theory to me, so I re-tagged.2011-09-15

2 Answers 2

1

I believe you are looking for something like a Golomb Ruler. The term minimal spanning ruler as described in the pdf here: http://www.math.sjsu.edu/~alperin/alperin-drobot.pdf seems to fit the bill. The pdf also has a construction (page 53).

1

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.