wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Chain Link 21
        
(Message started by: larivlan on Dec 6^th, 2007, 8:06am)

Title: Chain Link 21
Post by larivlan on Dec 6^th, 2007, 8:06am

I need help on the Chain Link 21 riddle, if you could help me out that would be great

Title: Re: Chain Link 21
Post by towr on Dec 6^th, 2007, 8:35am

It might have been helpful to post the puzzle, so people don't have to look it up.

Quote:

What is the least number of links you can cut in a chain of 21 links to be able to give someone all possible number of links up to 21?

It seems open to interpretation whether you actually cut the links loose, or whether the idea is just unlink them (the difference being that if you start with say a chain of 5 links, you might end up with e.g. 2+2+the cut one, or 2 and 3)

My guesses (i.e without proof of optimality)
[hide]1 2 4 6 8 -> so 4 'cuts' (unlinking)
1 1 + 3 6 10 -> 2 'cuts' (with cut links kept loose)[/hide]

Title: Re: Chain Link 21
Post by FiBsTeR on Dec 6^th, 2007, 2:15pm

I think 4 cuts is optimal for the first case, since if there were only 3 cuts, there could be, at most, only 4 distinct lengths of "subchains", which can result in only 2⁴-1 = 15 (you can't give him nothing...) different combinations you could make, whereas you need 21.

EDIT: If the interpretation is as towr also suggested, in which a cut leaves 3 "subchains", 2 cuts is also optimal, since it would result in 5 "subchains" (at most 4 distinct), in which the total number of combinations is, at most, 3*2³ - 1 = 23. One cut would allow you, at most, only 8 combinations. Seeing the other thread (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1113340021;start=0#0), there is indeed a solution for this (which is also towr's, upon looking again).

Title: Re: Chain Link 21
Post by Hippo on Dec 7^th, 2007, 7:34am

on 12/06/07 at 08:35:57, towr wrote:

My guesses (i.e without proof of optimality)
[hide]
1 1 + 3 6 10 -> 2 'cuts' (with cut links kept loose)[/hide]

There are problems with lengths 9, 13, 16, ....

Title: Re: Chain Link 21
Post by towr on Dec 7^th, 2007, 7:37am

on 12/07/07 at 07:34:04, Hippo wrote:

There are problems with lengths 9, 13, 16, ....

How? is 9 not 3+6, 13 not 3+10? 16 not 6+10?

Title: Re: Chain Link 21
Post by larivlan on Dec 7^th, 2007, 8:01am

Two cuts is what I got as well, but what about a 63 link chain, can it be done in 3 cuts?

Title: Re: Chain Link 21
Post by FiBsTeR on Dec 7^th, 2007, 9:42am

Why not just {1,1,1,4,8,16,32}?

Title: Re: Chain Link 21
Post by Hippo on Dec 11^th, 2007, 12:22am

on 12/07/07 at 07:37:39, towr wrote:

How? is 9 not 3+6, 13 not 3+10? 16 not 6+10?

I probably understand the problem another way ... what about when you are asked to create a chain from the pieces without additional cutting.
If there are chains of 3 uncut and 6 uncut pieces there is no way to connect them without further cutting...

But with 2 cuts there are 3 "uncut chains" and you can get:
(no cut, one uncut) 3+
(one cut, one uncut) 3+
(one cut, two uncut) 3+
(two cut, one uncut) 3+
(two cut, two uncut) 3+
(two cut, three uncut) 1+
(one cut, no uncut) 1+
(two cut, no uncut) 1+
at most 18 distinct positive lengths alltogether so 21 cannot be achieved.