Misplaced Pages

A perfect ruler of length ${\displaystyle \ell }$ is a ruler with integer markings ${\displaystyle a_{1}=0<a_{2}<\dots <a_{n}=\ell }$, for which there exists an integer ${\displaystyle m}$ such that any positive integer ${\displaystyle k\leq m}$ is uniquely expressed as the difference ${\displaystyle k=a_{i}-a_{j}}$ for some ${\displaystyle i,j}$. This is referred to as an ${\displaystyle m}$-perfect ruler.

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

Example

A 4-perfect ruler of length ${\displaystyle 7}$ is given by ${\displaystyle (a_{1},a_{2},a_{3},a_{4})=(0,1,3,7)}$. To verify this, we need to show that every positive integer ${\displaystyle k\leq 4}$ is uniquely expressed as the difference of two markings:

${\displaystyle 1=1-0}$

${\displaystyle 2=3-1}$

${\displaystyle 3=3-0}$

${\displaystyle 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.

This combinatorics-related article is a stub. You can help Misplaced Pages by expanding it.

• v
• t
• e

• Combinatorics
• Combinatorics stubs