Answer to Puzzle #2: 90 coins and an old-fashioned balance
2. 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?
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?
After years of looking for an answer I can use for this finally, with the help of Laura W, I have one I feel ready to share. The answer does rely on an understanding of the solution to question 1, or at least an acknowledgement that it exists.
Before reading the answer can I interest you in a clue?The first part is going involve us splitting the coins in to 12 piles and using the exact method from Question 1 to determine both which pile contains the unusual coin, and the nature of it's difference.
To do this we will split the coins in to piles of 8, and we'll label them individually. Pile 'A' will contain A1, A2, ... A7 & A8, Pile B will contain B1, B2 etc. Up to Pile L which will only contain 2 coins. That's OK, if we ever have to use Pile L we will just borrow 6 coins that we have already determined to be valid from one of the other groups.
Applying the procedure from question 1 will, after 3 weighings, yield us a result of the form something like Pile F is lighter, Pile K is heavier.
We then have 2 weighing and 8 coins to determine which is the odd coin. But importantly this time we know if the odd coin is heavier or lighter. Let's say the result from part one is Pile K is heavier. We will K1, K2, K3 V K4, K5, K6 should that balance we can weigh K7 V K8 and use that to identify the heavier coin.
Should it not balance and say the side K4, K5, K6 goes down then, since we know the coin we are looking for is heavy we have narrowed it down to K4, K5, K6. We can weigh any two of them against each other to determine if one of them is the heavier coin, if not it's the remaining coin.
I've seen at least 4 solutions to this puzzle, in the end this technique is actually not that hard.
5 Weighings?
The number theory approach we introduced at the end of question one can be used to show that 4 weighings is not sufficient. There is further information in the hint to this puzzle.I can't tell if the answers are correct or not.
If you're curious what Bard made of this puzzle...
If you're curious what ChatGPT made of this puzzle...
© Nigel Coldwell 2004 - – The questions on this site may be reproduced without further permission, I do not claim copyright over them. The answers are mine and may not be reproduced without my expressed prior consent. Please inquire using the link at the top of the page. Secure version of this page.
PayPal
I always think it's arrogant to add a donate button, but it has been requested. If I help you get a job though, you could buy me a pint! - nigel
