In the country Curgonia, there are many types of fake coins and only a single type of genuine coins. The weights of these coins satisfy the following conditions:
- All genuine coins have the same weight
- Every fake coin is heavier than any genuine coin
- No two fake coins have the same weight
Cosmo puts 100 coins on the table and tells Fredo: "Thirty of these coins are genuine and seventy of them are fake." Then Cosmo leaves the room. On the table, there is a balance with two pans (but there are no weights).
Question: What is the smallest possible number of weighings that guarantee Fredo to identify at least one genuine coin?
Answer
As many have already stated, the best you can do is
seventy weighings.
Suppose the genuine coins have weight 0, and the other coins have weights of distinct powers of two. Then any try on the old balance will always just tip the scale to the side of the heaviest fake coin, since it weighs more than all the other coins on the scale put together.
Now suppose the scale somehow magically marked the heaviest coin on the scale with a big red X everytime you weighed some coins. Now, there is no use using the coin with an X again. Also, you've learned absolutely nothing about the other coins. Hence, even with this extra magic, the only information you can gain each time is to eliminate one coin as being fake. Thus, it takes in the worst case seventy weighings to eliminate all the fake coins and find at least one genuine one.
No comments:
Post a Comment