The sparse ruler problem has been famously worked on by Paul Erdős, Marcel J. E. Golay, John Leech, Alfréd Rényi, László Rédei and Solomon W. Golomb, among many others. The problem is this: what is the smallest subset of so that the unsigned pairwise differences of give all values from 1 to ? One way to look at this is to imagine a blank yardstick. At what positions on the yardstick would you add 10 marks, so that you can measure any number of inches up to 36?
Another simple example is of size 3, which has differences , and . The sets of size 2 have only one difference. The minimal subset is not unique; the differences of also give .
Part of what makes the sparse ruler problem so compelling is its embodiment in an object inside every schoolchild's desk—and its enduring appeal lies in its deceptive simplicity. Read on to see precisely just how complicated rulers, marks and recipes can be.