Re: Weighing problem

On Nov 26, 12:30 am, Champ <iamach...@xxxxxxxxx> wrote:
On Nov 25, 8:31 pm, Chip Eastham <hardm...@xxxxxxxxx> wrote:



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.

Yes, 12 coin problem is solved in many places.

With regard to:

How does 2N + 1 come into picture in the proof ? Can you please
elaborate ?

Champ wrote:

"You have N apparently identical coins, one of which may be a forgery.
Forged coins are either too light or too heavy."

2N + 1 is the number of potential outcomes which you are asked
to distinguish by weighings:

(a) one of N coins is too heavy
(b) one of N coins is too light
(c) none of N coins is a forgery

regards, chip
.

Relevant Pages

  • Re: 10 coin puzzle
    ... Given a pan balance and three weighings, determine whether or not they all weigh the same. ... Suppose there are two different weights. ... Weighing unequal sets of coins is not useful. ...
    (rec.puzzles)
  • 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: 10 coin puzzle
    ... and three weighings, determine whether or not they all weigh the same. ... Suppose there are two different weights. ... Weighing unequal sets of coins is not useful. ... equal sets of coins will balance. ...
    (rec.puzzles)
  • 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: 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)