Brain Teaser: Can you find the heaviest and the lightest in 4 weighings?

Stop it!;)

Number the coins 1,2,3,4 (let’s say coin 1 is lightest and coin 4 is heaviest but you obviously don’t know that information yet).

Weigh coin 1 against coin 4 and record which is heaviest.

Weight coin 4 (the heavier coin) against coin 2 and record which is heaviest.

Weigh coin 2 (one of the lighter coins) against coin 3 (the remaining unknown coin) and record which is heaviest.

Weigh coins 1 against coin 3 (the two lightest coins) and record which side is heaviest.

Coin 4 is heavier than coin 2.
Coin 4 is heavier than coin 1.
Coin 2 is heavier than coin 3.
Coin 3 is heavier than coin 1.

Since coin 4 was heavier than coins 2 and 1, coin 2 was heavier than coin 3, coin 4 is obviously the heaviest.

Since coin 1 was lighter than coins 3 and 4 and coin 3 is lighter than coin 2, coin 1 is obviously the lightest.

What do you think?

Ok for the bonus question and maybe the super bonus question, here’s my thought:

N = number of coins = 10

Here is the randomly chosen order from heaviest to lightest: 4, 7, 3, 2, 5, 1, 6, 9, 8, 10

1. N vs N-1 ( 10 vs 9)
2. heaviest of step 1 vs N-2 (9 vs 8)
3. heaviest of step 2 vs. N-3 (9 vs 7)
4. heaviest of step 3 vs N-4 (7 vs 6)
5. heaviest of step 4 vs N-5 (6 vs 5) ** ok now we are at step N/2 so here we pick a coin that has never been the heaviest and use it for step 6 (here we’ll choose coin N.
6. N vs N-6 (10 vs 4)
7. lightest of step 6 vs. N-7 (10 vs 3)
8. lightest of step 7 vs N-8 (10 vs 2)
9. lightest of step 8 vs N-9 (10 vs 1)

** Now we know something about each of the coins. So, we arrange the coins into two columns, those which have never been outweighed and those that have never been underweighed.

In our case those that have never been outweighed are 5, 4, 3, 2 and 1
and those that have never been underweighed is 10

10 is for sure the lightest

Now evaluate those that have never been outweighed and each time eliminate the number that is outweighed as follows:

10. 5 vs 4
11. heaviest of step 10 (4 vs 3)
12. heaviest of step 11 (4 vs 2)
13. heaviest of step 12 (4 vs 1)

4 is then the heaviest.

So, I’m not sure how to write this in a mathematical formula but for N coins, start with coin N and do N/2 trials using the heaviest coin from the previous trial vs. the next coin in succession. Then for the [(N/2) + 1]th trial pick a coin that has never been the heaviest and do [(N/2) – 1] trials using the lightest coin from the previous trial vs. the next coin in succession. Then arrange the coins into the two columns and systematically remove possibilities as shown above.

So, is this correct? And, how would you write that mathematically?

Crap, I just noticed that I made an error. I would also have to compare 10 vs 8 to see which was lightest, so that would take 14 trials. Well, I give up. Hope someone figures this out.

Some good thinking there, but you are making it too complicated. Concentrate on the 4 coin case

original Q:
weigh A against B and C against D—that’s two weighings.
weigh the heavier of AB against the heavier of CD—that gives you the original heaviest, in three weighings.
Now weigh the lighter of AB against the lighter of CD—that fourth weighing gives you the original lightest.

suppose you had 8 coins; then in four weighings you could get a group of four that the heaviest must be among and a different group of four that the lightest must be among; then you could get the heaviest out of the former group in three more weighings, and the lightest out of the latter group in theree more weighings; so 10 weighings for 8 coins.

So, if i had started with ten coins, then i would need three more weighings; first i would set aside two coins and find the heaviest and lightest of the group of eight in ten weighings, as previously described; then i would use one additional weighing to find the heavier and lighter of the two previously unweighed coins, yet one more weighing to match the heavier of those two against the heaviest from the group of eight, and a final additional weighing to match the lighter of the two against the lightest of the group of 8; so 13 weighings for ten coins.

more later.

That is the correct answer, but there is a simpler way of describing the case of 10 coins. Just start out by weighing five pairs of coins and procede from there.

“go from there” is not an effective algorithm in this decade, because it’s difficult to program at the current state of development of computers.

also, that fifth coin appears to me to cause two extra weighings, and that’s hard to intuit.

my general answer for the number of weighings for a group containing a number of coins that is an exact power “n” of two is:
3*(2**(n-1))-2
This number is an upper bound for any group consisting of fewer than 2**n coins.

Here is “pseudocode” for the full algorithm:
======================================
For a group consisting of an even number of coins that is not an exact power of 2, break that group down into a collection of subgroups, with each sub-group consisting of a number of coins that is an exact power of 2, resolve each sub-group separately, and start again with the collection of coins that were the heaviest in their respective subgroups, but looking only for the heaviest, and independently with the collection of coins that were the lightest in their respective subgroups, but looking only for the lightest. More stages of this process might be needed.

If at any stage there is an odd number of coins in a sub-group, set aside one coin and, when the other coins in that sub-group have been resolved, weigh the odd coin against the heaviest and lightest found so far in that subgroup and replace, if necessary, the former heaviest or lightest with the odd coin.
====================================

Bad enough that i’ve done this much of someone’s homework problem; i’m not going to take the time to answer the Super Bonus portion any more fully.

“The answer is left as an exercise for the reader.”<grin>

This is not a homework problem. I thought it would make a fun challenge.
With 10 coins, divide them into 10 pairs and weigh each pair. Then compare the 5 heavier coins to find the heaviest. This takes 4 additional weighings. It takes another 4 weighings to find the lightest coin. 5+4+4=13 weighings.

In general, for n coins where n is even, the coins can be divided into n/2 pairs and the n/2 weighings give n/2 heavier coins and n/2 lighter coins. These two groups can be weighed against each other to give n/2 -1 weighings t find the heaviest coin and n/2 weighings to find the lightest for a total of 3(n/2)-2 weighings.

This is the best that can be done. Label each of the coins to weighed with the letters H and L, indicating that at the beginning each coin may be the heaviest or the lightest. The weighings can be seen as process of getting rid of the labels until there is one coin with just an H and another with just an L. When two coins with HL labels are weighed against one another, the heavier coin loses its L label since it can no longer be the lightest coin and similarly the other coin loses its H label. Any weighing eliminates at most two labels and once a coin loses one of its labels, any additional weighing does not guarantee that it will lose its remaining label, so the only way that two labels can be eliminated is if two unweighed coins are weighed. The coins can be grouped into n/2 weighings and in each case 2 labels are eliminated, leaving n/2 coins with an H and n/2 coins with an L. It is easy to see that the best that can be done is to weigh the coins with H labels against one another and the coins with L labels against one another. In each case a weighing eliminates the H or L label from one coin. It takes n/2 – 1 weigings to end up with a single H and n/2–1 to end up with a single L, for a total of n/2 + (n2–1) + (n/2–1) = 3n/2 – 2.