Before you are 10 vases, of which 9 have identical weight, and one is either lighter or heavier (you're not sure which). You have a simple balance scale capable of holding 5 vases on each side. How can you find the odd vase in the fewest weighings AND determine if it is heavier or lighter than the other 9?
I believe I was able to do so in 3 weighings back when I first looked at this problem, but the solution was somewhat involved to explain.
Originally posted by geepamoogleFirst divided them into three groups with 3,3 and 4 as the group sizes. Then weigh the two groups with size 3. Here we have two cases, they have the same weight or they have different weights. Same weight leads to that one of the four vases in the other group is the odd one.
Before you are 10 vases, of which 9 have identical weight, and one is either lighter or heavier (you're not sure which). You have a simple balance scale capable of holding 5 vases on each side. How can you find the odd vase in the fewest weighings AND determine if it is heavier or lighter than the other 9?
I believe I was able to do so in 3 w ...[text shortened]... gs back when I first looked at this problem, but the solution was somewhat involved to explain.
For the second weighing you use one of the groups you first weight because you know that their weight is "correct" and take three vases from the four group. Let say they way different (if not so the solution is trivial) then notice if the "new" group weigh more or less.
Now take two from the "new" group and weigh them against each other and from that you easily can conclude wich one of the vases weigh different and if they weigh more or less.
If we go back after the first weighing you can do almost use the same method if the two groups weigh different.
Originally posted by luskinif the first weighing (3a v 3b) was unequal, you know the 4 unweighed are genuine.
More interesting is, what do you do if the first weighing does not balance.
and you know which of 3a or 3b was heavier (lets say 3a was heavier)
for the second weighing balance 3 genuine against 3a
case 1
3g = 3a => 3b contains a light coin
3rd weighing - weigh any 2 of 3b against each other to find the light one
case 2
3g < 3a => 3a contains a heavy coin
3rd weighing - weigh any 2 of 3a against each other to find the heavy one
case 3
3g > 3a => 3g > 3a > 3b which is not possible
Oddly enough I was thinking about it, and I think I know how to extend it to 12. With 13, however, the best you can divide the possibilities is 8/8/10, and you can't discern between 10 possibilities in 2 extra weighings reliably.
Still, you have a 12 in 13 chance of succeeding in my estimation.
My solution for 12 coins (since coins are easier I guess)
Weigh 4 against 4.
If balanced - All 8 are good, 4 suspects.
Weigh 2 suspects against a suspect and a good coin.
If balanced - Only 1 suspect left. Weigh it against a good coin to determine lighter or heavier.
If unbalanced - 3 suspects. Weigh the two suspect coins on the same side against each other, setting the third aside.
A balanced result will indicate the third coin, and you'll know lighter or heavier from the last weighing. An unbalanced coin will indicate one of the two being weighed, and you can use the results of the last weighing to determine which and heavy/light.
If unbalanced - 8 suspects - 4 possibly heavy, 4 possibly light.
Set aside 3 of the light-side coins. Weigh 2 heavy-side and a light-side against 2 heavy-side and good coin.
If balanced - 3 suspects, coin will be light. Weigh 1 against another.
If unbalanced - One of 2 possibly heavy coins, and possibly the light-side not set aside. Weigh the two potentially heavy suspects against each other. A balanced result means the light-side coin is, in fact, light.
With 9 coins, you have 18 possibilities. Each weighing you have 3 possibilities, meaning you can only discern between 9 possibilities in 2 weighings.
The reason you have double the possibilities is that each coin may be light OR heavy, and it will make a difference in results of tests.
It occurred to me that you could find the fake out of 13 coins in 3 measures *IF* you also had a 14th coin and you KNEW it was good.
The initial weighing would involve 9 of the suspect coins and the good coin (required to make the number of coins even.)
You could also extrapolate the methods towards larger numbers without much hassle at all.