There are 80 pieces of gold. One of them is lighter. You can weigh only 4 times to find out which one is lighter.
Think from bottom to up, one time measure, we can find out 1 lighter out of 3, one more time measure, we can find lighter coin within 3 coins out of 9 coins...
1 1 1
3 3 3
9 9 9
27 27 27
So 4 times is enough to find the one lighter coin out of 81 coins, log_3(N)
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment