This problem is a combination of a traditional weights and scales puzzle and a probability puzzle.
You are given the traditional scale balance and a set of 10 coins. You know that in this set of coins there are four fakes - two that are heavier than the others, and two that are lighter. Furthermore, you know that a light coin plus a heavy coin will perfectly balance two genuine coins. You are permitted only two weighings with the balance and asked to pick one of the 4 fake coins. What strategy should you use to maximize your success rate, and what would your success rate be?
What if you were given one genuine coin to start with (though still leaving you with 10 unknown coins)?
(In reply to
~50% by ryan smith)
Good strategy, but I get over 82% this way unless I am doing something seriously wrong.
I get lost in all the combinations, so I wrote a program. Here are my results:
I arrange the coins in a row, and number them 1-10. Each coin is either "+", "-" or "0" (two each of +/-, six 0). There are 1260 distinct arrangements (10! permutations, but 4*6! of each are indistinguishable). Of these 1260 cases, I put together a matrix of weighings: weigh coin 1 against 2, then 1 against 3. There are 9 possible outcomes: (left,left), (left,even), etc,
where "left" means the first of the two is heavy, "even" they balance, "right" the second of the two is heavy.
Of the 1260 combinations, I get the following weight matrix (number of combinations that give each result):
left,left = 217
left,even = 133
left,right= 42
even,left = 133
even,even = 210
even,right= 133
right,left = 42
right,even = 133
right,right= 217
In each of the nine cases, I also counted the number of times each of the 10 coins was phony. For example, in the (left,left) weighing, 196 times out of 217 the first coin is phony. (since it is heavier both times, there are very few cases where it is real and both the second and third coins are light).
So I computed probabilities as follows:
For each of the 9 cases, always pick the coin which has the highest number of cases of being phony. Add these up over all 9 possibilities, and divide by the number of combinations. This will compute, over all combinations, the number of times I can guess a phony coin. The best coin to pick in each of the 9 cases (along with the number of times it is phony) are:
left,left = coin 1 (196/217)
left,even = coin 2 (112/133)
left,right= coin 2 or 3 (42/42)
even,left = coin 3 (112/133)
even,even = coin 3 or higher (120/210)
even,right= coin 3 (112/133)
right,left = coin 2 or 3 (42/42)
right,even = coin 2 (112/133)
right,right= coin 1 (196/217)
In total, I compute that a phony coin can be found 1044 times out of 1260, or 82.85%
This seems quite high to me (much better than I was able to do weighing 4 vs 4 or 3 vs 3 or 2 vs 2).
In the case of having 1 known good coin, you can weigh it against 1 then 2. 2/3 of the time one of these two will be bad, and you are sure to be right. The other third of the time, pick one of the remaining 8 and you have a 50% chance. Total chance then becomes 5/6, or 83.3%
If I did everything right, this really isn't much better, which is surprising.
Does this all sound right? I'll be happy to email my code (in C) to anyone who wants to check it out. It is a bit sloppy, but pretty short.
re: ~50%
