I have an unmarked ruler (AD) of length 6cm. Making two marks in it, one (B) at 1cm from the left end and other (C) at 2cm from the right end, I´m able to measure any integer length from 1 to 6 cm:

       +----+-------------+--------+
       A    B             C        D

AB = 1cm / CD = 2cm / BC = 3cm / AC = 4cm / BD = 5cm / AD = 6cm.

If I have an unmarked ruler of length 14cm, what is the minimum number of marks, and where do I have to make them, in order to be able to measure any integer length from 1 to 14cm?

Marking  1  3    6  and 10 allows repesentation of all distances,

except 12.

Theoretically 6 marks could cover 15 distances ==> C(6,2)=15.

However not all the pairs define different distances,
D(0,3)= D(3,6)   and D(6.10) =D(10,14)  so we are left with partial coverage only, (15-2=13) ==>12 is missing.

REM1 : My 4 marks are triangular numbers, but for the ruler
of 15 cm (next triangular number) the situation does not improve

REM2 : The fact that there is no possible 4tuple of different numbers between 1 and 13 inclusive can be be easily proven  by checking exhaustively all possible combinations

Posted by Ady TZIDON on 2008-11-15 11:11:26