Suppose you are given a collection of gold coins that includes a clever counterfeit coin (all the rest are genuine). The counterfeit coin is indistinguishable from the real coins in all measurable characteristics except weight. You have a scale with which you can compare the relative weights of coins. However, you do not know whether the counterfeit coin is heavier or lighter that the real coins. Your problem is to find the counterfeit coin and determine whether it is lighter or heavier than the rest. 1) Show that if there are 12 coins, the counterfeit coin can be found in three weighings. 2) Show that if there are 39 coins, the counterfeit coin can be found in four weighings 3) Show that if there are n >= 3 coins, the counterfeit coin can be found in log_3 2n weighings.
Suppose you are given a collection of gold coins that includes a clever counterfeit coin (all the rest are genuine). The counterfeit coin is indistinguishable from the real coins in all measurable characteristics except weight. You have a scale with which you can compare the relative weights of coins. However, you do not know whether the counterfeit coin is heavier or lighter that the real coins. Your problem is to find the counterfeit coin and determine whether it is lighter or heavier than the rest.
1) Show that if there are 12 coins, the counterfeit coin can be found in three weighings.
2) Show that if there are 39 coins, the counterfeit coin can be found in four weighings
3) Show that if there are n >= 3 coins, the counterfeit coin can be found in log_3 2n weighings.
Trending now
This is a popular solution!
Step by step
Solved in 7 steps
