14 replies to this topic

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

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]

Spoiler for If they are all different and no two weigh the same as the other two then...

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!

Spoiler for Even with ties, that's enoughj

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, 27 November 2012 - 11:26 PM.

[CaptainEd]

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

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

Spoiler for Thoughts...

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.