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

  • 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.