1. Joined
    15 Feb '07
    Moves
    667
    27 Feb '07 09:17
    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.
  2. Joined
    07 Mar '05
    Moves
    2255
    27 Feb '07 13:24
    Originally posted by geepamoogle
    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.
    First 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.

    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.
  3. Joined
    15 Feb '07
    Moves
    667
    28 Feb '07 04:30
    Nice.. The answer should be obvious, but what if both your first weighings are equal?
  4. Joined
    14 Dec '05
    Moves
    5692
    28 Feb '07 05:05
    In that case you know which one is the counterfeit, so just weigh it against a "good" one to find if it is heavy or light. More interesting is, what do you do if the first weighing does not balance.
  5. Joined
    28 Nov '05
    Moves
    24334
    28 Feb '07 09:23
    Originally posted by luskin
    More interesting is, what do you do if the first weighing does not balance.
    if the first weighing (3a v 3b) was unequal, you know the 4 unweighed are genuine.
    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
  6. Joined
    28 Nov '05
    Moves
    24334
    28 Feb '07 10:40
    or vase
  7. Joined
    14 Dec '05
    Moves
    5692
    28 Feb '07 15:42
    That seems right to me. How about the same problem but with 12 coins, You can try it at:
    http://www.mapsofconsciousness.com/12coins/
  8. Joined
    15 Feb '07
    Moves
    667
    01 Mar '07 01:061 edit
    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.
  9. Joined
    15 Feb '07
    Moves
    667
    01 Mar '07 01:414 edits
    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.
  10. Joined
    14 Dec '05
    Moves
    5692
    01 Mar '07 10:07
    Yes, I can't see anything wrong with that.
  11. Joined
    04 Feb '05
    Moves
    29132
    01 Mar '07 13:06
    yes, it is corect. if you would have 9 vases, you could do it in 2 weighings.
  12. Joined
    14 Dec '05
    Moves
    5692
    01 Mar '07 23:59
    Don't think so.
  13. Joined
    15 Feb '07
    Moves
    667
    02 Mar '07 03:49
    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.
  14. Joined
    14 Dec '05
    Moves
    5692
    02 Mar '07 06:05
    That's right. You could only do it if you know in advance whether the odd one is lighter or heavier than the others.
  15. Joined
    15 Feb '07
    Moves
    667
    04 Mar '07 06:48
    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.
Back to Top