Brain Teaser #53
Gold Links
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 100 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 100 weeks, what would be the minimum number of links he would need to cut?
Note that when a link in the center of the chain is cut, three pieces are obtained: a one-link piece and two other pieces. For example, when the third link in a chain consisting of 6 links is cut then what is obtained is a one-link piece, a two-link piece and a three-link piece.
The minimum number of cuts needed to be made is 4 for a chain with 100 links.
If the links are numbered serially from 1 to 100, then the cuts would be made on the following links:
6, 17, 38, and 79.
This would result in 4 one-link pieces, one 5-link piece, one 10-link piece, one 20-link piece, one 40-link piece, and one 21-link piece.
To gain a better understanding, consider the scenario in the first few weeks as illustrated in the table below.
Week: 1 2 3 4 5 6 7 8 9 10 11 12
Gold links given: 1 1+1 1+1+1 1+1+1+1 5 5+1 5+1+1 5+1+1+1 5+1+1+1+1 10 10+1 10+1+1
The table above indicates that:
at the end of the fifth week, the 5-link piece is given and the 4 one-link pieces are taken back;
at the end of the tenth week, the 10-link piece is given and the 4 one-link pieces as well as the 5-link piece are taken back.
Print
