Gold Chain Problem...

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

no need to cut i.e. 0 cut

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

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.

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

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

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

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?

No smartcoder...These combinations are wrong.

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

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

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

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

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

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) !

hi smartcoder,

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

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+([B]1+1+1+1+1+1+1+1[/B])(These eight single links added your answer, because every cut you got a single link.

[B]Brief Example:[/B]

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

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)

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

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?

hi smartcoder,

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

[ATTACH]69[/ATTACH]


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

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

Suresh tell me ur yahoo chat id!!

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

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

hi...............................>>>><>
what i think you have to cut 1 link at the last of every single link so that a son can give rent for 151 week if i am right you can tell me otherwise correct me

no rohit...that is not a correct answer.

[B][I]Clue: The total number of cut is only 4. Try to find which place we are going to cut.[/I][/B]

Hi Friends,

Here is my answer for this question...The mininum number of cuts needed to made is 4 for a chain with 151 links.

If the links are numbered serially from 1 to 151, then the cuts would be made n the following links. 6, 17, 38, 79.

So Now you have 4 one-link pieces, one 5-link piece, one 10-link piece, one 20-link piece, one 40-link piece and one 72-link piece.

To gain a better understanding, consider the scenerio in the first few weeks as illustrated in the table blow.

weeks - Gold links given

1 -------- 1
2 --------- 1+1
3 --------- 1+1+1
4 --------- 1+1+1+1
5 --------- 5 (get back the 4 one links)
6 --------- 5+1
7 --------- 5+1+1
8 --------- 5+1+1+1
9 --------- 5+1+1+1+1
10 -------- 10 (get back the one 5-link piece and 4 one link pieces)
11 -------- 10+1
12 -------- 10+1+1
.
.
.

Using the above format we can give a link for all the 151 weeks.


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

I have no clue abt ur solution.. i m nt able to understand.

what can i do? i can't able to explain simply other than this.

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

[QUOTE=smart_coder;9345]I have no clue abt ur solution.. i m nt able to understand.[/QUOTE]

I wonder why.

Just an extension to this problem...:)

what would be the minimum number of links he would need to cut?
i. if the gold chain that consisted of 383 links
ii. if the gold chain that consisted of 159 links
iii. if the gold chain that consisted of 63 links
iv. if the gold chain that consisted of 23 links

are you able to generalize the solution;)

If you see my solution i am using 4 cut for 151 links. Also finally i got (5,10,20,40,76) set of links.

So using 4 cut you can satisfy maximum of 155 links.
(5,10,20,40,80)
The series is going (x,2x,4x,..)

So if we using 5 cut you can satisfy maximum of 378 links.
(6,12,24,48,96,192)

If we using 6 cut you can satisfy the maximum of 889 links.
(7,14,28,56,112,224,448)

I don't have any generalized solution for this. Because i see this puzzle in somewhere place.

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

The generalized formula is,
By using 'n' cut you can get up to maximum of (n+1) 2^(n+1) -1 links.

And
[COLOR="Red"]
So using 4 cut you can satisfy maximum of 155 links.
(5,10,20,40,80)[/COLOR] is wrong...you can get up to 159 links ( 5+10+20+40+80 + 4 links ) by making 4 cuts.

Hi Suresh,

In your question, it says "He was required to pay every week one link of the gold chain as rent for the place..." Considering this fact, I think the minimum number of cuts will be 151.

Explanation: When he has to pay for the first week, he will cut the chain twice - he has to cut the chain frist, then remove one link (one more cut) and pay the land lady. At the end of 150 weeks, 151 cuts would have gone, but for final link he needn't cut the chain anymore.

The 2nd para stating, "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"; I suppose it's given to confuse people, bcoz anyway as 1 week adds on, one more link comes to her every week, and she will have the number of links stated. ;)

Am I right ???

Cheers,
Srilatha.K :)

I think minimum cut should be 4

because if u cut into following pattern
1 6 17 38 79 151
---------------------------------------------------------
^ ^ ^ ^
^ means cut
now no. of single links are (1+1+1+1) in 4 places cut

and other 5 pieces are 1. 5 links
2. 10 links
3. 20 links
4. 40 links
5. 72 links


for week
1=1
2=1+1
3=1+1+1
4=1+1+1+1
5=put 5 link piece and remove other 1+1+1+1 (4) single pieces
6=5+1
......

72=put 72 links and remove 40+20+10+5+1+1+1+1
....
81=72+5+1+1+1+1
82=72+10


....
and so on upto 151 links

my answer :

5 + 1 + 10 + 1 + 20 + 1 + 50 + 1 + 62

--->>4 cuts

it is the same with the moneytary