4 unknown coins - another weighing puzzle

[k-man]

You have 4 coins that look identical, but you know nothing about their weights. They may all weigh the same or may have different weights or some of them may weigh the same and some be lighter or heavier - you get the idea. The difference (if any) is small relative to the weight of the coins

Goal: You need to organize the coins based on their relative weight, i.e. sort them by weight grouping identical coins together. All you have is a balance scale that tells you which side of the scale is heavier or if the sides are in balance.

Question 1: What's the minimum number of weighings required to achieve the goal?

Question 2: Provide a method that accomplishes the goal in the minimum number of weighings.

Have fun!!!

[CaptainEd]

Down to 5.

It takes no more than three to sort A, B, and C. Less if there are ties.

Assuming A LT B LT C, do a binary search:

weigh B|D and then weigh D against the coin on the appropriate side (e.g. if B LT D, then C|D

[CaptainEd]

Just a question about the conditions. "The difference is small relative to the weight of the coins". I'm guessing that means something like "the difference between the lightest and the heaviest coin is less than the weight of the lightest coin."

Is that sort of what you mean?

(What an interesting weighing puzzle!)

[curr3nt]

I believe 6.

I think AB vs CD, AC vs BD and AD vs BC would tell which is the heaviest.

>>> means A

><< means B

<>< means C

<<> means D

In the case that A is heaviest then weigh B>C, B>D and C>D for 6 weighing.

Need to figure how same weights or two coins weighing the same as the other two might change things.

[k-man]

Aye, Captain. You can interpret it that way. I put this condition there to exclude the possibility of one coin weighing as much as 2 others.

[CaptainEd]

good point, Curr3nt!

Weigh A against each of the others: A|B, A|C, A|D.

This divides them into three piles: LessThanA, EqualA, GreaterThan A.

If LTA or GTA has two members, weigh them and you're done.

If LTA or GTA has three members, then Weigh B against the other two: B|C, B|D.

This divides them into three groups: LTB, EQB, GTB.

If C and D are both in LTB or GTB, Weigh C|D.

Edited November 27, 2012 by CaptainEd

[k-man]

Very good, Captain.

This is the same solution that I've found to be the best so far. Now, I've been trying to either find a way to do it in 4 weighings or prove that it cannot be done.

There are 75 possible arrangements, and 4 weighings yield 81 outcomes, so, theoretically, you could do it in 4 weighings. The problem is that the first weighing of any coin against any other coin distributes the possible outcomes in 31:13:31 ratio making it impossible to complete the puzzle in 3 additional steps. Weighing any 2 coins against any other 2 creates different distributions based on whether there are 2 coins that together weigh the same as the other 2 or not. Worst case distribution is 35:5:35 and best case (that I found) is 29:17:29, still not allowing to solve it in 3 steps from there. I think that proves that this puzzle cannot be solved in 4 weighings, but I would love to hear what others think about that.

[CaptainEd]

K-man, you've clearly given it a lot of thought. I wonder if this number of weighings can resolve more than 4 coins.

[k-man]

Adding the fifth coin under the same conditions increases the number of possibilities dramatically, so 5 weighings will not cover 5 coins. I'll do some calculations and if I find it interesting enough, I'll post a new topic for 5 coins.

[CaptainEd]

Good point. It would be nice to have a number of coins where there's a benefit to a multi-coin weighing. My solutions for single-coin weighings are 8 weighings for 5 coins, 11 weighings for 6.

[phil1882]

hmm. i only get 47 total cases. there are 4! = 24 cases where all coins are a different weight, 12 cases where 2 coins are equal, 6 cases where 2 pairs are equal, 4 cases where 3 are equal, and 1 case where all coins are equal. am i missing something?

[phil1882]

edit nm i got it. i was only thinking of the heaviest being equal but any of the three positions can be equal.

[CaptainEd]

Aye, Captain. You can interpret it that way. I put this condition there to exclude the possibility of one coin weighing as much as 2 others.

I think I see it more clearly now--any number of coins always weighs strictly more than a smaller number of coins.

[phil1882]

i tend to agree with curr3nts assessment. no way to get a guaranteed solve in 4. best i can do with 4...

assume that the four coins have a weight of 1.1, 1.2, 1.3, or 1.4; any coin can be any of those four weights.

weigh ab against cd

---if equal either we have two pairs equal, or all four equal, or one side at the extremes with the other in the middle. weigh a against c.

------if equal, either two pairs are equal, or all four are equal. weigh a against b.

---------if less, we have a == c < b ==d. if greater; we have b == d < a == c.if equal, all four are equal.

------if a < c; then either a == d < b == c, or a < c <> d < b; or d < a <> b < c. weigh ac against db.

---------if equal; then first case; if ac is less, then second case; weigh d against c, if greater, then third case, weigh a against b.

now for the impossible case.

---if ab < cd then the lightest coin must be on the left and heaviest on the right. weigh bc against ad.

------if equal; either a== b < c== d; b < a == d < c; a < b == c < d; b < a <> d < c; a < b <> c < d. two more weighing should be enough (ac vs bd).

------if bc < ad; we have 11 total cases, with only 2 weighs. should be impossible.

Edited November 28, 2012 by phil1882

[Prime]

This is Sort problem. Computer scientists have been tackling this very puzzle for the past 60 years or so, producing a great variety of algorithms.

Down to 5.

It takes no more than three to sort A, B, and C. Less if there are ties.
Assuming A LT B LT C, do a binary search:
weigh B|D and then weigh D against the coin on the appropriate side (e.g. if B LT D, then C|D

What you have suggested here seems like “Tree Sort” with self-balancing binary tree. The "worst case" order for such algorithm is O(n log n). That's as fast as it gets. Or, at least, that’s the present day theory.