Jump to content
BrainDen.com - Brain Teasers
  • 0

4 unknown coins - another weighing puzzle


k-man
 Share

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

Link to comment
Share on other sites

14 answers to this question

Recommended Posts

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

Link to comment
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
Link to comment
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.

Link to comment
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
Link to comment
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.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...