Numbers 1 - 40 by dividing a rope

[Fredrik Johansson]

This "problem" is an old one. But I'd like some help with explaining
the strategy of solving it starting from the information in the
problem, not from guessing.

You are given a rope of 40 meters length.
The task is to divide the rope in no more than 4 pieces where you can
"build" each and every integer from 1 to 40. 1 meter represents the
number 1 and so on... If you have one length of 7 and one of 8 meters,
then you can build numbers 1 (put 7 next to 8), 7, 8 and 15. What
lengths should you cut the rope in?

(Sorry if the language is unclear, english is not my first language.)

--Fredrik Johansson--

[Nick Wedd]

In article <f396dc8d.0109...@posting.google.com>, Fredrik
Johansson <hit...@yahoo.se> writes

>This "problem" is an old one. But I'd like some help with explaining
>the strategy of solving it starting from the information in the
>problem, not from guessing.
>
>You are given a rope of 40 meters length.
>The task is to divide the rope in no more than 4 pieces where you can
>"build" each and every integer from 1 to 40. 1 meter represents the
>number 1 and so on... If you have one length of 7 and one of 8 meters,
>then you can build numbers 1 (put 7 next to 8), 7, 8 and 15. What
>lengths should you cut the rope in?

Stating with a 1-metre piece seems a good idea.

The next piece should obviously not have length 1. Nor length 2, as
this would allow us to measure 1 in two different ways (1, and 2-1)
which seems inefficient. So let's try 3 for the second piece. Now we
can measure lengths 1, 2, 3, 4.

So the next length we want to measure is 5. And we can already measure
4, and therefore subtract 4 from things. So 9 metres seems a good idea
for our third piece of rope. With lengths of 1,3,9, we can measure
1,2,3,4,5,6,7,8,9,10,11,12,13, each of them in a unique way.

And a pattern is emerging. These numbers are all powers of 3. So maybe
the next piece should be 27 metres. Indeed, the next length we want to
be able to measure is 14, and 14 is 27-9-3-1.

Nick
--
Nick Wedd

[Michael Hochster]

You may be interested in an old thread in rec.puzzles
called "optimal weights converse," which you can find
by searching for this phrase in google.

Mike

Fredrik Johansson <hit...@yahoo.se> wrote:
: This "problem" is an old one. But I'd like some help with explaining

[Sun Wentian]

starting with 1 can be a guess 'cuz we can get small numbers by one
piece minus another. we don't really have to cut off a 1-meter piece
only for this reason.

actually we must use the 4 fragments very very effeciently: there are
only 40 possibilities for 4 fragments which means if we can get a
length(integer) in 2 or more than 2 ways, we must have cut off at least
one fragment with a wrong length.

they are: ("1" represents a piece)

combination: possibilities
1 4
1+1 6
1+1+1 4
1+1+1+1 1
1-1 6
1+1-1 12
1+1+1-1/1-1-1-1 4
1+1-1-1 3
=========================================
40

4 fragments are represented by W,X,Y and Z. W<X<Y<Z. let's look at the
biggest numbers we can get with W, X, Y and Z first:

obviously W+X+Y+Z=40
the rest biggest number is X+Y+Z
thus W=1, X+Y+Z=39 and X+Y+Z-W=38;
the rest biggest number is W+Y+Z
thus X=3, W+Y+Z=37 and Y+Z=36.

let's now consider the small numbers:
now we can get 1=W, 2=X-W, 3=X, 4=W+X.
how long fragment Y can be? it's clear that it can't be shorter than 9
meters.
if Y=8 we can get 4 in two ways: 4=W+X, 4=Y-W-X. Y can't be 7 or 6 or 5
either.
can Y>=10 be possible? no.
if Y=10, then Z=17, we can get 6 by 6=Y-W-X and 6=Z-Y-W.
it will be even worse if Y is a number bigger than 10.

so the answer must be as below if there is a solution.
W=1
X=3
Y=9
Z=27

[Luc Kumps]

Yes, this *looks* like the optimal weights converse, but is *much* simpler,
and has *lots* of solutions, IMHO. If my program is correct, then 157 (out
of a total of 478 possible ones) sets of 4 pieces will it make possible to
obtain all numbers from 1 through 40.

Since the problem specifically talks about a ROPE and not about a STICK,
there is an additional operator introduced!
With a stick cut into parts, all we could do would be to add or subtract.
But with a rope, we can also divide by 2, simply by folding the rope into
two!

For example, if we have cut up the rope into 4 parts with lengths 1,1,6 and
32, then we can make ALL numbers from 1 through 40.
With a stick, one couldn't make "3".
But with a rope, it is sufficient to fold the piece with length "6" into two
equal parts.
From the fourth piece, with length 32, one can obtain lenghts 1, 2, 4, 8 and
16!

We can also fold the result of an addition or subtraction into two equal
halves.
For example, from two pieces with lengths 13 and 19, one can make 32 or 6,
and therefore also 1,2,3,4,8 and 16!

BTW, if the rope would be elastical, one would have another operator:
extending a piece to a length already available. This would mean we could go
BEYOND 40. In fact, we could go to infinity if the rope is infinitely
elastical ;-)
Just start with three pieces a,b and c with lengths a=N,b=N+1 and c=N+2.
Extend "a" so it becomes as long as "b", then extend "b" so it becomes as
long as "c".
"b" - "a" being 1, use it to extend "c" to N+3.

Luc

"Michael Hochster" <mic...@rgmiller.Stanford.EDU> wrote in message
news:9nsvum$lip$1...@usenet.Stanford.EDU...

[Sun Wentian]

i like your points. thought of folding but not extending.

cheers,

wt

-----Original Message-----
From: Luc Kumps
Posted At: 9/14/01 10:12 PM
Conversation: Numbers 1 - 40 by dividing a rope
Subject: Re: Numbers 1 - 40 by dividing a rope