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$
  • 1
    $\begingroup$ This is similar to Golomb rulers but those have all differences distinct instead of accounting for all differences. $\endgroup$ – Ross Millikan Nov 25 '17 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 Nov 25 '17 at 1:53
  • $\begingroup$ @Henry Spot-on, thanks! $\endgroup$ – Luis Mendo Nov 25 '17 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 Nov 25 '17 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.