5
$\begingroup$

Given $n \in \mathbb N$, I'm interested in sets $S \subset \mathbb Z$ such that the numbers $1$, $2$, ..., $n$ can be obtained as differences between pairs of elements in $S$.

I'd like to find the minimum size of $S$ given $n$. Call that $f(n)$. I'd also like to know if the sets $S$ can be restricted to be of the form $S \subset \{1,2,...n+1\}$ without loss of optimality (where "optimality" means smallest size).

For example, $f(6) = 4$ (found by exhaustive search). One optimal set for $n=6$ is $\{1,2,5,7\}$ (note that $2-1=1$, $7-5=2$, $5-2=3$, $5-1=4$, $7-2=5$ and $7-1=6$). This set is of the form $S \subset \{1,2,...n+1\}$.

So, my questions are:

  1. Is there some formula for $f(n)$, or an algorithm to construct an optimal $S$?
  2. Can a minimum-size set always be found that is a subset of $\{1,2,...,n+1\}$?

Even if the answers are not known, any pointer in these directions will be helpful.

$\endgroup$
4
  • 1
    $\begingroup$ This is similar to Golomb rulers but those have all differences distinct instead of accounting for all differences. $\endgroup$ Commented Nov 25, 2017 at 1:45
  • 1
    $\begingroup$ Instead try minimal sparse rulers. The answer to question 2 is presumably "yes" since you can check $2^{n-1}$ cases and choose the minimal cases $\endgroup$
    – Henry
    Commented Nov 25, 2017 at 1:53
  • $\begingroup$ @Henry Spot-on, thanks! $\endgroup$
    – Luis Mendo
    Commented Nov 25, 2017 at 1:58
  • $\begingroup$ The difference seems to be that sparse rulers impose the condition $S \subset \{1,2,...n+1\}$ by definition. Removing that condition can result in smaller sets that still generate all numbers $1$, ..., $n$, as shown in the linked Wikipedia article $\endgroup$
    – Luis Mendo
    Commented Nov 25, 2017 at 2:15

0

You must log in to answer this question.

Browse other questions tagged .