You are given a set of scales and 90 coins. The scales are of the same type as above. You must pay $100 every time you use the scales.
The 90 coins appear to be identical. In fact, 89 of them are identical, and one is of a different weight. Your task is to identify the unusual coin and to discard it while minimizing the maximum possible cost of weighing (another task might be to minimizing the expected cost of weighing). What is your algorithm to complete this task? What is the most it can cost to identify the unusual coin?
No comments:
Post a Comment