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