Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site harvard.ARPA
Path: utzoo!linus!philabs!cmcl2!seismo!harvard!heddaya
From: heddaya@harvard.ARPA ( Solom)
Newsgroups: net.puzzle
Subject: Re: Advanced Weighing problem
Message-ID: <55@harvard.ARPA>
Date: Fri, 19-Apr-85 13:00:27 EST
Article-I.D.: harvard.55
Posted: Fri Apr 19 13:00:27 1985
Date-Received: Sun, 21-Apr-85 03:14:29 EST
References: <455@alberta.UUCP>
Distribution: net
Organization: Aiken Computation Laboratory, Harvard
Lines: 57

>  Ok we have seen the well known weighing problem of the
>  twelve coins, one counterfeit (lighter or heavier) , three
>  weighings find the phoney. 
> 
>  Lets generalize the problem as follows.
>   Given that there is one counterfeit in a pile of coins
>   and that it is lighter or heavier than the others (you dont
>   know which).  Derive the formula F(n) that will tell you
>   that if you are allowed n weighings on a balance scale what
>   is the maximum number of coins there could be where you could
>   find the counterfeit among them and whether it is heavier or lighter.


Here is a derivation of F(n), the maximum number of items for which the
problem can be solved in n weighs.  I give only a proof sketch, using the 12
item problem as an example, and I also give a hint as to how a complete
formal proof can be constructed.

I'll show that:
			F(n) <= 0.5 * (3**n)

First, the problem: the distinguished item (x) can be any one of the 12
items, and it can be either heavier or lighter than the 11 identical items.
Therefore, we have 24 distinct states from which we have to select one.

Second, the means: we have a balance that can tell us one of three things
(<, =, >) every time we weigh two groups of items against each other.  So,
it seems that the best we can do is eliminate 2/3 of the possible states by
any one weigh (the weigh tells which third is right).  It is not possible to
eliminate more, since you don't know before hand which of the three outcomes
is going to happen.  In our case of 24 states, the first weigh can eliminate
at most 16 states (leaving 8), the second at most 6 (leaving 2), the third
at most 1 (giving us the solution).  So, we cannot do better than 3 weighs.

In general, for k items (2*k states), we cannot do it in less than log to
the base 3 (2*k); taking the lowest integer higher than that number, of
course.  To formally prove this lower bound, on can use a decision tree
argument, where every decision can have 3 outcomes, as someone pointed out
before.  

Let the number of weighs be n, then, what we showed was that:

		n >= log3 (2*k)
so,		k <= 0.5 * (3**n)

The constructive result of this analysis is that each weigh must be designed
in such a way that each of the 3 possible outcomes implies at least one
third of the possible states of x, the distinguished item.  I have a sort of
derivation of a solution for the 12 item problem using this condition (I can
mail it to interested people).

It is conceivable that, as n increases and/or k approaches its upper bound,
this condition becomes harder and harder to achieve.  It may even become
impossible, in which case our lower bound on the number of weighs becomes
unachievable.

						Abdelsalam Heddaya