Re: can Huffman coding method be used to coin weighing problem?

From: Martin Penderis (tafeltennis_at_mwpenderis.mailshell.com)
Date: 02/17/05 

Date: 17 Feb 2005 09:46:58 -0800

I have no idea what the Huffman coding scheme is. Here is my input.
Name the coins A, B, C, D, E, F, G, H, I, J, K, L.
First weighing:
Weigh A, B, C, D against E, F, G, H.
Second weighing:
If mass(A, B, C, D)=mass(E, F, G, H), weigh I, J, K against A, B, C.
If mass(A, B, C, D)> mass(E, F, G, H), weigh A, B, G against C, D, E.
If mass(A, B, C, D)< mass(E, F, G, H), weigh A, B, G against C, D, E.
Third weighing:
If mass(I, J, K)=mass(A, B, C), weigh L against A. If mass(L)=mass(A),
then there is no counterfeit coin. Otherwise L is the counterfeit
coin.
If mass(I, J, K)>mass(A, B, C), weigh I against J. If
mass(I)=mass(J), then K is the counterfeit coin. If mass(I)>mass(J),
then I is the counterfeit coin. If mass(I)<mass(J), then J is the
counterfeit coin.
If mass(I, J, K)<mass(A, B, C), weigh I against J. If
mass(I)=mass(J), then K is the counterfeit coin. If mass(I)<mass(J),
then I is the counterfeit coin. If mass(I)>mass(J), then J is the
counterfeit coin.
For mass(A, B, C, D)> mass(E, F, G, H):
If mass(A, B, G)=mass(C, D, E), weigh F against A. If there is a
difference, then F is the counterfeit coin. Otherwise H is the
counterfeit coin.
If mass(A, B, G)>mass(C, D, E), weigh A against B. If mass(A)>mass(B),
then A is the counterfeit coin. If mass(A)<mass(B), then B is the
counterfeit coin. If mass(A)=mass(B), then E is the counterfeit coin.
If mass(A, B, G)<mass(C, D, E), weigh C against D. If mass(C)>mass(D),
then C is the counterfeit coin. If mass(C)<mass(D), then D is the
counterfeit coin. If mass(C)=mass(D), then G is the counterfeit
coin.
For mass(A, B, C, D)< mass(E, F, G, H):
If mass(A, B, G)=mass(C, D, E), weigh F against A. If there is a
difference, then F is the counterfeit coin. Otherwise H is the
counterfeit coin.
If mass(A, B, G)<mass(C, D, E), weigh A against B. If mass(A)<mass(B),
then A is the counterfeit coin. If mass(A)>mass(B), then B is the
counterfeit coin. If mass(A)=mass(B), then E is the counterfeit coin.
If mass(A, B, G)>mass(C, D, E), weigh C against D. If mass(C)<mass(D),
then C is the counterfeit coin. If mass(C)>mass(D), then D is the
counterfeit coin. If mass(C)=mass(D), then G is the counterfeit
coin.

lucy wrote:
> Suppose one has n coins, among which there may or may not be ONE
counterfeit
> coin.
> If there is a counterfeit coin, it may be either heavier or lighter
than the
> other coins.
> The coins are to be weighed by a balance.
>
> What is the coin weighing strategy for k = 3 weighings and 12 coins?
>
> I am trying to figure this weighing scheme out by using optimal
Huffman
> coding scheme to achieve the minimal code length...
>
> How to do that?