From: yuen@bhprtc.scpd.oz.au (Daniel Yuen)
Subject: Re: Another fun problem (SOLUTION)
Organization: BHP Steel, Sheet & Coil, Research & Technology Centre
Date: Tue, 5 Jan 93 06:12:16 GMT

wshi@ponder.csci.unt.edu (Weiping Shi) writes:

WS> In <1993Jan4.023037.7729@bhprtc.scpd.oz.au> yuen@bhprtc.scpd.oz.au (Daniel Yuen) writes:

DY> Can you pick a bad ball among 13 balls *and* identify if it is heavier 
DY> or lighter in 3 weighings ?  If not, can you *prove* that it can't be 
DY> done?
DY> My solution says that it can't be done.  However, I received an e-mail
DY> indicating that this problem has been solved and that it has been shown
DY> (or *proved*) that it could be done.  If so, I'd love to see someone post
DY> a 'counter-solution' or send me an e-mail.

WS> The solution can be found in "Combinatorial Algorithms",
WS> by E. Reingold, Nievergelt and Deo.

The quoted reference does give a reasonble discussion of the generalisation
of this problem.  Since there appears to be some confusion of whether the 
problem can be solved, I reproduce the theorems stated in the quoted 
reference (pp 18 & 19) below, with my comments in brackets :

Theorem 1.3
^^^^^^^^^^^
It is *impossible* to solve the n-coin problem with m comparisons,
*without* using coin 0, if n >= (3^m-1)/2.
(NOTE : "Coin 0" refers to an extra standard coin)

Theroem 1.4
^^^^^^^^^^^
It is *possible* to solve the n-coin problem with m comparisons if
n <= (3^m-1)/2.
(NOTE : The implicit assumption here is that a "coin 0" is used.)

Hence, for our problem, it can be solved *only* if an extra standard ball
is available.

DY> Here goes my solution :
DY> 7. However, for the first weighing, we could not have P(LH)=P(LL)=P(BE)=1/3.
DY>    The best we could do is to have 4 balls on each side of the balance, in
DY>    which case P(LH)=P(LL)=4/13 and P(BE)=5/13.  Thus, maximum probability
DY>    is P(BE) and information deduced from this weighing is only
DY>    log2(13/5) = 1.379 bits

WS> The proof here is wrong.  The information you can get here is
WS> $$
WS> 	\sum_{i=1}^3 - p_i \log_2 p_i
WS> $$
WS> This is the definition of entropy, and since you can reduce
WS> this much entropy, by definition, you gain this much information.

The quoted formula is indeed the entropy function, and is a measure of
the degree of uniformity of the probability vectors.  However, it only
represents the *average* amount of information obtained when we know
which of the singleton event has occurred.  If we consider the worst
scenario (which is required in order to show that the problem can be
solved without luck playing a role), the information obtained for the
worst case is *less* than the average (given by the entropy function).
In fact, since we are considering the worst scenario here, the average
information content (hence the entropy function) is irrelavant.  Rather,
it is the *minimum* information content that can be deduced from each
weighing which is of critical importance.  And this is equivalent to
considering the maximum of the probabilities of the outcomes, since
     I(w) = - SUM_{i=1}^n [ log_2(P_i) * X_Si(w) ]
     where  Si is the singleton event corresponding to the outcome w_i
            X_Si(w) is the indicator (characteristic) function of Si
                    and takes the value of 0 or 1
            I(w_j) is the information corresponding to w_j
            P_i = P(Si)

WS> Put the numbers in, you'll have
WS> 
WS> 	- ( 4/13 log2(4/13) + 4/13 log2(4/13) + 5/13 log2(5/13))
WS> 
WS> Sorry, I don't have a calculator here.  But I believe this number
WS> should be large enough to make your proof not working.

Yes, according to this calculation, it would mean that the problem *can*
be solved, which contradicts the quoted reference (since I have *not* used
an extra standard ball in the proof)!  Can you suggest a reason (other
than what I have explained above)??

Cheers,
Daniel (yuen@bhprtc.scpd.oz.au)