An analysis of the 12 balls problem from perspective of Information and coding theory.
Problem: Given 12 balls/coins where all are identical save one such that the odd ball can be either lighter or heavier than other normal balls. We are given a beam balance that we can use for weighing to tell which of the two pans is heavier or are balanced. Our task is to find the odd ball in minimum weighing (different question can be to do so in 3 weighing). The problem is quite common and can be solved with some persistence, but I never had patience to go through the decision tree approach.
Ans: Lets first model the problem from perspective of coding theory.
Entropy (S) = Entropy quantifies the amount of uncertainty involved in the value of a random variable or the outcome of a random process, here entropy refers to the possibilities that any of the 12 balls can be heavier or lighter . So a total of 24 outcomes .
Entropy of the system is :
We gain following information from each weighing, left pan is heavier or right pan is heavier or both are balanced. So information gained from one weighing of balance is 3, total information from three such weighing is 27.
Total Information that can be gained from three observations is :
So we can see amount of Information is greater than amount of Entropy. But it is close so we have to avoid redundancy and generate optimal codes.We will try to encode our information as function of weighing of balance.
Hamming Analysis “just a name I have given”:
We need to label each ball to track its propagation through each of the balances lets try to assign some code words from our code book.
We have gone for balanced ternary instead of binary because each balance has 3 outcomes. Size of each code word is set to be 3 because there are total of 3 balances. Total code words are 3³ = 27 as each trit can be coded in three different ways. For now let’s just assign code words corresponding to symbols 1 through 12 to the twelve balls.
Analysing 3⁰ trit we see that there are 4 code words encoded as 1 i.e {1,4,7,10} and there are 4 code words encoded as -1 i.e {2,5,8,11}.
Analysing 3¹ trit we see that there are 5 code words encoded as 1 i.e {2,3,4,11,12} and there are 3 code words encoded as -1 i.e {5,6,7}.
Analysing 3² trit we see that there are 8 code words encoded as 1 i.e {5,6,7,8,9,10,11,12} and there are 0 code words encoded as -1 .
As we can see that there is some unbalance in our codes for positions marked by trits 3¹ and 3² can we some how find other code words to balance all 3 trits. There are a total of 27 code words of which we have used 12, so there are 15 more such code words left.
Of these 15 code words 3 are useless marked by -13 {-1 -1 -1} , 0 {0,0,0}, 13{111}
On further analysis of code book 1 we find some interesting codes that can be replaced by their inverses to make our code book balanced, code word for 9 is a perfect candidate for one such transformation as it wont affect trit_0 and trit_1 and reduce imbalance at trit_2. Similarly transforming 12 does not affect trit_0 and balances trit_1 and further reduces imbalance at trit_2.
to balance trit_2 we need to find a pair of code words that counter each others effect on transformation to their inverse as trit_0 and trit_1 are already balanced as well as remove imbalance at trit_2. We find a candidate pair as 7 and 11.
lets take a look at our new code book
Upon application of above mentioned transformation it is easy to see that all 3 trits are balanced.
Interpretation of above code words
properties of the new code book
- 12 rows of 3 columns each, one row for each ball.
- each column has exactly 4 encodings of {-1, 0, 1}.
- for each code word its inverse is not allowed in the code book.
Interpretation
- Each code word tells how a ball participates in balances ex for ball marked as -12 i.e {-1-10} is as follows:
during weighing at trit_2 it goes to right balance , during weighing at trit_1 it goes to right balance, and it remains as a bystander diring weighing at trit_0.
2. Interpreting result of balance based on outcomes of the weighing let us say the result was {-1 -1 0} then coin marked as -12 is odd one out and is heavier, But what if 12 was lighter then outcomes would be {1 1 0} i.e 12 it does not exist in our new code book. This is interpreted as the odd ball is still ball no 12 but it is lighter.
Participants at each balance encoded as per code book
result of a balance weighing is encoded as side that was heavier if left is heavier result will be 1 else if right is heavier result is -1 , else result is 0
Simulation: let ball 6 be the odd ball and lighter then evaluating at 3² gives -1, evaluating at 3¹ gives result as 1 and 0 at 3⁰, i.e code word after 3 weighing is {-1 1 0} which is -6 which is right from our interpretation ball is correctly identified but the data whether ball is heavier or not is decided by if ball is present in code book if so heavier else if it is an inverse of code word the ball is lighter.
