Gold Chain Problem...

[psuresh1982]

The son of a rich bullion merchant left home on the death of his father. All he had with him was a gold chain that consisted of 151 links. He rented a place in the city center with a shop at the lower level and an apartment at the upper level. He was required to pay every week one link of the gold chain as rent for the place.

The landlady told him that she wanted one link of the gold chain at the end of one week, two gold links at the end of two weeks, three gold links at the end of three weeks and so on.

The son realized that he had to cut the links of the gold chain to pay the weekly rent. If the son wished to rent the place for 151 weeks, what would be the minimum number of links he would need to cut?

--------------------
suresh

[gripusa]

no need to cut i.e. 0 cut

[psuresh1982]

sorry gripusa....Last question i made a mistake..But here there is no mistake in my question...How you told no cut needed..How he give it to the owner. Elaborate your answer please..

----------------
suresh

[smart_coder]

12 cuts !!
two 1 link, two 2 links, one 3 links, two 4 links , two 8 links, two 16 links, one 32 links, one 64 links.

[psuresh1982]

Sorry smartcoder...that is not a correct answer. According to your answer totally 64+32+32+16+8+3+4+2 = 161 links are there..

But in my question i told only 151 links.

Also if you cut any place you got a single piece. Suppose if you cut 32nd link then you have three pieces. ie a single piece, 31 link piece, 119 link piece..

--------------------
suresh

[smart_coder]

Sorry..miscalculation!
its
1 + 1 +1 + 2 + 2 + 2 + 2 + 4 + 4 + 4 + 8 + 8 + 16 + 32 + 64
hence 14 cuts

[psuresh1982]

Hi smart coder,

In my previous post i also mentioned that if you want to cut a 64 link in 151 links then you cut at 65th link. Because on that 65th link comes to an single link after you cut it. So now you have three links 64,1,86. I think you understood what i am saying.

Also 14 cuts is not a correct answer.

------------------
suresh

[smart_coder]

Ok i dnt know how many cuts...but the links wud be like this only
1 + 1 +1 + 2 + 2 + 2 + 2 + 4 + 4 + 4 + 8 + 8 + 16 + 32 + 64
Tell me whether this combination is right or wrong?

[psuresh1982]

No smartcoder...These combinations are wrong.

----------------
suresh

[smart_coder]

sorry the answer is
1+ 2 + 4 + 8 + 16 + 32 + 64.

7 cuts( if chain is round)
6 cuts (if chain has lose ends)

[psuresh1982]

That was not a rounded chain. Also 7 cut is not a minimum.

------------------
suresh

[smart_coder]

1+ 2 + 4 + 8 + 16 + 32 + 64 + 24
Tell me whether this combination is correct or not?

If the chain has lose ends then there shud be 7 cuts to break the chain in 8 parts( as listed above) !

[psuresh1982]

hi smartcoder,

In my question i mentioned "what would be the minimum number of links he would need to cut?"

Once again i told you, you are not able to cut the links as it is. it means it is not possible to cut the chain into two parts. For example, it is not possible to cut the chain like (75,76) or (50,101) or any combinations.

What i told if you want cut, you must remove a single chain on that position. Then only you can get the remaining part. But you told your combination is 1+ 2 + 4 + 8 + 16 + 32 + 64 + 24.

it means 1+2+4+8+16+32+64+24+(1+1+1+1+1+1+1+1)(These eight single links added your answer, because every cut you got a single link.

Brief Example:

i am cutting the 151 links in the following places.
10th place, 40th place, 70th place, 120th place, 145th place.

After this cutting i got the following set of links.
one 9-link (10th place link going to be a single link)(1-9)
one 29-link(40th place link going to be a single link)(11-39)
one 19-link(70th place link going to be a single link)(41-69)
one 49-link(120th place link going to be a single link)(71-119)
one 24-link(145th place link going to be a single link)(121-144)
one 6-link
5 one links

I think now you can clearly understand. My question is try to find the small amount of cuts.


------------------------
suresh

[smart_coder]

U didnt get my answer Suresh!!
My answer ( in ur terminology) is given below:
I am cutting the chain after link numbers 1, 3, 7, 15, 31, 63, 127.

After this cutting i got the following set of links

one 1 link ( 1)
one two links ( 2 -3)
one four links( 4 - 7)
one eight links ( 8- 15)
one sixteen links( 16 - 31)
one thirty-two links ( 32 - 63)
one sixty-four links ( 64- 127)
one twenty-four links( 128- 151)

[psuresh1982]

hi smartcode,

Where is the seven single links ?(According to each cut you got one single link. I already mentioned in my previous post)

----------------
suresh

[smart_coder]

What do u mean by seven single links ?
Look i explain my solution in detail now:
At the end of first week I will take out 1 link from chain and give to hotel.
At the end of second week I will take out 2 links from chain and give to hotel and take back the 1 link which i gave him earlier.
At the end of 3rd week I will give him the 1 link which I took from him last week.
At the end of 4th week I will take out 4 links from the chain and give it to the hotel and take back 1 link and 2 links.
At the end of 5th week I will give him 1 link....and so on.


I dnt know wt exactly are u asking in ur question?

[psuresh1982]

hi smartcoder,

I told cut means remove a single chain. Please watch carefully the following picture.




---------------------
suresh

[smart_coder]

I gave up...Kindly u tell the solution!!

[smart_coder]

Suresh tell me ur yahoo chat id!!

[psuresh1982]

i sent a private message to you which contains my yahoo chat id.

-----------------
suresh