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.
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$.
The wikipedia article on Sparse Rulers gives many examples and a number of references where you can find out what has already done on this problem.
I wanted to post this as a comment, but seemingly don't have a privilege to post comments (shouldn't a user have first ability to post comments and then answers?)
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)
