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

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....

.

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 ... weighings are required. ... Forged coins are either too light or too heavy." ...
    (sci.math)
  • 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 ...
    (sci.math)
  • Re: What does 1+1=2 really mean?
    ... > Is the equation 1+1=2 a theoretical equation in which the equal sign is ... > different items to be identical at all times in order for the balance ... > balance scale to be level? ... 1a never equals 1b ...
    (sci.math)