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 DAB = 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?
(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 9
1 2 3 6 10
1 2 3 7 10
1 2 3 7 11
1 2 3 8 10
1 2 3 8 12
1 2 3 9 10
1 2 3 9 13
1 2 4 6 11
1 2 4 6 13
1 2 4 8 13
1 2 5 6 12
1 2 5 8 11
1 2 5 8 12
1 2 5 9 11
1 2 6 7 11
1 2 6 8 11
1 2 6 9 11
1 2 6 9 12
1 2 6 10 13
1 2 6 11 13
1 2 7 8 11
1 2 7 9 11
1 2 7 10 11
1 2 7 10 12
1 2 7 10 13
1 2 8 9 12
1 2 8 10 13
1 3 4 6 13
1 3 4 7 12
1 3 4 8 12
1 3 4 8 13
1 3 5 6 13
1 3 5 7 13
1 3 5 8 13
1 3 5 11 12
1 3 6 9 13
1 3 6 10 12
1 3 6 10 13
1 3 7 9 13
1 3 7 11 12
1 3 8 9 13
1 3 8 10 12
1 3 8 10 13
1 3 8 11 12
1 3 9 10 12
1 3 9 10 13
1 4 5 6 12
1 4 5 7 12
1 4 5 8 12
1 4 5 10 12
1 4 5 11 12
1 4 7 9 12
1 4 7 10 12
1 4 8 9 12
1 5 6 11 12
1 5 8 10 12
1 5 8 11 12
1 5 9 11 12
1 6 7 10 12
1 7 8 10 12
1 7 9 10 12
1 7 9 11 12
1 8 9 10 12
1 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 |
solution
