In a pile, there are 11 coins: 10 coins of common weight and one coin of different weight (lighter or heavier). They all look similar.

Using only a balance beam for only three times, show how you can determine the 'odd' coin.

Open problem (i cannot solve this myself): how many more coins (with the same weight as the ten) can we add to that pile so that three weighing still suffices? My conjecture is zero, though my friend guessed that adding one is possible. The best bound we can agree upon is < 2.

(In reply to Solution for 13 coins!!! by Morgan)

Interesting.  This solution relies on not acgtually determining whether the odd coin out is heavier or lighter.  Thus, the maximum number of possibilities (10) that can be handled if the first weighing is balanced is beyond what seems like the theoretical limit of 9.  Of course this is because two of the possibilities are not distinguished.

13 is the limit.

once a coin has been in a weighing if we know it is the odd one we know if it is heavier or lighter.  Thus this trick can only work for reducing the possibility limit by one.  (if there are two coins that are not weighed we can't know which is odd).  By this logic 14 coins (28 possibilities / 2 possibilities per coin) cannot be exceeded.

However, the first weighing must be k coins vs k coins yielding an even number of possibilities if it is uneven (either way).  Thus, the maximum number of possibilities that might be handled (9) cannot be reached so we get 13 as the limit.  If we had another coin we knew was proper weight we could weigh 5 vs 4+1 and get 9 in each case thus handling 14 coins be we don't have that coin.

So, given a general n, the first weighing must be at most k vs k where 2k=3^(n-1)-1 and the excess coins cannot exceed k+1 (using the trick with coin down the all even path)

The answer in general then is that ((3^n)-1)/2 coins can be handled which is oddly what I would have thought immediately (3^n-1 possibilities) but for the wrong reasons ( one effect reduces it by one and the other increases it by one )

Posted by Joel on 2006-11-12 23:21:03