Monday, December 7, 2009

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

0 comments:

Post a Comment