# A ruler with missing graduation.

What is the minimum number of graduations, i.e. $f(n)$, on a ruler such that it can measure all integral units from $1$ to $n$, which $n\in\mathbb{Z}$, inclusively?

For example, to measure from $1$ to $5$ units, you only need $4$ graduations (not $6$) as shown in this figure: So, how can we deduce a general way general way to find $f(x)$. I suspect this has something to do with combination, which is not something I'm familiar with. Can anyone give me a hand? Thank you.

• Welcome to any ideas, hints, or questions if I've not made myself clear.
– JSCB
Nov 1, 2012 at 13:33
• Rulers of this kind are related to Golomb rulers after Solomon Golomb of USC who studied the problem extensively. Nov 1, 2012 at 19:06

These things have been studied, and the appropriate search terms for Googling are sparse rulers, complete rulers, optimal rulers, and perfect rulers, but as far as I know there is no known simple solution which works for all lengths $n$.
Assuming that the graduations contain the two boundary points, a simple lower bound for $m=f(n)$ is around $\sqrt{2n}$ (the number of segments achieved with $m$ graduations is $\frac{m(m+1)}{2}$ and for $m\gtrapprox \sqrt{2n}$, $n$ is reached)