Re: Weighing problem

On Nov 25, 9:52 am, Champ <iamach...@xxxxxxxxx> wrote:
You have N apparently identical coins, one of which may be a forgery.
Forged coins are either too light or too heavy. You have a balance, on
which you may place any of the coins you like and determine whether
the coins in one pan are together lighter, heavier or the same weight
as those in the other. Using the balance you wish to detect whether
there is a forgery and, if so, which coin it is and whether it is
lighter or heavier. Prove that at least log_3 (2N + 1)
{to the base 3} weighings are required.

* Show that for N = 12 three weighings suffice.

Hint for the first part: Each weighing results in three possible
outcomes, so k weighings produce 3^k outcomes. If 3^k < 2N + 1,
apply the pigeonhole principle.

There are many discussions of the N = 12 coins problem on the web,
as you will find by googling on terms: weighing 12 coins. However
you will probably enjoy trying to solve it yourself before looking
these up.

regards, chip
.

Relevant Pages

  • Re: Believe it or not...
    ... daughter, last year, learned about half dollars and dollar coins in her ... They were amazed (these are high school ... I was taught how to balance books ... going up a few cents and down a few ...
    (rec.collecting.coins)
  • Re: On the complexity of determining whether n numbers are distinct
    ... given a balance scale and are asked to determine if the coins are all ... If I weigh two coins at a time, the decision tree for this problem will ...
    (comp.theory)
  • Re: Weighing problem
    ... Forged coins are either too light or too heavy. ... Using the balance you wish to detect whether ... Each weighing results in three possible ... There are many discussions of the N = 12 coins problem on the web, ...
    (sci.math)
  • Re: On the complexity of determining whether n numbers are distinct
    ... given a balance scale and are asked to determine if the coins are all ... What is the minimum amount ... If I weigh two coins at a time, the decision tree for this problem will ...
    (comp.theory)
  • Weighing problem
    ... You have N apparently identical coins, one of which may be a forgery. ... Forged coins are either too light or too heavy. ... Using the balance you wish to detect whether ...
    (sci.math)