All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Building a ruler (Posted on 2008-11-14)
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?

 See The Solution Submitted by pcbouhid No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution | Comment 2 of 10 |
(In reply to Catch? by ed bottemiller)

I don't think there was a catch.

I also origianally got 130 solutions but added a history internal array so I could weed out solutions that were the reverse of previous solutions.  It turns out (with hindsight) that I could have accomplished that by requiring a mark at 1; I didn't know ahead of time that no solution depends on having an internal distance of 1 cm.

The 65 solutions with 5 marks not counting their mirror images:

`1   2   3   4   91   2   3   6  101   2   3   7  101   2   3   7  111   2   3   8  101   2   3   8  121   2   3   9  101   2   3   9  131   2   4   6  111   2   4   6  131   2   4   8  131   2   5   6  121   2   5   8  111   2   5   8  121   2   5   9  111   2   6   7  111   2   6   8  111   2   6   9  111   2   6   9  121   2   6  10  131   2   6  11  131   2   7   8  111   2   7   9  111   2   7  10  111   2   7  10  121   2   7  10  131   2   8   9  121   2   8  10  131   3   4   6  131   3   4   7  121   3   4   8  121   3   4   8  131   3   5   6  131   3   5   7  131   3   5   8  131   3   5  11  121   3   6   9  131   3   6  10  121   3   6  10  131   3   7   9  131   3   7  11  121   3   8   9  131   3   8  10  121   3   8  10  131   3   8  11  121   3   9  10  121   3   9  10  131   4   5   6  121   4   5   7  121   4   5   8  121   4   5  10  121   4   5  11  121   4   7   9  121   4   7  10  121   4   8   9  121   5   6  11  121   5   8  10  121   5   8  11  121   5   9  11  121   6   7  10  121   7   8  10  121   7   9  10  121   7   9  11  121   8   9  10  121   8   9  11  12`

The program includes 7 "marks", counting two of which are the end points of the ruler.

DECLARE SUB place (which!)
DIM SHARED n, m(10), ct, h(200, 10)
m(1) = 0: m(2) = 14

CLS

FOR n = 4 TO 7
REDIM SHARED used(14), lst(n)
used(0) = 1: used(14) = 1
place 3
NEXT

PRINT : PRINT ct

SUB place (which)
IF which = 3 THEN st = 1:  ELSE st = m(which - 1) + 1
FOR psn = st TO 14 - (n - which)
IF used(psn) = 0 THEN
used(psn) = 1
m(which) = psn
IF which = n THEN
REDIM meas(14)
FOR i = 1 TO n
FOR j = 1 TO n
dist = ABS(m(i) - m(j))
meas(dist) = 1
NEXT j
NEXT i
good = 1
FOR i = 1 TO 14
IF meas(i) = 0 THEN good = 0: EXIT FOR
NEXT
IF good THEN
FOR i = 1 TO ct
match = 1
FOR j = 3 TO n
IF m(j) <> 14 - h(i, n - j + 3) THEN match = 0: EXIT FOR
NEXT
IF match THEN good = 0: EXIT FOR
NEXT i
IF good THEN
ct = ct + 1
FOR i = 3 TO n
PRINT USING "####"; m(i);
h(ct, i) = m(i)
NEXT
PRINT
IF ct MOD 40 = 0 THEN DO: LOOP UNTIL INKEY\$ > "": PRINT
END IF
END IF
ELSE
place which + 1
END IF
used(psn) = 0
END IF
NEXT psn
END SUB

 Posted by Charlie on 2008-11-14 18:06:03

 Search: Search body:
Forums (0)