Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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: enter image description here

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.

share|improve this question
    
Welcome to any ideas, hints, or questions if I've not made myself clear. –  ᴊ ᴀ s ᴏ ɴ Nov 1 '12 at 13:33
    
Rulers of this kind are related to Golomb rulers after Solomon Golomb of USC who studied the problem extensively. –  Dilip Sarwate Nov 1 '12 at 19:06
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.