Suppose you have 12 coins, 11 of which are identical and one which is fake. The fake coin differs from the 11 others only in that its mass is imperceptibly different (it may be slightly more or slightly less -- you're not sure).
You have a perfectly accurate and sufficiently sensitive balance which can only tell you two pieces of information: 1) whether or not the two sides have equal mass 2) if the two sides do not have equal mass, the balance tells you which side has more mass.
In general, what is the fewest number of times you need to use the balance in order to determine which of the 12 coins is fake?
You are only allowed to use the 12 coins and the balance I have described. You are not allowed to use other weights or balances, to cut coins, etc, etc.
there isn't an exact minimum # of steps, based on chance, but if everything went wrong, the maximum minimum (heh) would be the following:
(coins: ABCDEFGHIJKL)
step 1: weigh coins ABC vs. DEF finding they are equal (we now know ABCDEF are normal)
step 2: weigh coins GHI vs. ABC finding they are equal (we now know coins GHI are normal as well)
step 3: weigh J vs. K finding they are different (so one must be irregular)
step 4: weighing J vs. any coin except K (if same, K is irregular, if different J is irregular)
Is there a faster weigh (sic) ? 😉
Originally posted by slippytoadYour method involves 4 weighings, but Vengoropatubus is right when he says that you at most need only 3 weighings (even in the general case when "everything goes wrong" as you alluded to).
there isn't an exact minimum # of steps, based on chance, but if everything went wrong, the maximum minimum (heh) would be the following:
(coins: ABCDEFGHIJKL)
step 1: weigh coins ABC vs. DEF finding they are equal (we now know ABCDEF are normal)
step 2: weigh coins GHI vs. ABC finding they are equal (we now know coins GHI are normal as well)
step ...[text shortened]... t K (if same, K is irregular, if different J is irregular)
Is there a faster weigh (sic) ? 😉
Vengoropatubus didn't post a solution for the general method, and I don't want to post the solution yet either, to give other people some more time to think about the problem...
it took me a long time to figure the solution out...i don't know if it's because it's tricky or because i'm slow...it's probably both 😀
Originally posted by davegageI can see three steps, easily, if one knows that the fake coin is heavier.
Your method involves 4 weighings, but Vengoropatubus is right when he says that you at most need only 3 weighings (even in the general case when "everything goes wrong" as you alluded to).
Vengoropatubus didn't post a solution for th ...[text shortened]... because it's tricky or because i'm slow...it's probably both 😀
I can see three steps, easily, if one knows that the fake coin is lighter.
I'd love to see the three-step method when one doesn't know whether it is heavier or lighter, specifically.
I can do three steps with 9 > or < weight coins, though not twelve. Yet.
Wait, I'm seeing it now. I guess you can weigh 6 different sets of four coins (accounting for three weighings), then deduce which coin weighs more or less based on the results (such as <<=, >>>, etc.).
I don't want to work out which four coins to put in each set, because it would just involve trial and error for me and drive me crazy. Is there a logical way to work out which sets to use?
Originally posted by slippytoadthis method of testing 6 different sets of 4 coins will not work (at least not for only 3 uses of the balance), but the good news is that you are on the right track...
Wait, I'm seeing it now. I guess you can weigh 6 different sets of four coins (accounting for three weighings), then deduce which coin weighs more or less based on the results (such as <<=, >>>, etc.).
I don't want to work out which four coins to put in each set, because it would just involve trial and error for me and drive me crazy. Is there a logical way to work out which sets to use?
a hint:
--the general solution i have in mind does begin with weighing two sets of 4 against each other as step one.
are you sure?
i'll clarify... start with something along the lines of ABCD vs. IJKL, then two more balances (and combinations), then figuring, based on the sets and results, which coin is indeed lighter or heavier.
for instance:
ABCD weighs more than IJKL
AEFG weighs more than BDJK
ACEG weighs more than BDFH
by which we could conclude (if I had the proper sets which accounted for each coin) that A must be the fake coin, which happens to weigh more.
Originally posted by slippytoadhmmm...let me think about that.
are you sure?
i'll clarify... start with something along the lines of ABCD vs. IJKL, then two more balances (and combinations), then figuring, based on the sets and results, which coin is indeed lighter or heavier.
for instance:
...[text shortened]... h coin) that A must be the fake coin, which happens to weigh more.
Originally posted by slippytoadSlippytoad: your approach works; but you have only shown it works for a specific case...if you can generalize your approach, then you will have found my general solution.
are you sure?
i'll clarify... start with something along the lines of ABCD vs. IJKL, then two more balances (and combinations), then figuring, based on the sets and results, which coin is indeed lighter or heavier.
for instance:
...[text shortened]... h coin) that A must be the fake coin, which happens to weigh more.
For example, consider that your example could also run like this:
ABCD weighs more than IJKL
AEFG weighs the same as BDJK
Uh-oh...Now we know that the fake coin is either C, I, or L.
With only one more use of the balance, can you determine which one it is?
In fact, you can, and if you see how, then I'm guessing you will quickly be able to see the general full solution...
EDIT: I was wrong earlier to say that your approach would not work; in fact, my general solution is basically the same approach and is just a systematic way to figure out what sets of 4 to pit against each other. still, the difficulty of the problem lies in being able to generalize the approach. I think if you can figure out the above example I provided, it will be a HUGE hint 😀