14 replies to this topic

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

Spoiler for

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 by phil1882, 28 November 2012 - 09:31 PM.

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

Spoiler for One less

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.