Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/5/84; site alberta.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!ihnp4!alberta!makaren
From: makaren@alberta.UUCP (Darrell Makarenko)
Newsgroups: net.puzzle
Subject: Advanced Weighing problem
Message-ID: <455@alberta.UUCP>
Date: Thu, 18-Apr-85 13:13:04 EST
Article-I.D.: alberta.455
Posted: Thu Apr 18 13:13:04 1985
Date-Received: Fri, 19-Apr-85 01:29:50 EST
Distribution: net
Organization: U. of Alberta, Edmonton, AB
Lines: 24


 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.