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\leq 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\leq 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

This article incorporates material from perfect ruler on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.