2

MATERIAL
We have a set of 9 coins equally sized and shaped but with a different weight for each of them.
We also have a very new three-pan balance which work in the following way:
Three slots in which you may put coins, if one of the slot is lighter than the two other it will go up, the heavier will go down and the medium-weighted will stay at a central position. This mechanism was also describe in this question

QUESTION
Can you give the minimum number of weighting you will need to order your coins by weight?

EDIT
For the moment the best answer was given by Bass in a certain number of move can we achieve to make it with one less move?

Source: Diophante.fr A726

Untitpoi
  • 2,700
  • 1
  • 14
  • 28
  • 1
    Possible duplicate of https://puzzling.stackexchange.com/questions/41222/15-balls-weighing – TrojanByAccident Feb 09 '18 at 16:15
  • Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it. If not, some responses to the answerers to help steer them in the right direction would be helpful. – Rubio Mar 03 '18 at 08:34

3 Answers3

4

Thinking while I write, so probably not optimal. However, this method orders the coins with

9 weighings.

Split the coins into three groups, and weigh each group separately, always labeling the coins 1-3, with 3 being the heaviest of the group. Then weigh the middle coins (coins labeled with number 2) of the groups, and label the groups by letters a-c, with the lightest middle coin belonging to group a. 

a3   b3   c3
v    v    v
a2 < b2 < c2
v    v    v
a1   b1   c1

Then weigh a3, b2 and c1. After these 5 weighings, we can split the coins into 2 groups using b2 as the pivot. (We know whether each coin is heavier or lighter than b2.) Also, both groups are guaranteed to have at least 3 coins.

First, let’s assume we got a 5-3 (or 3-5) split. The larger portion already has one full measurement done among the coins in it, so 3 more weighings will solve it. The smaller group is solved in 1, for a total of 9. (EDIT: actually, since a3 and c1 are both in the bigger group, and weighing 5 just compared them, we can shave off one weighing in the 5-3 case.)

The worst-case 4-4 split has a1, b1, c1 and a2 in the lighter-than-b2 group. Luckily, we already know a2 is heavier than a1, so 2 weighings are enough. By symmetry, the heavy group can also be solved in 2, for a total of 9.

Bass
  • 77,343
  • 8
  • 173
  • 360
  • This is so tantalizingly close to being solvable in eight! Out of all the possible cases, only the one with b2 being 5 takes nine weighings. I keep trying to figure out a way of doing the 3-merge-sort in 8 moves (sorting from both ends, even), but one annoying combination or another always seems to pop up and foil my plans. – Bass Feb 04 '18 at 21:31
2

Modifying a few common sorting algorithms, we have:
3-Merge

Very similar to UselessInfoMine's solution, we:
- Split the stack into 3 even piles of three coins.
- Sort each of those stacks [3]
- Compare the heaviest coins from each stack [1], and place the max out of that as the overall max.
- Repeat, comparing the heaviest remaining coin from each stack and taking the heaviest out of that as the next heaviest overall coin [6].
- This sorts it with 10 total uses of the scale.

3-Quicksort

- Pick any two coins to use as "pivots"
- Place those two coins on their own plate, and one at a time sort the rest of the coins into three piles: "less than both", "greater than both", or "in between". [7]
- Best Case: There are exactly 3 coins in two of the piles, and 1 coin in the third.
--- Those two piles can be sorted with 1 coin on each plate [2] for a total of 9 uses of the scale.
- Worst Case: All of the coins are in one of the piles. You sort this small pile recursively, but choose bad pivots again, [5] and have a pile of 5 coins to sort.
--- You choose bad pivots again and end up with a pile of 3 coins to sort [3].
----- It takes one more comparison to sort this pile [1], for a total of 16 comparisons.

I'll add more common sorting algorithms as I figure out how to modify them for the 3-scale setup.

DqwertyC
  • 8,196
  • 22
  • 50
  • In your first algorithm called 3-merge, I don't understand how you choose your 3 coins after you get the max out. Let's take an example: 9 5 4// 2 1 7 // 8 6 3. Sorting of the 3 groups ==> 4 5 9 // 1 2 7 // 3 6 8. I take the most heavy one of each group and I get to know 9 is the heaviest [4]. How do I continue? – Untitpoi Feb 02 '18 at 17:27
  • @Unitpoi Take the heaviest remaining in each group each time. That is, after finding 9 is the heaviest, the next comparison would be comparing 5, 7, and 8. – DqwertyC Feb 02 '18 at 17:34
  • Got it thanks! So you may compare the same two coins multiple times. – Untitpoi Feb 02 '18 at 17:45
1

I make it

Ten weighings.

I'm probably wrong, but hey...

Arrange the coins into a three by three grid.
Take the coins at positions 1, 2 and 3 and weigh them.
Lay them back out with the lightest at the lowest position.
Repeat with the coins at positions 4-6 and 7-9. This now has the three rows ordered by weight.
Now take the coins at positions 1, 4 and 7 and weigh them.
Lay them out with the lightest coins at the lowest position.
Repeat with the coins at positions 2, 5, and 8 and 3, 6 and 9.
Now repeat taking the coins at positions 1, 2 and three again, and weigh them, laying the lightest in the lowest position.
Repeat with the coins at positions 4-6 and 7-9.
Tenth weighing - Weigh the coins at positions 1, 3 and 7. Replace in same postions. If 3 is heavier, your coins are in weight order down the columns, left to right. If 7 is heavier, your coins are in weight order across the rows, top to bottom.

UselessInfoMine
  • 661
  • 5
  • 8
  • If we take coins weighted in that order: 9 5 4// 2 1 7 // 8 6 3. your method is not working. 3 weighting on line ==> 4 5 9 // 1 2 7 // 3 6 8. weighting (3) in colums ==> 1 2 7 // 3 5 8 // 4 6 9. And then again 3 weighting in line gives you ==> 1 2 7 // 3 5 8 // 4 6 9. The tenth weighting won't help the coins are not ordered in any way! – Untitpoi Feb 02 '18 at 16:37
  • I said I was probably wrong. :) I was on a boring phone call and ran a few random tests and they worked. – UselessInfoMine Feb 02 '18 at 16:39