⌈3n/2⌉−2 weighings are required to find the lightest and the heaviest coin among n coins. Prove/disprove this

Question

1. We are given n coins, all of which have a different weight. Prove/disprove that ⌈3n/2⌉−2 weighings are required to find the heaviest and the lightest coins among them using a 2 pan balance scale. You can assume that n= 68 or any other number if you so need.

2. Do the number of weighings required, increase or decrease, if it is given that some of these coins have the same weight?

Answer 1

1. The statement is

correct.

Proof:

We will for simplicity assume n is even.
Sufficiency:
Form two groups H and L by randomly creating n/2 disjoint pairs and comparing each always adding the heavier coin to group H and the lighter one to group L. Afterwards find the heaviest of group H (n/2-1 comparisons) and the lightest of group L (n/2-1 comparisons)
Taken together this sums to n/2 + 2x(n/2-1) = 3n/2 - 2.
Necessity: We can model the cumulative gain of information in terms of a refining partial ordering. (The partial ordering can be refined to a total ordering in many different ways and these are precisely the weight rankings that are compatible with the weighings so far.) We are finished as soon as the numbers of minima and maxima in the partial ordering sum to 2 (i.e. 1 max, 1 min). In the beginning we know nothing hence every coin is maximal and minimal and the sum is 2n. Each weighing reduces this number by 0,1 or 2. What is the worst case under the best strategy?
It is easy to verify that the worst case is 0 or 1, no matter what we compare with one exception: If we compare two isolated nodes, i.e. coins that have not been compared to anything yet, the reduction is 2, one minimum and one maximum. This can be done at most n/2 times.
Taken together we see that we cannot reduce the number of extrema from 2n to 2 in fewer than n/2 steps of 2 and n-2 steps of 1. Summing we recover n/2+n-2 = 3n/2 - 2.

2. Having some equal items does

no harm, the strategy described in 1. works for ">=" just as well as for ">".
If we know in advance the number and rank of equal coins faster strategies may be possible.

Answer 2

This statement as written is:

false

Proof:

All we need to do to disprove this, all we need to do is offer a counter example. So, let's do that.

Assume n=0

This gives us:

3(0)/2 - 2 = 0/2 - 2 = 0 - 2 = -2

But that's impossible!

We can't weigh a group of coins a negative number of times. We can weigh them, or we can not weigh them, but we can't weigh them a negative number of times!

So the equation as written cannot work.

Now I suppose we could make an exception. After all:

Getting 0 coins, while arguably a valid value for n since we can use "any other number if you so need", isn't exactly the same as getting some coins. Rather, getting 0 coins is the same as not getting any coins at all.

Thus, we could make an exception for this specific case.

So let's do another one.

Suppose:

n=1

This gives us:

3(1)/2 - 2 = 3/2 - 2 = 1.5 - 2 = -0.5

But this is also impossible!

As mentioned above, we can't weigh things a negative number of times. So this doesn't work either

As before, we could make an exception here because:

One coins could arguably not be a "group" of coins. Perhaps a "group" here means more than one.

So I suppose we could make another exception for this case as well.

So let's do another.

Suppose:

n=3

This gives us:

3(3)/2 - 2 = 9/2 -2 = 4.5 - 2 = 2.5

But this is also impossible!

This time, we have a slightly different reason. As before, we can either weigh a group of coins, or we can not weigh them. But we cannot weigh a group of coins 0.5 times! That just doesn't make sense either.

In fact, by this logic, it is easy to see that:

Any odd number of coins doesn't work with this formula, as we will always end up with a "half" weigh.

---

So, TL;DR

1.--as it is currently worded--is:

false, since we can find some examples where the result of our formula just doesn't make sense.

And for 2:

This doesn't change anything as our logic isn't dependent on weight at all, really.

And some final notes:

The OP could reasonably restrict these cases, such as say that n > 2, or all odd cases are excluded. Alternatively, the OP could say how to handle "half" weightings. But I'm just going to leave this here for now for a couple of reasons:

First, the OP has placed no such restriction at the time of this writing.

Second, Paul Panzer's answer already answers the rest of the cases much better than I could.