[Puzzle] Chain Link

[gaurav gupta]

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

--
GAURAV GUPTA
B.Tech IV Yr. , Department of Computer Science & Engineering
IT BHU , Varanasi
Contacts
Phone No: +91-99569-49491

e-mail :
gaurav...@acm.org
gaurav.gu...@itbhu.ac.in

[Manoj Kumar]

i think 5 links

1,1,3,6,10

[gaurav gupta]

Actually I am looking for logic behind it, can you explain it.

[Manoj Kumar]

the logic here i use is :

the length of nth link should be 1 more than the sum of all link upto (n-1).

if u will arrange it in increasing order .

[gaurav gupta]

I think 3 is sufficient
1,3,9

so
1 ==1
2 == 3-1
3 == 3
4 == 1+3
5 == 9-3-1
6 == 9-3
7 == 9+1-3
8 == 9-1
9 == 9
10 == 9+1
11 == 9+3-1
12 == 21-10(9+1)         simillary all 21-...


Is this solution right ?

[Manoj Kumar]

hey how can u break the chain .??

suppose u have to make lenth 2 .

then physically u cant make it using 1,3,9

[Manoj Kumar]

see the example given for link length 23 here

http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/chain-link-pay

[Karan Jain]

Gaurav,

 

Your solution shall work fine upto 5. For giving 4, for instance you'll give 1 & 3. For 5, you'll give 9 & take back 1 and 3. Now the person has 9. How will you give him 6?

 

Hence the solution is usually the one where you can form all the numbers upto 21 (or any other).

On Sat, Aug 15, 2009 at 12:06 PM, Manoj Kumar <manoj...@gmail.com> wrote:

--
Regards,

Karan

[N!+!N]

We can do it using 2 cuts.
actually we need to cut the chain in such a way that we can make all
combinations.
if we cut the 4th and 10th link, then the chain will be like

000X000000X0000000000

where X are the broken links
so if we have to give

1=X
2=XX
3=000
4=000X
5=000XX
6=000000
7=000000X
8=000000XX
9=000000 000
10=000000 000 X
11=0000000000 X


and similarly for the rest..

On 15 Aug, 11:27, gaurav gupta <1989.gau...@googlemail.com> wrote:
> Actually I am looking for logic behind it, can you explain it.
>
>
>
> On Sat, Aug 15, 2009 at 11:54 AM, Manoj Kumar <manoj.it...@gmail.com> wrote:
> > i think 5 links
> > 1,1,3,6,10
>

> > On Sat, Aug 15, 2009 at 11:37 AM, gaurav gupta <1989.gau...@googlemail.com

> > > wrote:
>
> >> 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
>
> >> --
> >> GAURAV GUPTA
> >> B.Tech IV Yr. , Department of Computer Science & Engineering
> >> IT BHU , Varanasi
> >> Contacts
> >> Phone No: +91-99569-49491
>
> >> e-mail :

> >> gaurav.gu...@acm.org
> >> gaurav.gupta.cs...@itbhu.ac.in

>
> --
> GAURAV GUPTA
> B.Tech IV Yr. , Department of Computer Science & Engineering
> IT BHU , Varanasi
> Contacts
> Phone No: +91-99569-49491
>
> e-mail :

> gaurav.gu...@acm.org
> gaurav.gupta.cs...@itbhu.ac.in

[gaurav gupta]

I wrote all cases na,
 for 6 I will do 9-3 ( first length of 9 and then i will remove subchain of length 3)

is there any problem in that ? If it is, then please explain what is the problem.

[Manoj Kumar]

i have the same answer naa??

bcoz the broken parts are same .

[Karan Jain]

@Nitin

You gave the same answer as Manoj except the fact that you say it will be 2 cuts. But for X to be considered as a link, you need to make 2 cuts for each X and so a total of 4 cuts are required.

--
Regards,

Karan

[N!+!N]

one modification..
its 3 if chain is circular as gaurav bhaiya explained

and 2 if its streight

On 15 Aug, 11:44, gaurav gupta <1989.gau...@googlemail.com> wrote:
> I wrote all cases na,
>  for 6 I will do 9-3 ( first length of 9 and then i will remove subchain of
> length 3)
>
> is there any problem in that ? If it is, then please explain what is the
> problem.
>

> On Sat, Aug 15, 2009 at 12:09 PM, Karan Jain <karanjain.it...@gmail.com>wrote:
>
>
>
> > Gaurav,
>
> > Your solution shall work fine upto 5. For giving 4, for instance you'll
> > give 1 & 3. For 5, you'll give 9 & take back 1 and 3. Now the person has 9.
> > How will you give him 6?
>
> > Hence the solution is usually the one where you can form all the numbers
> > upto 21 (or any other).
>

> > On Sat, Aug 15, 2009 at 12:06 PM, Manoj Kumar <manoj.it...@gmail.com>wrote:
>
> >> hey how can u break the chain .??
> >> suppose u have to make lenth 2 .
> >> then physically u cant make it using 1,3,9
>
> >>   On Sat, Aug 15, 2009 at 12:04 PM, gaurav gupta <

> >> 1989.gau...@googlemail.com> wrote:
>
> >>> I think 3 is sufficient
> >>> 1,3,9
>
> >>> so
> >>> 1 ==1
> >>> 2 == 3-1
> >>> 3 == 3
> >>> 4 == 1+3
> >>> 5 == 9-3-1
> >>> 6 == 9-3
> >>> 7 == 9+1-3
> >>> 8 == 9-1
> >>> 9 == 9
> >>> 10 == 9+1
> >>> 11 == 9+3-1
> >>> 12 == 21-10(9+1)         simillary all 21-...
>
> >>> Is this solution right ?
>
> >>> On Sat, Aug 15, 2009 at 11:57 AM, gaurav gupta <
> >>> 1989.gau...@googlemail.com> wrote:
>
> >>>> Actually I am looking for logic behind it, can you explain it.
>

> >>>> On Sat, Aug 15, 2009 at 11:54 AM, Manoj Kumar <manoj.it...@gmail.com>wrote:
>
> >>>>> i think 5 links
> >>>>> 1,1,3,6,10
>
> >>>>>   On Sat, Aug 15, 2009 at 11:37 AM, gaurav gupta <

> >>>>> 1989.gau...@googlemail.com> wrote:
>
> >>>>>> 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
>
> >>>>>> --
> >>>>>> GAURAV GUPTA
> >>>>>> B.Tech IV Yr. , Department of Computer Science & Engineering
> >>>>>> IT BHU , Varanasi
> >>>>>> Contacts
> >>>>>> Phone No: +91-99569-49491
>
> >>>>>> e-mail :

> >>>>>> gaurav.gu...@acm.org
> >>>>>> gaurav.gupta.cs...@itbhu.ac.in

>
> >>>> --
> >>>> GAURAV GUPTA
> >>>> B.Tech IV Yr. , Department of Computer Science & Engineering
> >>>> IT BHU , Varanasi
> >>>> Contacts
> >>>> Phone No: +91-99569-49491
>
> >>>> e-mail :

> >>>> gaurav.gu...@acm.org
> >>>> gaurav.gupta.cs...@itbhu.ac.in

>
> >>> --
> >>> GAURAV GUPTA
> >>> B.Tech IV Yr. , Department of Computer Science & Engineering
> >>> IT BHU , Varanasi
> >>> Contacts
> >>> Phone No: +91-99569-49491
>
> >>> e-mail :

> >>> gaurav.gu...@acm.org
> >>> gaurav.gupta.cs...@itbhu.ac.in

>
> >>> --
> >>> Regards,
>
> >>> Karan
>
> --
> GAURAV GUPTA
> B.Tech IV Yr. , Department of Computer Science & Engineering
> IT BHU , Varanasi
> Contacts
> Phone No: +91-99569-49491
>
> e-mail :

> gaurav.gu...@acm.org
> gaurav.gupta.cs...@itbhu.ac.in

[Karan Jain]

@Gaurav,

 

To do 6, you are doing 6 = 9-3. But to do this, you have only two ways:

1. The other person has 3 & you have 9. You give him 9 and take back 3 which is not the case after 5 has been given. So, this way is not possible.
2. The one that you suggested, shall not give the minimum number of cuts.

I think 1,1,3,6,10 is the right answer & minimum number of cuts shall be 4

--
Regards,

Karan

[Manoj Kumar]

other answer is :

1,2,4,6,8

[Karan Jain]

I probably figured out the logic.

 

If you cut the links till the nearest power of 2 & the remaining difference.

For instance: cut 21 into 2^0, 2^1, 2^2, 2^3, 21-(sum of all links broken) which gives 21 = (1,2,4,8,6)

 

Similarly for 7 = (1,2,4).

 

This is probably b'coz in bit representation you might be able to produce all the numbers upto 2^n, if you have the links as 2^i (0<=i<=n-1)

 

Now in case of 21, the highest power of 2 is 16. So, we break into 1,2,4,8. Now the next cannot be 16 since the sum shall exceed 21 (i.e. 1+2+4+8+16 = 31 > 21). The remaining is 21-(1+2+4+8) = 6.

Now for digits after 16 and until 21 can be considered as 16+(1), 16+(2), 16+(3), 16+(4), 16+(5). Now each of the numbers in brackets viz. 1,2,3,4,5 can already be developed using links produced. And since the sum of all links is 21, the remaining can be used to form 16.

 

--
Regards,

Karan