This is a problem that is extensively discussed on the internet. Here we will provide a solution to the general case which is from a paper by Freeman Dyson.
This is the way the problem is generally posed: You have four to twelve coins and a weighing balance but no weights. All of the coins have the same weight except one which is either lighter or heavier but you do not know which). In how many weightings can you identify the defective coin?
The usual solution proceeds as follows:
Only three weightings are necessary for 4-12 coins. We will sketch the cases with 4 and 12 coins.
4 Coins:
· Label the 4 coins c1, c2, c3, c4. Weigh c1 against c2.
If they balance, the defective coin is either c3 or c4. In this case, weigh c3 against c1.
If they balance, c4 is defective and weighting it against one of the others will determine if it is heavier or lighter.
If c1 and c2 do not balance, weigh them one by one against c3 to identify both the defective coin and whether it is heavier or lighter.
12 coins:
If there are 12 coins, compare the weights of two sets of 4 coins.
If they do not balance, label the coins h1,h2,h3,h4 and l1,l2,l3,l4 depending on which 4 were higher or lower weight.
Now weigh h1,h2,l1 vs h3,h4,l2. If they balance, the defective coin is either l3 or l4 and can be found in one weighting.
If they do not balance, say h1, h2, l1 is heavier, then the defective coin is either h1, h2 or l2. Now we compare h1 and h2. If they balance, defective coin is l2. If they do not balance, the heavier of the two coins h1 or h2 is defective.
If instead the initial sets of 4 coins balanced, then they are good coins, and the defective coin is in the remaining four. Label these c1,c2,c3,c4 and let us use a coin labeled c from the initial weighing to find the defective coin within these 4 coins as follows:
Weigh (c1,c2) vs (c3,c). If they balance, then c4 is defective and it can be weighed against c to see if it is lighter or heavier. If (c1,c2) vs (c3,c) do not balance, we can assume without loss of generality that (c1,c2) are heavier then (c3,c). Now weigh c1 vs c2. Whichever is heavier is the defective coin. If c1 vs c2 balances, then the defective coin is c3 and is lighter.
https://en.wikipedia.org/wiki/Freeman_Dyson
Dyson’s General Solution for any number of coins: The general solution was provided by Freeman Dyson in a 1946 paper. Reference: The Mathematical Gazette, (Oct., 1946, Vol. 30, No. 291, pp. 231-234.
The method used by Dyson is an example of optimum coding. Dyson first showed that if M = (3n-3)/2, then the defective coin can be found in n weightings (including determining whether it is heavier or lighter). We will sketch the proof for n = 3, M = 12. where in three weightings it is possible to identify a defective coin in up to 12 coins. We start by considering all possible labels in base 3 from 001 to 221, skipping the mappings 000, 111 and 222. Now we start by assigning sequential labels for the 12 coins: 001, 002, 010, 011, 020, 021, 022, 100, 101, 102, 110. Next, we convert these to “cyclic labels”, where cyclic means that the labeling for each of the coins read from left to right must have 01, 12 and 20. Such cyclic labels are generated by swapping 0 and 2 in the original labels. This converts the labeling of the twelve coins to: 001, 220, 010, 011, 012, 202, 201, 200,122, 121,120,112 where the ones converted to cyclic order are in bold. We now group these labels into 4 sets of 3 so that each of three labels in a set are obtained by permuting 0 to 1, 1 to 2 and 2 to 0. The four sets are (001, 112, 220), (010,121,202), (011,122,200) and (012,120,201).
As an example, we show how to find the defective coin among six coins. For this we choose two sets of three cyclic permutation labels to label the coins.
Label of Coin 1: 001
Label of Coin 2: 112
Label of Coin 3: 220
Label of Coin 4: 010
Label of Coin 5: 121
Label of Coin 6: 202
The column labels correspond to the three weighting rules for the coins: If the label is 0, 2 the coin is placed in the left or right pan respectively. If in the weighting, the left/right hand pan is heavier, we call the result 0/2 respectively. If the pans balance, call the result 1. After the three weightings, the result will represent either the code of the coin or its complement (obtained by switching 0 and 2). If the code matches the assigned code, the coin was heavier. If the code is the complement of the assigned code, the coin was lighter.
Let us see how this works. Suppose coin 1 is heavier. Going column wise, in the first weighting, we put coins 1,4 in the left pan and 3,6 in the right pan. The left pan will be heavier, so we get 0 as the result. In the second weighting, we put coins 1,6 in the left pan and 3,5 in the right pan. The left pan is heavier, so we get 0 as the result again, and the two results together are 00. In the third weighting, we put 3,4 in the left pan and 2 and 6 in the right pan. The coins will balance, so we get the result 1. The complete result is 001, which is the label of coin 1. It also shows that this coin is heavier. If coin 1 were lighter, it is easy to see that the result would have been 221, which is the complement of 001.
Dyson also showed that for M in the interval 3 < M < (3n-3)/2, then n weightings are sufficient. The Table above summarizes some of the results. For details, please read his paper referenced above.