Perfect ruler

A perfect ruler of length $\ell$ is a ruler with integer markings $a_1=0<a_2<\dots <a_n=\ell$, for which there exists an integer $m$ such that any positive integer $k\le m$ is uniquely expressed as the difference $k=a_i-a_j$ for some $i,j$. This is referred to as an $m$-perfect ruler.

An optimal perfect ruler is one of the smallest length for fixed values of $m$ and $n$.

Example

A 4-perfect ruler of length $7$ is given by $(a_1,a_2,a_3,a_4)=(0,1,3,7)$. To verify this, we need to show that every positive integer $k\le 4$ is uniquely expressed as the difference of two markings:

$1=1-0$

$2=3-1$

$3=3-0$

$4=7-3$

See also

• Golomb ruler
• Sparse ruler
• All-interval tetrachord

Template:Combin-stub