Here is a fun math statistic/probability question

[firstwave]

My grade 12 math teacher gave us a question that I found to be very interesting.

You have 12 identical keys. 11 of the 12 keys have the same mass. Only one of them has a different mass. You have a scale, but it is not digital and it does not tell you the actual weight. It only shows you which one of the two sides is heavier. You are allowed 3 uses of the scale. How do you determine which key has a different mass?

I found this question to be very interesting, but unfortunately, I can't solve it. How about you guys?

 

[Tide]

HINT: Start by comparing the weight of two groups of 4 keys.

 

[firstwave]

Hmm, I don't think that works. If I compare two groups of 4 keys, there are 2 possible outcomes.

Either one side is different or both groups weigh the same. If the outcome is the former, I still need to use the scale once more to determine which one of the three groups contains the different key. The problem is that knowing which side is heavier or light does not necessarily help because we don't know if the "special" key is ligher or heavier than the other 11 keys.

Maybe I am perceiving this wrong, so please enlighten me :)

 

[Tide]

Okay,

If the two sets of four do not balance then you eliminate the third (unweighed) set so we'll set them aside.

Label the set of heavier keys as 1, 2, 3 and 4 and the lighter set 5, 6, 7 and 8. Now remove 7 & 8 from (say) the right side (and remember they were part of the lighter set!) and swap 5 and 4 so you are now comparing 1, 2 and 5 with 3, 4 and 6. This is the second weighing.

Now, if 1, 2 and 5 balance with 3, 4 and 6 then one of 7 and 8 is the special key and will be the lighter of the two (recall the note above!) - you find which one it is by a third weighing.

However, if 1, 2 and 5 do not balance then you eliminate 7 and 8.

Recall that 1, 2 and 5 came from the heavier side of the first weighing so that if 1, 2 and 5 are heavier than 3, 4 and 6, then 3 and 4 are ordinary keys so that 1 and 2 are potentially heavier while 6 is potentially lighter (recall it came from the light side of the first weighing). A third weighing comparing 1 and 2 tells you that if 1 and 2 are the same then 6 is the a heavy key and if 1 and 2 are not the same then the heavier of the two is the odd key.

On the other hand, if 1, 2 and 5 are lighter than 3, 4 and 6 then 1, 2 and 6 are ordinary keys while 5 is potentially lighter and 3 and 4 are potentially heavier. Finally, compare 3 and 4 (third weighing!). If they are the same then 5 is the special key and if they are not the same then the heavier of 3 and 4 is a heavy key.

I'll leave it to you to decide the case when 1, 2, 3 and 4 balance with 5, 6, 7 and 8. :)

 

[firstwave]

Ohhhh right. I forgot that if two sets of four do not balance, you can eliminate the third set. Thanks for your insightful solutions :)

 

[Curious3141]

This is a different statement of a classic weighing problem (which uses coins, not keys).

There is a beautifully elegant and methodical solution for this problem and the general class of problem.

Read Lars Prins' method (at the bottom) for the 12-coin problem : http://mathforum.org/library/drmath/view/55618.html

In general, with n weighings, you can find the odd coin out of (at most) \frac{3^n - 3}{2} coins. You can read the general solution from here (the first part) : http://www.cut-the-knot.org/blue/OddCoinProblemsShort.shtml