There is a blank ruler of $X$ units. You are going to set $9$ marks on this ruler so that you will be able to measure all integer values from $1$ to $X$ units with only one measurement.

What is the maximum value $X$ can take?

For example: if this problem was asked for $3$ marks, the answer would be $9$ by marking $1$,$2$ and $6$ units on the ruler.

Source: 2006 Puzzleup

  • 2
    how is 3 in one measurement? – JonMark Perry Aug 18 at 8:18
  • 1
    @JonMarkPerry from 9 to 6. – Oray Aug 18 at 8:19
  • Yes, the end points $0$ and $X$ are essentially also marks, not included in the count of the additional marks that you need to make. The solution to this problem can easily be found on Wikipedia if you know the mathematical term to look for. It looks possible to find the answer by hand, but I'm not so sure how you could prove that $X$ is maximal without computer assistance. – Jaap Scherphuis Aug 18 at 8:32
  • @JaapScherphuis "The solution to this problem can easily be found on Wikipedia if you know the mathematical term to look for." find it then and post it here as an answer. I believe it is also a solution to find an answer via wiki. I didnt say you should not use a computer to solve it by the way. – Oray Aug 18 at 8:34
  • @JonMarkPerry share it please :) sounds interesting – Oray Aug 19 at 5:36
up vote 7 down vote accepted

A ruler with just a few marks is called a "sparse ruler". Such a ruler of length $X$ that can measure all lengths from $1$ to $X$ is called a "complete sparse ruler". It is called optimal if it can't be done with fewer marks and there is no complete ruler with the same number of marks which is longer.

The Wikipedia page for Sparse Ruler lists optimal sparse rulers, and it shows that the one for 11 marks (including the end points of the ruler) is unique:

It has length $X=43$ and the marks are at $\{0, 1, 3, 6, 13, 20, 27, 34, 38, 42, 43\}$

II.I..I......I......I......I......I...I...II
01234567890123456789012345678901234567890123

The middle sections are all of length $7$, so it is fairly easy to verify that all lengths are measurable.

  • 1
    to be honest, i did not know the answer! thanks :) – Oray Aug 18 at 9:24

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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