Author |
Topic: Chain Link 21 (Read 1034 times) |
|
larivlan
Newbie
Posts: 2
|
 |
Chain Link 21
« on: Dec 6th, 2007, 8:06am » |
 Quote  Modify
|
I need help on the Chain Link 21 riddle, if you could help me out that would be great
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Chain Link 21
« Reply #1 on: Dec 6th, 2007, 8:35am » |
Quote Modify
|
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)
1 2 4 6 8 -> so 4 'cuts' (unlinking)
1 1 + 3 6 10 -> 2 'cuts' (with cut links kept loose)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
FiBsTeR
Senior Riddler
Gender:
Posts: 581
|
|
Re: Chain Link 21
« Reply #2 on: Dec 6th, 2007, 2:15pm » |
Quote Modify
|
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 24-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*23 - 1 = 23. One cut would allow you, at most, only 8 combinations. Seeing the other thread, there is indeed a solution for this (which is also towr's, upon looking again).
|
| « Last Edit: Dec 6th, 2007, 2:36pm by FiBsTeR » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Chain Link 21
« Reply #3 on: Dec 7th, 2007, 7:34am » |
Quote Modify
|
on Dec 6th, 2007, 8:35am, towr wrote:
My guesses (i.e without proof of optimality)
1 1 + 3 6 10 -> 2 'cuts' (with cut links kept loose)
|
|
There are problems with lengths 9, 13, 16, ....
|
| « Last Edit: Dec 7th, 2007, 7:35am by Hippo » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Chain Link 21
« Reply #4 on: Dec 7th, 2007, 7:37am » |
Quote Modify
|
on Dec 7th, 2007, 7:34am, Hippo wrote:| There are problems with lengths 9, 13, 16, .... |
|
How? is 9 not 3+6, 13 not 3+10? 16 not 6+10?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
larivlan
Newbie
Posts: 2
|
|
Re: Chain Link 21
« Reply #5 on: Dec 7th, 2007, 8:01am » |
Quote Modify
|
Two cuts is what I got as well, but what about a 63 link chain, can it be done in 3 cuts?
|
|
IP Logged |
|
|
|
FiBsTeR
Senior Riddler
Gender:
Posts: 581
|
|
Re: Chain Link 21
« Reply #6 on: Dec 7th, 2007, 9:42am » |
Quote Modify
|
Why not just {1,1,1,4,8,16,32}?
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Chain Link 21
« Reply #7 on: Dec 11th, 2007, 12:22am » |
Quote Modify
|
on Dec 7th, 2007, 7:37am, 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.
|
| « Last Edit: Dec 11th, 2007, 12:31am by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print