8
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ how is 3 in one measurement? $\endgroup$
    – JMP
    Aug 18, 2018 at 8:18
  • 1
    $\begingroup$ @JonMarkPerry from 9 to 6. $\endgroup$
    – Oray
    Aug 18, 2018 at 8:19
  • $\begingroup$ 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. $\endgroup$
    – Jaap Scherphuis
    Aug 18, 2018 at 8:32
  • $\begingroup$ @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. $\endgroup$
    – Oray
    Aug 18, 2018 at 8:34
  • $\begingroup$ @JonMarkPerry share it please :) sounds interesting $\endgroup$
    – Oray
    Aug 19, 2018 at 5:36

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ to be honest, i did not know the answer! thanks :) $\endgroup$
    – Oray
    Aug 18, 2018 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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