BrainDen.com - Brain Teasers
• 0

# 4 unknown coins - another weighing puzzle

## Question

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

## Recommended Posts

• 0

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

##### Share on other sites

• 0

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!)

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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 by CaptainEd
##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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.

##### Share on other sites

• 0

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?

##### Share on other sites

• 0

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.
##### Share on other sites

• 0

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 by phil1882
##### Share on other sites

• 0

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.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.