Sparse ruler
A sparse ruler is a ruler in which some of the distance marks may be missing. More abstractly, a sparse ruler of length with marks is a sequence of integers where . The marks and correspond to the ends of the ruler. In order to measure the distance , with there must be marks and such that . 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 with 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 with marks. A sparse ruler is called optimal if it is both minimal and maximal. Since the number of distinct pairs of marks is , this is an upper bound on the length of any maximal sparse ruler with 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 be distinct. In general, a Golomb ruler with marks will be considerably longer than an optimal sparse ruler with marks, since 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. (Wikipedia).
