Chain Cut Problem

Problem:

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

Solution:

Assume that a chain of length k for every 1<=k<=length(chain)  
  must be doable with the open links. Then you can reach  
  
  **links  length    dissection**  
  
    0      1         1  
    1      5         1-(1)-3  
    2     13         1-(1)-3-(1)-7  
    3     29         1-(1)-3-(1)-7-(1)-15  
    4     61         1-(1)-3-(1)-7-(1)-15-(1)-31  
    n   2^(n+2)-3

we have taken links as 2^k-1...and hence get such answer.

The question can be modified a bit...

You are having 31kg of rice. You are provided with a 1kg stone for weighing. In how many weights the 31kg of rice can be weighed.

Now we can't have empty selection...so for

n we have 2^(n+1)-3…

so we have 2^(n+1)-3 = 31

n+1 = 6 (because 2^5 < 35 < 2^6 )

n=5
```

Problem:

Solution:

See also