Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 8/28/84; site lll-crg.ARPA
Path: utzoo!watmath!clyde!bonnie!akgua!mcnc!philabs!cmcl2!seismo!umcp-cs!gymble!lll-crg!muffy
From: muffy@lll-crg.ARPA (Muffy Barkocy)
Newsgroups: net.puzzle
Subject: Re: Advanced Weighing problem
Message-ID: <536@lll-crg.ARPA>
Date: Sun, 21-Apr-85 17:50:26 EST
Article-I.D.: lll-crg.536
Posted: Sun Apr 21 17:50:26 1985
Date-Received: Wed, 24-Apr-85 02:36:36 EST
References: <455@alberta.UUCP>
Reply-To: muffy@lll-crg.UUCP (Muffy Barkocy)
Distribution: net
Organization: Lawrence Livermore Labs, CRG group
Lines: 36

In article <455@alberta.UUCP> makaren@alberta.UUCP (Darrell Makarenko) writes:
>
> 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.
>
>    From the original problem and numerous solutions posted
>    we know that F(3) >= 12.  i.e. we can determine a counterfeit
>    in at least twelve coins given three weighings.
>
> Derive F, either in closed form or failing that place limits
> on F  eg.  F(n) < n!,  F(n) > n**2  etc.
> You dont have to describe the n weighings necessary to find the
> coin, just the formula as to the max number of coins there could be 
> such that it is possible to find it in n weighings.
>
> Post solutions or ideas to net.puzzle.


There are 2n+1 possible solutions, either one of the n coins is light (n),
one is heavy (n) or they are all equal (1).  The tree for this problem is
ternary.  The first weighing has three possible outcomes (< = >), as does
each subsequent weighing.  Therefore, at any level of the tree L, L being
the number of weighings that has taken place, there are 3^(L - 1) possible
places for solutions.  Thus, 2n + 1 <= 3^(L - 1), for all the solutions to
be possible.  2n <= (3^(L - 1)) - 1, n <= ((3^(L - 1) - 1)/2.

                    Muffy