Re: On the complexity of determining whether n numbers are distinct

eKo1 wrote:
eKo1 wrote:
Suppose you have n coins, all of which look exactly the same. You are
given a balance scale and are asked to determine if the coins are all
distinct, i.e. they all weigh differently. What is the minimum amount
of times the balance will be used to solve the problem?

If I weigh two coins at a time, the decision tree for this problem will
have a height h = C(n, 2) so in the worse case, the balance would be
used C(n, 2) times which is proportional to n^2. This is certainly not
n lg n. Hmm....

Nevermind. Every time I weigh two coins, say a and b, either a > b, a <
b or a = b. That means each internal node in the decision tree has 3
children.

I drew a decision tree for n = 3 for this problem and a decision tree
for sorting n = 3 numbers and they look exactly the same except that
the internal nodes on the sorting decision tree only have two children
as opposed to three. I must figure out a way to show that both trees
have the same height. Perhaps a proof by induction is in order. I'll
think about this a bit and post some results tomorrow.

.

Relevant Pages

  • 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: 10 coin puzzle
    ... Given a pan balance and three ... weighings, determine whether or not they all weigh the same. ... First, note that if we are weighing two equal amounts of coins, and the ... Either they all have the same weight, ...
    (rec.puzzles)
  • Re: 10 coin puzzle
    ... Given a pan balance and three ... weighings, determine whether or not they all weigh the same. ... First, note that if we are weighing two equal amounts of coins, and the ... Either they all have the same weight, ...
    (rec.puzzles)