# Sparse ruler

## Abstract ruler in which some of the distance marks may be missing / From Wikipedia, the free encyclopedia

#### Dear Wikiwand AI, let's keep it short by simply answering these key questions:

Can you list the top facts and stats about Sparse ruler?

Summarize this article for a 10 years old

A **sparse ruler** is a ruler in which some of the distance marks may be missing. More abstractly, a sparse ruler of length $L$ with $m$ marks is a sequence of integers $a_{1},a_{2},...,a_{m}$ where $0=a_{1}<a_{2}<...<a_{m}=L$. The marks $a_{1}$ and $a_{m}$ correspond to the ends of the ruler. In order to measure the distance $K$, with $0\leq K\leq L$ there must be marks $a_{i}$ and $a_{j}$ such that $a_{j}-a_{i}=K$.

A *complete* sparse ruler allows one to measure any integer distance up to its full length. A complete sparse ruler is called *minimal* if there is no complete sparse ruler of length $L$ with $m-1$ marks. In other words, if any of the marks is removed one can no longer measure all of the distances, even if the marks could be rearranged. A complete sparse ruler is called *maximal* if there is no complete sparse ruler of length $L+1$ with $m$ marks. A sparse ruler is called *optimal* if it is both minimal and maximal.

Since the number of distinct pairs of marks is $m(m-1)/2$, this is an upper bound on the length $L$ of any maximal sparse ruler with $m$ marks. This upper bound can be achieved only for 2, 3 or 4 marks. For larger numbers of marks, the difference between the optimal length and the bound grows gradually, and unevenly.

For example, for 6 marks the upper bound is 15, but the maximal length is 13. There are 3 different configurations of sparse rulers of length 13 with 6 marks. One is {0, 1, 2, 6, 10, 13}. To measure a length of 7, say, with this ruler one would take the distance between the marks at 6 and 13.

A Golomb ruler is a sparse ruler that requires all of the differences $a_{j}-a_{i}$ be distinct. In general, a Golomb ruler with $m$ marks will be considerably longer than an optimal sparse ruler with $m$ marks, since $m(m-1)/2$ is a lower bound for the length of a Golomb ruler. A long Golomb ruler will have gaps, that is, it will have distances which it cannot measure. For example, the optimal Golomb ruler {0, 1, 4, 10, 12, 17} has length 17, but cannot measure lengths of 14 or 15.