• 0
Sign in to follow this  
Followers 0

4 unknown coins - another weighing puzzle

Question

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

14 answers to this question

  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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?

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0

  • Recently Browsing   0 members

    No registered users viewing this page.