Counterfeit coin of unknown weight: Eight balancing (edited)

Let's solve the more general problem of having $n$ weighings, to find out the maximum number of coins so that we can still identify which coin is the counterfeit (but we don't need to identify whether the counterfeit coin is heavier or lighter).

For each weighing, there could be three possible results: left-heavy, right-heavy, or balanced. Let's assign the value 1 to left-heavy, 2 to right-heavy, and 0 to balanced. Then let's consider the ternary number formed by the sequence of weighing results. For example, if in three weighings we have left-heavy, right-heavy, and right-heavy, then the corresponding number is $122$ . Clearly, there are $3^n$ possible ternary numbers given $n$ weighings. For example for $n=3$ we have: $000, 001, 002, 010, 011, 012, 020, 021, 022, 100, 101, 102, 110, 111, 112, 120, 121, 122, 200, 201, 202, 210, 211, 212, 220, 221, 222$ .

Now, let's consider the case when we know that the counterfeit is definitely heavier. We can then assign a number to each coin, and based on the ternary representation of the number, at the $i$ -th weighing, we put the coin on the left-pan if the $i$ -th digit (or more accurately: trit) is 1, on the right-pan if the $i$ -th digit is 2, and do not weigh it if the $i$ -th digit is 0. Note that this system will result in the same number of coins in each pan for each weighing, since for each coin there will be its symmetry assigned on the opposite pan in all weighings. This is important, as if there are different number of coins in the left and right pans, then it will never be balanced. Now, each weighing sequence will then correspond to a coin, and we can identify the coin simply by looking at the ternary number formed by the weighing sequence. So in this case we can weigh at maximum $3^n$ coins.

Now, coming back to the case where we don't know whether the counterfeit is heavier or lighter. Since we do not know whether placing a coin on the left-pan will yield left-heavy or right-heavy, we cannot assign a ternary number and its symmetry (by interchanging 1 and 2) to different coins. For example, if coin $c_1$ is given the number $112$ and coin $c_2$ the number $221$ , and the weighing result is $112$ , we won't be able to distinguish whether it is because coin $c_1$ is counterfeit and heavier, or because coin $c_2$ is counterfeit and lighter. Therefore, we need to assign two ternary numbers for each coin, a number and its symmetry (note that sequence of all zeros do not have a symmetry), and we can pick either of them as the placement configuration for that coin. Now, if we use all the $3^n$ numbers, each trit will appear $3^{n-1}$ times. But this is an odd number, and therefore will not lead to the same number of coins for each weighing. So we need to remove at least one number (and its symmetry) and it should have at least one non-zero trit. This left us with at most $3^n-2$ numbers. Since the ternary number 0 does not have a symmetry, we have $3^n-3$ numbers with symmetry, plus the ternary number 0. So in total we can have at most $\frac{3^n-3}{2}+1$ coins.

Now the problem reduces to the question of whether we can assign the numbers in a way that we always have the same number of coins on the left and right pans at each weighing. This is left as an exercise for the readers.

Given this formula, plugging in $n=8$ gives us: $\frac{3^8-3}{2}+1 = 3280$ .

When weighing, there are three possible results, which are: left pan being heavier, left pan being lighter, or that the pan has equal weight. So if it's possible to shrink the number of suspects to ceiling of a third in one weighing, the method should be optimal. When weighing, we can also label the suspects with (+) for the one possibly heavier, and (-) for the one possibly lighter. Some might be unlabeled, for example if these are not yet being weighed at all.

Assume the condition in which we have n labeled coins with similar number of (+) coin and (-) coin or almost similar number (the difference is at most 1 coin), and two coins already known to be normal. It will be shown that we can create algorithm to optimally shrink the number of suspects into ceiling of n/3 coins with similar or almost similar number of (+) or (-). First, divide n into three groups of coins sized floor of n/3 or ceiling of n/3 (the three groups don't have to be of equal size). It's easy to prove that we can arrange such that each group can have equal (+) and (-) or at least almost similar number (if there is a group with too different composition of (+) and (-), we can just trade members with another group). After that, we can leave the first group unbalanced, then put the (+) in second group in left pan, the (-) from the third group in left pan, the (-) from the second group in the right pan, and the (+) of the third group in the right pan. The two normal coins can be added to make the number of coins in the pan is equal. Now we can tell which group is at fault from the weighing result. If the pan weighs the same, the first group contains the different coin. If the left pan is heavier, the second group is at fault, and if right pan is heavier, the third group is at fault. This way, we can definitely shrink n labeled coins to at most ceiling of n/3 suspects.

With this algorithm, if we have 7 weighings, we can definitely shrink number of suspects to 1 only if we have at most 2187 labeled coins (3^7) before the 7 weighings. Thus, after the first weighing, in case the pan weighs differently, we can only handle 2187 labeled coins. However, since during the first weighing we do not have coins already known as normal, we can only weigh 1093 coins vs 1093 coins to avoid getting 2188 labeled coins or more. Thus, in the first weighing, we need to weigh 2186 coins, and m coins that we can still handle in 7 weighings in case the pan weighs similar. In the case both pan weighs similar, among m coins we need to weigh a certain number of coins such that if in the second weighing the pans weigh different, we can handle the labeled coins in 6 weighings. As we have discussed before, the number should be at most 729 coins to be labeled. However, since this is the second weighing, we already have normal weighed coins, so we can balance 364 unweighed coin + 1 normal coin against 365 unweighed coins.

And again, a fraction remains unweighed, and we need to ensure those can still be handled in six weighings. With the same logic, if the second weighing, the pan still weighs the same, we can weigh 243 unweighed coins with the help of 1 normal coin (121 unweighed coins + 1 normal coins against 122 unweighed coins).

With this logic, the most number of suspects we can handle in 8 weighing is: 2186+729+243+81+27+9+3+2 (2 is the most number of coins such that we can find the suspect in just 1 weighing, in case the first seven weighings all weigh the same).

It will be easier to explain with the help of image, but I can't find a way to upload image in answer section.