Of Coins and Balances

Exploration of counterfeit coin problems using Information Theory.An interesting question whose solution eludes if some key observations are not made. Analysis of the question will provide some key insights for application of Information Theory to such kinds of problems as a whole.

Problem: Given 3 pairs of coins such that each pair is uniquely marked and in each pair there is a fake coin which is lighter than perfect coin. Find all the fake coins with 2 weighing of the balance i.e coins are A{A1, A2}, B{B1 ,B2} & C{C1,C2}. Problem Source. Try to solve it on your own first to get the feel of problem.

Solution: Lets begin with quantifying the entropy of the system. Each pair has 2 balls any of which can be fake there are 3 such pairs do Entropy S= 2*2*2= 8. Amount of Information that can be gathered from 2 weighing is I =3*3 = 9. So Information is greater than Entropy of the system so it can be solved.

So we have to concoct a strategy to find a solution.

Strategy 1- what if we find the nature of ball in any pair first let it be in A and use this defined state of ball to use in further weighing. Compare A1 with A2 this will give us the correct ball, but now we are faced to solve for state of balls from B and C that have entropy of 4 and amount of information that we will get is 3 so this strategy is futile.

Strategy 2- let us consider 2 pairs i.e A and B with following distribution A1,B1 vs A2,B2 will have the following configurations.

As you can see 2 & 3 configurations remain unsolved but can be solved if weigh next balance as A1,B2 VS A2,B1. But we have already used the 2 weighing and have not found out the nature of coins in C so this strategy is not promising.

Strategy 3- let us weigh the balances as C1,A1 VS C2,B1. There are a total of 8 possible states.

So on a cursory glance even this weighing strategy does not help us as for only 2 outcomes 3&6 can we assign well defined states to coins from each pairs, also how do we differentiate these outcomes from 1,4,5&8 as we only get information as left or right is heavier. And what about outcomes 2 and 7 looks like we are doomed as we will need a total of 3 weighing.

But a more detailed look will reveal a very crucial observation, observe that there is a correlation between the result of balance and nature of balls of pair C if balance is right heavy then C2 is heavy and if balance is left heavy then C1 is heavy. So we have actually managed to identify the nature of coins in C now we are left to determine the nature of coins from A and B. This leads us to problem of how to figure out a way to differentiate between A1 AND B1 The possible states are generated from first balance involving C1,A1 VS C2,B1 of which we have already solved C so we solve the leftover part of A1 vs B1. I will show how to do it if right is heavy similar arguments can be made if left is heavy and use of similar transformations.

We could have simply compared A1 VS B1 but we would not be able to differentiate between 1 and 3 above as both sides are equal so unable to tell if coins are light or heavy type. This can be solved if we make comparison as A2 vs B1 what this transformation does is transforms the i, ii, iii above to

From i and iii we will be clearly able to tell the state of A2 and B1 but what about ii we can argue that following this series of transformation, equality will always tell that coins are of heavy type as the similar state L VS L is unreachable , so we have solved problem for 1,3,4,5,6&8 in 2 weighings.

What about if outcome of first weighing is of form 2 and 7, we can make another key observation that state of A1 is always equal to state of C2 , So our next weighing will be C2 VS B1 this will help us in identifying the state of C2 and B1 and with help of our last observation the state of A1.

So we have solved the problem that looked impossible with some clever observations in 2 weighing.

LESSONS

  • CONJECTURE- THERE CAN BE NO PARALLEL WEIGHING STRATEGY IF TOTAL ENTROPY IS NOT DIVISIBLE BY INFORMATION GAINED IN 1 WEIGHING.
  • We could have come up with strategy 3 faster if we had analysed every strategy using information theory.
  • Strategy 1 after first weighing would have got 2 info but for next weighing entropy was 4 and max information that could have been gained would be 3 so we would be stuck.
  • Strategy 2 after 1st weighing had an entropy of 4 and gave 2 information leaving 2 entropy and for next weighing there would have been a gain of 2 more entropy . So total entropy for next weighing would be 4 at expense of 3 information we would be stuck again.
  • Strategy 3 after first weighing that had entropy of 8
  1. For 6 unbalanced outcomes we gain 2 information of C and in next weighing we have to find states of A and B that looks like entropy of 4 but in reality as we have seen is 3 because 1 is a forbidden state , So 3 entropy could be done in 2nd weighing as it will give 3 information.
  2. For 2 balanced outcomes we gain info that C and A on opposite side are of same state so if we solve C we will get A for free . It looks that entropy of 2nd weighing is 4 if so we will be stuck but we also have observation that B and A are in opposite states therefore B is also in opposite state from C. So in actual the Entropy for 2nd weighing is just 2 which can be gained in 1 weighing.

Reach for the sky