15 Balls Sorting

Question

This is a variant of 15 Balls Weighing.

You have 15 balls of 15 different weights, but the weights are so similar you can't tell them apart by feel. The balls are also identical by any other sense you might try, and cannot be marked, marred, or otherwise altered.

Your job is to sort the balls by weight.

The only tool you have is a black-box scale. You enter two or three balls, press a button, and after a bit of whirring noises, the balls roll out in order by weight, heaviest first, lightest last.

How many weighings are required to sort the balls by weight?

The difference between this puzzle and the other is that you lose track of which ball is which when you perform the weighing. Thus, if you know $a>b>c$ and $d>e>f$, then weigh $a$ vs $d$, the scale will sort them, but you won't know whether the heaviest was $a$ or whether it was $d$.

Hint

There is an algorithm that can solve this in 31 weighings. Not sure if it is optimal.

Answer 1

And now my computer generated and checked solution:

It needs 29 weightings

Put the weights in a row and number the places from 1 to 15. Then do the following:

Put the weights at 1, 6 and 11 into the scale. Put the lightest weight at 1 the heaviest at 11 and the other at 6.
Put the weights at 2, 7 and 12 into the scale. Put the lightest weight at 2 the heaviest at 12 and the other at 7.
Put the weights at 3, 8 and 13 into the scale. Put the lightest weight at 3 the heaviest at 13 and the other at 8.
Put the weights at 4, 9 and 14 into the scale. Put the lightest weight at 4 the heaviest at 14 and the other at 9.
Put the weights at 5, 10 and 15 into the scale. Put the lightest weight at 5 the heaviest at 15 and the other at 10.
Put the weights at 1, 2 and 4 into the scale. Put the lightest weight at 1 the heaviest at 4 and the other at 2.
Put the weights at 1, 3 and 5 into the scale. Put the lightest weight at 1 the heaviest at 5 and the other at 3.
Put the weights at 12, 14 and 15 into the scale. Put the lightest weight at 12 the heaviest at 15 and the other at 14.
Put the weights at 11, 13 and 15 into the scale. Put the lightest weight at 11 the heaviest at 15 and the other at 13.
Put the weights at 8, 9 and 10 into the scale. Put the lightest weight at 8 the heaviest at 10 and the other at 9.
Put the weights at 2, 6 and 7 into the scale. Put the lightest weight at 2 the heaviest at 7 and the other at 6.
Put the weights at 2, 3 and 8 into the scale. Put the lightest weight at 2 the heaviest at 8 and the other at 3.
Put the weights at 12, 13 and 14 into the scale. Put the lightest weight at 12 the heaviest at 14 and the other at 13.
Put the weights at 7, 10 and 14 into the scale. Put the lightest weight at 7 the heaviest at 14 and the other at 10.
Put the weights at 3, 4 and 5 into the scale. Put the lightest weight at 3 the heaviest at 5 and the other at 4.
Put the weights at 6, 9 and 11 into the scale. Put the lightest weight at 6 the heaviest at 11 and the other at 9.
Put the weights at 3, 6 and 12 into the scale. Put the lightest weight at 3 the heaviest at 12 and the other at 6.
Put the weights at 8, 10 and 13 into the scale. Put the lightest weight at 8 the heaviest at 13 and the other at 10.
Put the weights at 5, 11 and 13 into the scale. Put the lightest weight at 5 the heaviest at 13 and the other at 11.
Put the weights at 4, 6 and 7 into the scale. Put the lightest weight at 4 the heaviest at 7 and the other at 6.
Put the weights at 4, 8 and 9 into the scale. Put the lightest weight at 4 the heaviest at 9 and the other at 8.
Put the weights at 10, 11 and 12 into the scale. Put the lightest weight at 10 the heaviest at 12 and the other at 11.
Put the weights at 7, 9 and 12 into the scale. Put the lightest weight at 7 the heaviest at 12 and the other at 9.
Put the weights at 5, 6 and 8 into the scale. Put the lightest weight at 5 the heaviest at 8 and the other at 6.
Put the weights at 8, 9 and 11 into the scale. Put the lightest weight at 8 the heaviest at 11 and the other at 9.
Put the weights at 5, 6 and 10 into the scale. Put the lightest weight at 5 the heaviest at 10 and the other at 6.
Put the weights at 7, 9 and 10 into the scale. Put the lightest weight at 7 the heaviest at 10 and the other at 9.
Put the weights at 6, 7 and 8 into the scale. Put the lightest weight at 6 the heaviest at 8 and the other at 7.
Put the weights at 7, 8 and 9 into the scale. Put the lightest weight at 7 the heaviest at 9 and the other at 8.

I generated these command by an similar algorithm as Murch. But with the difference if I compare three weights at $\left(\begin{array}{c}x_1\\y_1\end{array}\right)$, $\left(\begin{array}{c}x_2\\y_2\end{array}\right)$, $\left(\begin{array}{c}x_3\\y_3\end{array}\right)$ then the resulting weights have an weight of $\left(\begin{array}{c}\max(0, x_{min})\\\max(2, y_{min})\end{array}\right)$ and $\left(\begin{array}{c}\max(1, x_{min})\\\max(1, y_{min})\end{array}\right)$ and $\left(\begin{array}{c}\max(2, x_{min})\\\max(0, y_{min})\end{array}\right)$.
In that formula $x_{min} = \min(x_1, x_2, x_3)$ and $y_{min} = \min(y_1, y_2, y_3)$

I checked my solution the same way as Gareth McCaughan: I wrote a program that uses this sorting algorithm, and sorted all possible 0-1 inputs and used the Zero-one_principle.

Explanation

Here is an algorithm how to reach this count:

Make 9 heaps with the names $a_{00}, a_{01}, a_{02}, a_{10}, a_{11}, a_{12}, a_{20}, a_{21}, a_{22}$.
Rule 1: All weights in heap $a_{ij}$ have at least $i$ weights smaller and $j$ weights bigger then themself.

At the start all 15 weights are in $a_{00}$.

The algorithm is the following:
- If you can find the lightest weight faster then the heaviest weight, then find and remove the lightest weight.
- If you can find the heaviest weight faster then the lightest weight, then find and remove the heaviest weight.
- If you can find the lightest and the heaviest with the same amount of weightings then
-- If there is an odd amount of canidates for the lightest weight then find and remove the lightest weight
-- else find and remove the heaviest weight.

Repeat until there is no weight remaining.

How fast can we find the lightest/heaviest weight

We need $\lfloor \frac{1}{2}(a_{00}+a_{01}+a_{02})\rfloor$ weightings to find the lightest weight and $\lfloor \frac{1}{2}(a_{00}+a_{10}+a_{20})\rfloor$ weightings to find the heaviest weight

How to find and remove the lightest weight

If there is an even number of weights in $a_{00}, a_{01}, a_{02}$ then remove one weight from $a_{10}$ and put it on $a_{00}$.

If there is more then one weight then take the 3 weights from the heap with the smallest possible index and put them into the scale.
(If there are 2 weights in $a_{00}$ and three in $a_{01}$ you take two from $a_{00}$ and one from $a_{01}$)
If the smallest index of the weights was $a_{00}$ then put the weights from the scale on $a_{02}$, $a_{11}$ and $a_{20}$.
If the smallest index of the weights was $a_{01}$ then put the weights from the scale on $a_{02}$, $a_{11}$ and $a_{21}$.
If the smallest index of the weights was $a_{02}$ then put the weights from the scale on $a_{02}$, $a_{12}$ and $a_{22}$.
(You can ponder why Rule 1 is still in effect).
This weighting and redistributing is repeated until there is only one weight in $a_{00}$, $a_{01}$ and $a_{02}$ together.

Remove the single weight from $a_{00}$, $a_{01}$ or $a_{02}$ and shift all weights one space.
That way the weights that were on $a_{1j}$ are now on $a_{0j}$ and the weights on $a_{2j}$ becomes $a_{1j}$ and $a_{2j}$ becomes empty.

How to find and remove the heaviest weight

Same way as the lightest weight, but work on $a_{00}$, $a_{10}$ and $a_{20}$ instead of $a_{00}$, $a_{01}$ and $a_{02}$

Answer 2

I can do better than Chelsea's and Penguino's 49 operations, as follows. (The following is pretty painful to read; sorry. For this reason it probably won't be much of a spoiler to anyone not going out of their way to be spoiled, so I haven't spoilerified it apart from the final total.)

Step 1: Divide the 15 balls into five groups of three. Put each group into the black box separately; we now have five sorted groups of three, and have done five sortings.

Step 2a: Take two of these triples. Put their lightest balls into the box (which identifies the lightest of the 6). Put their heaviest balls into the box (which identifies the heaviest; and the other one is at any rate not the lightest of the remaining balls). Put the three possibly-lightest balls into the the box (which identifies the lightest of them all) and then the remaining three (which gives us the others in order). We now have a sorted 6-tuple of balls, having done another four sortings.

Step 2b: Same as 2a, with another pair of triples. Now we have two 6-tuples and a 3-tuple, and we have done 5+4+4=13 sortings.

Step 3: Take a 6-tuple and the 3-tuple. Put their lightest balls in the box, yielding the overall lightest and one other that was lightest of one of the tuples (and leaving a 5-tuple and a 2-tuple, both of known ordering). Similarly with the heaviest. Now from those nine balls we have: the lightest and heaviest; one "lightish" and one "heavyish" ("lightish" means: either this one is next-lightest, or the lightest of one our of remaining chains is, and in any case this isn't next-heaviest; similarly for "heavyish"); an ordered 4-tuple; and a single ball that was originally from the middle of the 3-tuple.

Next merge the single ball into the 4-tuple (two obvious operations) yielding an ordered 5-tuple. (In addition to that we have a "lightish" and a "heavyish" ball.)

Now weigh lightish + lightest two in tuple, identifying the next-lightest ball and giving us another ordered pair; similarly for the heavy end. So now we have two ordered pairs and a ball about which we know nothing. Weigh the three of these that could be lightest, giving an ordered pair and two left over; weigh the three of these that could be heaviest, giving an ordered pair and one left over; weigh the remaining three.

[EDITING NOTE: An earlier version of this answer made some wrong assumptions around here. I have fixed them, and avoided needing extra weighings by turning some 2-comparisons into 3-comparisons.]

After this step, which took another 9 operations, we have an ordered 9-tuple -- and of course the other ordered 6-tuple left over from before. Total so far: 13+9=22 operations.

Step 4: Now we need to merge a 9-tuple and a 6-tuple. We can begin this as follows.

First, compare the lightest of each tuple, and also the heaviest. We now have: overall lightest, overall heaviest; "lightish" and "heavyish" (same meaning as before); a 7-tuple and a 4-tuple.

Now compare "lightish" plus the lightest of each remaining tuple, and similar for heaviest. We now have: overall two lightest and two heaviest; two (ordered) "lightish"; two (ordered) "heavyish"; a 5-tuple and a 2-tuple.

Now take the two "lightish" and the lightest ends of the two tuples; we can order all these in two operations; the lightest of the resulting balls is the 3rd-lightest overall. Similarly at the heavy end. The 2-tuple is now gone; we have a "lightish" 3-tuple, a "heavyish" 3-tuple, and a 3-tuple in the middle. (And the 3 lightest and 3 heaviest balls overall, correctly ordered.) "Lightish" merely means that the lightest ball is either its lightest or the lightest of the middle tuple, and similarly for "heavyish".

That's another 8 operations, for a total of 30 so far.

Step 5: We have our three triples still to deal with. I think at this point the "lightish" and "heavyish" descriptions may be of historical interest only; it is possible e.g. for the heaviest remaining ball to be the heaviest of the "lightish" triple. So let's treat these as three triples known only to be individually ordered correctly.

[EDITING NOTE: An earlier version of this answer assumed more about these triples, used one less operation overall, and was I think wrong as a result.]

So, compare the lightest balls of these three, and the heaviest balls; this gives us the 4th-lightest and 4th-heaviest balls overall and leaves us with two ordered pairs and three leftover balls that could be in any order. Sort those three, so now we have two pairs and a triple.

So now we have two pairs and a triple, all known to be ordered.

Weigh the lightest of them (giving us the 5th-lightest ball and two left over) and the heaviest of them (giving us the 5th-heaviest ball and two left over). We now have two ordered pairs and a single ball. Compare the three possibly-lightest balls (we now have an ordered triple and two left over, and have found the 6th-lightest ball). Compare the three possibly-heaviest balls (we now have two ordered pairs, and have found the 6th-heaviest ball).

Finally, we have three balls left, which we can sort out with one more operation.

This step has taken 8 more operations.

So we seem to be done after a total of

38 operations.

I have checked that this works in every case by the following means. This is essentially a "sorting network" that uses 3-way comparisons. There is a theorem about such networks that says: if you have one that sorts correctly whenever all the inputs are either 0 or 1, then it sorts correctly for all possible inputs. And I have written a stupid simple-minded computer program that checks this property for the algorithm above; it checks out.

Answer 3

An alternate way to look at it (for an odd number of balls) is to do a 3 way weighting, then 'discard' the middle weight and repeat the weighing with the lightest, the heaviest, and each remaining unweighted ball in turn. At the end of the process you will have identified the lightest and heaviest balls. Put them to one side and repeat the process again with the discards (to identify the next lightest and next heaviest balls).

Algorithmically, to test 2N+1 balls you would have:

 while N > 0
   weigh 1,2,3
   discard M
   for i = 4 to 2*N+1
     weigh L,i,H
     discard M
   N = N-1

each while loop requires 2*N-1 weightings, so total number is

 Sum(i=1,N) of {2*N-1) = N^2

so 15 = 2*7+1 balls requires 7^2 = 49 weightings, and (for example) 2001 balls would require 1000000 weightings.

Answer 4

I believe this is a procedure that will identify the order with:

37 tests

I suspect this is similar to Gareth McCaughan's answer, but I didn't take the time to read it all that carefully as it seemed very involved.

Given a subset $n$ of balls, one of which may be the lightest, identify the lightest ball as follows. First, test three balls. Then, repeat testing the lightest ball of each test against two new balls for the next test.

This identifies the lightest ball in $⌈\frac{(n+1)}{2}⌉$ tests.

However, we have additional information. For each 3-way test that was performed, we know that one of the failed balls is lighter and one is heavier. In particular, the ball that was heaviest in each 3-way test cannot be the second lightest ball of the original $n$.

So, I propose the following procedure. At each stage, some sequence of balls have been identified as the lightest balls in a known order. The remaining $n$ balls are divided into three categories: "lighter", "heavier", and "unknown". Initially, all 15 balls are in the "unknown" category. We will keep the invariant that at each stage, the next lightest ball is not in the "heavier" category.

We will use the procedure described above to determine the lightest ball out of the combination of the "lighter" and "unknown" categories. If the number of balls is even, we will throw in an extra ball from the "heavier" category in as well to make sure all the tests are 3-way.

This will positively identify the next lightest ball. Of the remaining balls, those that were untested (previously "heavier") become "unknown". Of those that were tested, the heavier of each pair become the "heavier" category and the lighter become the "lighter" category.

Once there are only 3 balls that haven't been positively identified, a single additional test can put all 3 of these remaining balls into order.

Starting with 15 unknown balls:

1. 15 unknown, 0 lighter, 0 heavier: 7 tests
2. 0 unknown, 7 lighter, 7 heavier: 3 tests
3. 7 unknown, 3 lighter, 3 heavier: 5 tests
4. 2 unknown, 5 lighter, 5 heavier: 3 tests
5. 5 unknown, 3 lighter, 3 heavier: 4 tests
6. 2 unknown, 4 lighter, 4 heavier: 3 tests
7. 3 unknown, 3 lighter, 3 heavier: 3 tests
8. 2 unknown, 3 lighter, 3 heavier: 2 tests
9. 3 unknown, 2 lighter, 2 heavier: 2 tests
10. 2 unknown, 2 lighter, 2 heavier: 2 tests
11. 1 unknown, 2 lighter, 2 heavier: 1 test
12. 2 unknown, 1 lighter, 1 heavier: 1 test
13. 3 remaining: 1 test

Answer 5

I think (but haven't checked carefully, unlike my earlier answer) I can do it in

33 operations.

I will sketch the procedure using a notation that I hope will become comprehensible after staring at it for a minute. When I write something like 3+2 -> 2+1+1 I mean "if you have three balls in known order and two balls in known order (3+2), then a single operation (->) will let you turn this into two balls in known order, one mystery ball, another mystery ball (2+1+1), while perhaps identifying some of the very lightest or heaviest of the original set". In this case we identify one of the lightest or heaviest, as you can see from the fact that (3+2)-(2+1+1)=1.

(How do we do this? We can e.g. weigh the lightest two of the 3 and the lighter of the 2, which identifies the lightest of all the balls and leaves us with two in known order (from the weighing) and one left over from each of our two groups: 2+1+1. It would actually be better to weigh the lightest of the 3 and both of the 2, in which case we reduce to 2+2 instead.)

In some cases I will want to indicate that we can do a particular operation in a known number of moves bigger than one: e.g., 2+2 -2-> 4 means that if we have two ordered pairs it takes two operations to get them all in order. (Left as an easy exercise for the reader.)

There isn't really any distinction between e.g. 2+2 -2-> 4 and 2+2 -2-> 3 since in the latter case it is understood that we have also identified a single overall-lightest or overall-heaviest ball. I will sometimes write things like 2+2 -2-> done where that seems clearer than putting a particular number on the right.

Sometimes it's clearer to write things in multiple steps: 3+2 -> 2+1+1 -2-> done, which is a bit more informative than just 3+2 -3-> done.

OK. So now here are some transformations we can do. Each one should be easy to justify either from scratch or by using earlier ones in the list. I haven't tried to prune everything I haven't used because some of these may prove useful to others, or to me later.

(Often an unexplained -> means "pick the obvious 3 'light' balls and weigh them" and an unexplained -2-> means "pick the obvious 3 'light' balls and the disjoint obvious 3 'heavy' balls and weigh both".)

2+2 -2-> done 3+1 -2-> done 2+1+1 -2-> done

3+2 -3-> done (via 2+2) 4+1 -3-> done (via 2+2) 2+2+1 -3-> done (via 2+1+1)

3+3 -> 2+2+1 -3-> done 2+2+2 -2-> 2+2 -2-> done 4+2 -> 3+2 -3-> done

3+2+2 -2-> 2+2+1 -3-> done

3+3+2 -2-> 2+2+1+1 -> 3+2+1 -> 2+2+1 -3-> done

3+3+3 -2-> 2+2+1+1+1 -> 3+2+2 -5-> done

3+3+3+3+3 -8-> 9+3+3 -2-> 7+2+2+1+1 -2-> 7+3+3 -2-> 5+2+2+1+1 -2-> 5+3+3 -2-> 3+2+2+1+1 -2-> 3+3+3 -8-> done

and the last of these, along with five lots of 1+1+1 -> 3, yields the claimed solution.

Answer 6

By Induction:

49 Sorts

What you need to do is figure out how many trials it takes to sort the first two balls with certainty, and then you can essentially remove them from the set.

1 Ball is automatically sorted.

To sort two balls, you just put them both in the machine.

To sort three balls, you just put all three in the machine.

To sort four balls, you need two sorts to get the first two sorted with certainty. (I am selecting "randomly" here; the point is that you order the first three, and then since we're just trying to find the lightest two balls, we continue taking the lightest two balls and sorting them against the next "random" ball from the set)

First select: a c d

Second Select: a b c

At this point, we don't know if d or c is heavier, but we now have two unsorted balls left. We know sorting two balls takes 1 use of the machine, so that's 2 Initial sorts + 1 Sort for Two Balls = 3 Sorts

To sort five balls, you need to get the first two sorted with certainty:

First select: b d e Second Select: a b d Third Select: a b c

So it took 3 sorts to get the first two balls sorted. We now have c, d, and e unsorted, and we know it takes 1 sort to get three balls sorted, so it will take Four Sorts total.

So after the first three, sorting the first two balls with certainty will always take n-2 moves, leaving you with n-2 balls to sort.

So our growth chart is as follows:

1 Ball: 0 Sorts 0 Balls Left Additional Sorts: 0 0 Total Sorts
2 Ball: 1 Sorts 0 Balls Left Additional Sorts: 0 1 Total Sorts
3 Ball: 1 Sorts 0 Balls Left Additional Sorts: 0 1 Total Sorts
4 Ball: 2 Sorts 2 Balls Left Additional Sorts: 1 3 Total Sorts
5 Ball: 3 Sorts 3 Balls Left Additional Sorts: 1 4 Total Sorts
6 Ball: 4 Sorts 4 Balls Left Additional Sorts: 3 7 Total Sorts
7 Ball: 5 Sorts 5 Balls Left Additional Sorts: 4 9 Total Sorts
8 Ball: 6 Sorts 6 Balls Left Additional Sorts: 7 13 Total Sorts
9 Ball: 7 Sorts 7 Balls Left Additional Sorts: 9 16 Total Sorts
10 Ball: 8 Sorts 8 Balls Left Additional Sorts: 13 21 Total Sorts
11 Ball: 9 Sorts 9 Balls Left Additional Sorts: 16 25 Total Sorts
12 Ball: 10 Sorts 10 Balls Left Additional Sorts: 21 31 Total Sorts
13 Ball: 11 Sorts 11 Balls Left Additional Sorts: 25 36 Total Sorts
14 Ball: 12 Sorts 12 Balls Left Additional Sorts: 31 43 Total Sorts
15 Ball: 13 Sorts 13 Balls Left Additional Sorts: 36 49 Total Sorts

Answer 7

I found an answer that uses

31 weighings, as mentioned in the hint.

I've written out all the steps I took, but I'm sure it could be easily generalized into an algorithm. I'm also on mobile, so hopefully spoilers worked.

! Split the balls into groups of 3 and weigh each. You now have 5 ordered sets of balls. We can call the lightest of each "A", the middle one "B", and the heaviest "C".

! ABC,ABC,ABC,ABC,ABC. 5 weighings, balls found: none.

! (Throughout this puzzle, any sequential symbols without a comma separating them are ordered. So A is lighter than B, which is lighter than C.)

! Weigh 3 A's, and make the new ordered set DEF.

! DEF,BC,BC,BC,ABC,ABC. 6 weighings, balls found: none.

! Weigh DAA to find the lightest of the balls and place it aside. The new ordered set will be GH, and we can be sure that neither G nor H is the heaviest, since they were selected from all the A's - the lightest balls.

! GH, EF, BC, BC, BC, BC, BC. 7 weighings, balls found: 1.

! Now let's rinse and repeat with the C's. Weigh 3 C's, and make the new ordered set IJK.

! IJK, IJ, GH, EF, B, B, B, BC, BC. 8 weighings, balls found: 1.

! Weigh KCC to find the heaviest of the balls and place it aside. The new ordered set will be LM, and we can be sure that neither L nor M is the lightest, since they were selected from all the C's - the heaviest balls.

! LM, IJ, GH, EF, B, B, B, B, B. 9 weighings, balls found: 1, 15.

! Now let's look for ball 2 and ball 14. M, J, H, and F are disqualified from 2 for being heavier than something, and L, I, G, and E are lighter than something, so they can't be 14.

! Candidates for 2: L, I, G, E, B, B, B, B, B.

! Candidates for 14: M, J, H, F, B, B, B, B, B.

! Let's weigh LIG, and call it NOP. We can also weigh MJH and call it QRS.

! NOP, QRS, EF, B, B, B, B, B. 11 weighings, balls found: 1, 15.

! Candidates for 2: N, E, B, B, B, B, B.

! Candidates for 14: S, F, B, B, B, B, B.

! Not candidates for either: OP, QR.

! Let's weigh N, E and a B, to make TUV. This means we replace one of the B candidates for 14 with V, since that B either is V or was heavier than it.

! TUV, OP, QRS, F, B, B, B, B. 12 weighings, balls found: 1, 15.

! Candidates for 2: T, B, B, B, B.

! Candidates for 14: S, F, V, B, B, B, B.

! Not candidates for either: OP, QR, U.

! Now weighing T and 2 B's (giving us WXY) will give us only three remaining candidates for 2. It'll also knock out one of the remaining candidates for 14, since we're comparing 2 B's.

! WXY, UV, OP, QRS, F, B, B. 13 weighings, balls found: 1, 15.

! Candidates for 2: W, B, B.

! Candidates for 14: S, F, V, Y, B, B.

! Not candidates for either: OP, QR, U, X.

! Now weighing W and 2 B's will find us ball 2and leave us... Z~. It'll also, again, knock out one of the remaining candidates for 14, since we're comparing 2 B's.

! Z~, XY, UV, OP, QRS, F. 14 weighings, balls found: 1, 2, 15. Candidates for 14: S, F, V, Y, ~.

! Now we can focus on ball 14. Weighing SFV will give us !@#.

! !@#, Z~, XY, U, OP, QR. 15 weighings, balls found: 1, 2, 15.

! Candidates for 14: #, Y, ~.

! Weigh the last three candidates, #Y~, to find ball 14, which we'll remove to leave us $%.

! $%, !@, Z, X, U, OP, QR. 16 weighings, balls found: 1, 2, 14, 15.

! Now our symbols are a mess, so I'm going to rename them quickly back to the beginning of the alphabet. The symbols don't matter as much as the order, so this won't change anything except to make it easier to read.

! AB, CD, E, F, G, HI, JK. 16 weighings, balls found: 1, 2, 14, 15.

! I'll weigh the lonely EFG, since they're only useful when compared to something. Now we can call them LMN.

! LMN, AB, CD, HI, JK. 17 weighings, balls found: 1, 2, 14, 15.

! Then we'll look for balls 3 and 13, in pretty much the same way as we did 2 and 14.

! Candidates for 3: L, A, C, H, J.

! Candidates for 13: N, B, D, I, K.

! Candidates for no one: M.

! Let's get 3 first. Weight LAC and call it OPQ.

! OPQ, MN, B, D, HI, JK. 18 weighings, balls found: 1, 2, 14, 15.

! Candidates for 3: O, H, J.

! Candidates for 13: N, B, D, I, K.

! Candidates for no one: M.

! Weigh OHJ to find 3. Stash it and call the others RS.

! RS, PQ, MN, B, D, I, K. 19 weighings, balls found: 1, 2, 3, 14, 15.

! Candidates for 13: N, B, D, I, K.

! For 13, weigh NBD, call it TUV.

! TUV, RS, PQ, M, I, K. 20 weighings, balls found: 1, 2, 3, 14, 15.

! Candidates for 13: V, I, K.

! Weigh the last 3 candidates, VIK, and the last one is 13. Call the remaining 2 WX. We'll be repeating the process for 4 and 12.

! WX, TU, RS, PQ, M. 21 weighings, balls found: 1, 2, 3, 13, 14, 15.

! Candidates for 4: W, T, R, P, M.

! Candidates for 12: X, U, S, Q, M.

! First we'll weigh RPM and rename them to YZ~. This means we replace one of the M as a candidate for 12 with ~, since that M either is ~ or was heavier than it.

! YZ~, WX, TU, S, Q. 22 weighings, balls found: 1, 2, 3, 13, 14, 15.

! Candidates for 4: W, T, Y.

! Candidates for 12: X, U, S, Q, ~.

! Weigh the last 3 candidates for 4. The lightest is 4, place it aside, we'll call the last 2 !@.

! !@, Z~, X, U, S, Q. 23 weighings, balls found: 1, 2, 3, 4, 13, 14, 15.

! Candidates for 12: X, U, S, Q, ~.

! Weigh XUS, rename the result to #$%.

! #$%, !@, Z~, Q. 24 weighings, balls found: 1, 2, 3, 4, 13, 14, 15.

! Candidates for 12: %, Q, ~.

! Weigh the last 3 candidates for 12. The heaviest is 12, so we can set it aside and call the last 2 ^&.

! ^&, #$, !@, Z. 25 weighings, balls found: 1, 2, 3, 4, 12, 13, 14, 15. I'll rename them back to the beginning of the alphabet again, then we'll be looking for 5 and 11:

! AB, CD, EF, G. 25 weighings, balls found: 1, 2, 3, 4, 12, 13, 14, 15.

! Candidates for 5: A, C, E, G.

! Candidates for 11: B, D, F, G.

! Weighing ACE -> HIJ gives us: HIJ, B, D, F, G. 26 weighings, balls found: 1, 2, 3, 4, 12, 13, 14, 15.

! Candidates for 5: H, G.

! Candidates for 11: B, D, F, G.

! Now we'll weigh HGB. The lightest will be 5, and by comparing G and B we've also given ourselves a head start on finding 11. We'll call the remaining 2 balls KL.

! KL, IJ, D, F. 27 weighings, balls found: 1, 2, 3, 4, 5, 12, 13, 14, 15.

! Candidates for 11: D, F, L.

! Weigh the only remaining candidates for 11, and the heaviest will be 11. We'll call the remaining ones MN.

! MN, K, IJ. 28 weighings, balls found: 1, 2, 3, 4, 5, 11, 12, 13, 14, 15. 6 must be M, K, or I. We'll weigh those next, set aside the lightest as 6, and call the remainder OP.

! OP, N, J. 29 weighings, balls found: 1, 2, 3, 4, 5, 6, 11, 12, 13, 14, 15.

! 10 must be P, N, or J. Weigh 'em, bag and tag the heaviest, and call the others QR.

! QR, O. 30 weighings, balls found: 1, 2, 3, 4, 5, 6, 10, 11, 12, 13, 14, 15.

! Only three balls remain, they must be 7, 8, and 9. Weigh QRO to find out the order.

! 31 weighings, balls found: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

Answer 8

1. Arrange all 15 balls in a line. Contrive the output of the machine in such a way that it will output the balls to the empty slots in this line and always in the same order.
   A simple illustration:
   1 2 3 4 5 6 7 8 9 A B C D E F
   With this situation, presume worst-case: the balls are perfectly sorted according to your wishes but in the reverse order, with the slightest ball, º1, where I want to place the heaviest, ºF.
   I.e., ball º1 is in slot ºF, and ball ºF is in slot º1.

2. Sort the balls from one end to the other in non-overlapping sets of 3: 5
   Ball º1 is now in slot ºD.

3. Sort the balls in sets of 2 which straddle the boundaries between the previous sets of 3: 4 + 5 = 9
   Ball º1 is now in slot ºC.

4. Repeat step º2: 5 + 9 = 14
   Ball º1 is now in slot ºA.

5. Repeat step º3: 4 + 14 = 18
   Ball º1 is now in slot º9.

6. Repeat step º2: 5 + 18 = 23
   Ball º1 is now in slot º7.

7. Repeat step º3: 4 + 23 = 27
   Ball º1 is now in slot º6.

8. Repeat step º2: 5 + 27 = 32
   Ball º1 is now in slot º4.

9. Repeat step º3: 4 + 32 = 36
   Ball º1 is now in slot º3.

10. Repeat step º2: 5 + 36 = 41
    Ball º1 is now in slot º1.

---

By 41 distinct uses of the sorting machine, every single ball is now sorted according to gravity.

Answer 9

It takes [31 operations] to sort the balls.

Edited to present my second attempt (see edit history for first attempt), this is similar to Etoplay's answer but not auto-generated:

The idea is to identify the remaining two lightest and two heaviest in each cycle. To that end we keep track which balls are still candidates for those four positions and defer disqualified balls to the next cycle. This should account for re-weighing balls against each other.

We track balls on a two dimensional field of pockets:

    0H  1H  2H
0L      
1L          
2L      

Where e.g. 1H stands for pockets that hold balls of which is known that at least one other ball is heavier, vice versa balls in 2L have been seen to be heavier than at least two other balls. Balls that get moved to (2L,2H) are no longer considered for any of the four positions. Number of operations is listed at end of header as [ops].

First Cyle with 15 balls [0]:

    0H  1H  2H
0L  15      
1L          
2L          

Sort in 5 weighings [5]:

    0H  1H  2H
0L  0       5
1L      5   
2L  5       

Find lightest by weighing 3 from (0L,2H), then weighing lightest against remaining 2 from (0L,2H) [7]:

    0H  1H  2H
0L  0      [1]
1L      5   2
2L  5       2

Find heaviest by weighing 3 from (2L,0H), then weighing heaviest against remaining 2 from (2L,0H) [9]:

    0H  1H  2H
0L  0       0
1L      5   2
2L [1]  2   4

Weigh 3 times to sort all from (1L,1H). Lightest goes to (1L,2H), heaviest goes to (2L,1H), middle can be put to (1L,1H) of next cycle already, remaining two go to (2L,2H) [12]:

    0H  1H  2H      Next    0H  1H  2H
0L  0       0       0L      ?   
1L      0   3       1L          1   
2L  0   3   6       2L          

Weigh (1L,2H) and (2L,1H) to identify second lightest and second heaviest, remaining 10 move to (0L,0H) in next cycle [14]:

    0H  1H  2H      Next    0H  1H  2H
0L  0       0       0L      10      
1L      0  [1]      1L          1   
2L  0  [1]  10      2L          

Second cycle with 11 balls [14]:

    0H  1H  2H      
0L  10              
1L      1           
2L                  

Sort four times from (0L,0H), reuse two from (1L,1H) to fill fourth weighing [18]:

    0H  1H  2H
0L  0       4       
1L      3           
2L  4               

Determine third lightest and defer one by sorting twice from (0L,2H), two middle ones go to (1L,2H) [20]:

    0H  1H  2H
0L  0      [1]
1L      3   2
2L  4       1

Third heaviest and defer one by sorting twice on (2L,0H), two go to (2L,1H) [22]:

    0H  1H  2H
0L  0       0
1L      3   2
2L [1]  2   2

Find remaining candidates for fourth lightest and heaviest by sorting (1L,1H) [23]:

    0H  1H  2H
0L  0       0
1L      0   3
2L  0   3   3

Determine fourth lightest and heaviest [24]:

    0H  1H  2H
0L  0       0
1L      0  [1]
2L  0  [1]  7

Third cycle [24]:

    0H  1H  2H
0L  7       
1L          
2L          

Sort three times from (0L,0H) reusing two from (1L,1H) [27]:

    0H  1H  2H
0L  0       3
1L      1   
2L  3       

Determine fifth lightest from (0L,2H) [28]:

    0H  1H  2H
0L  0      [1]
1L      1   1
2L  3       1

Determine fifth heaviest from (0L,2H) [29]:

    0H  1H  2H
0L  0       0
1L      1   1
2L [1]  1   2

Determine sixth lightest and heaviest by sorting from (1L,2H), (1L,1H) and (2L,1H) [30]:

    0H  1H  2H
0L  0       0
1L      1  [1]
2L  0  [1]  2

Sort remaining 3 balls and insert in middle [31].

Answer 10

Assuming weighting machine can take 3 or 2 balls at a time.

1. Divide the balls into 5 groups 3 in each.
   [ooo],[ooo],[ooo],[ooo],[ooo]
   
   

2. weight all groups one by one to sort balls in group (A,B,C,D & E).
   A: [(1),(2),(3)],
   B: [(1),(2),(3)],
   C: [(1),(2),(3)],
   D: [(1),(2),(3)],
   E: [(1),(2),(3)]
   
   

3. Take (1), (2) & (3) of each group and form 3 groups like this.
   [(1A),(1B),(1C)] [(1D),(1E)] ... similarly for 2nd and 3rd ball.
   
   

4. Now taking one group out of 3 (1,2,3) at a time, we will try to eliminate lightest and heaviest.

   a. Sort [(1A),(1B),(1C)] & [(1D),(1E)] which will ensure either 1A or 1D will be the lightest.
   b. Sort (A) and (D) // this will give lightest of all.
   c. Similarly Sort [(3A),(3B),(3C)] & [(3D),(3E)] and Sort (A) and (D) this will give heaviest of all.
   d. Count fron step 1 is 5(step 2) + 2(step 4.a) + 1(step 4b) + (step 4c) = 9
   
   

5. Now we are left with 13 balls and we will aim to get 2nd lightest and 2nd heaviest.
   
   

6. Repeat same process from step 1 to get lightest and heaviest balls, repeat till we have just 3 balls left.
   
   

7. Count of weights Will go like:
   a. 15 Balls ---| 5 + 2 + 1 + 1 = 9
   b. 13 Balls ---| 5 + 2 + 1 + 1 = 9
   c. 11 Balls ---| 4 + 2 + 1 + 1 = 8 (in step 1 make group of 3,3,2,2 balls)
   d. 09 Balls ---| 3 + 0 + 1 + 1 = 5
   e. 07 Balls ---| 3 + 0 + 1 + 1 = 5
   f. 05 Balls ---| 2 + 0 + 1 + 1 = 4 (in step 1 make group of 3,2 balls)
   g. 03 Balls ---| 5 + 0 + 0 + 0 = 1 (only one sort will order them)
   
   

8. Step 7 sums up to 41 weights.

Answer 11

My last answer was horribly wrong (I didn't quite think it through). I came up with a different strategy that doesn't get the result you're looking for, but perhaps someone can improve on it.

When you sort any 3 balls we know what they cannot be. The lightest of the 3 cannot be the heaviest or second heaviest of the remaining balls, the middle of the 3 cannot be the lightest or heaviest of the remaining balls, and the heaviest of the 3 cannot be the lightest or second lightest of the remaining balls.

First level:

with 5 sorts, we can create three piles of 5:
- a "not 14 and not 15" pile,
- a "not 1 and not 15" pile and,
- a "not 1 and not 2" pile

we can use 2 sorts on each outer pile to determine #1 and #15 for a total of 9

Second level:

there are 13 balls remaining, 4 of which are "not 2" and 4 of which are "not 14"
we'll take the "not 14" group of 4 and the group of 5 together to find out which of these balls is #2
we can use 3 sorts to split the 9 into 3 piles, then one more sort on the "light" pile to figure out #2
we're now at 13 sorts

Third level:

with 12 balls remaining (#3-#14), we'll use 4 sorts to put them in 3 piles of 4:
- a "not 13 and not 14" pile,
- a "not 3 and not 14" pile and,
- a "not 3 and not 4" pile
we can again use 2 sorts on each outer pile to determine #3 and #14
we are now at 21 sorts

Fourth level:

there are 10 balls remaining, 3 of which are "not 4" and 3 of which are "not 13"
we'll take the "not 13" group of 3 and the group of 4 together to find out which is #3
we can find #4 (the lightest of 7 balls) using 3 sorts
we're now at 24 sorts

Fifth level:

with 9 balls remaining (#5-#13), we'll use 3 sorts to put them in 3 piles of 3:
- a "not 12 and not 13" pile,
- a "not 5 and not 13" pile and,
- a "not 5 and not 6" pile
we can sort the outer piles 1 time each to find out #5 and #13
we are now at 29 sorts

Sixth level:

there are 7 balls remaining, 2 of which are "not 6" and 2 of which are "not 12"
we'll take the "not 12" group of 2 and the group of 3 together to find out #6
we can find #6 (the lightest of the 5) in 2 sorts
we're now at 31 sorts

Seventh level:

with 6 balls remaining (#7-#12), we'll use 3 sorts to put them in 3 piles of 2:
a "not 11 and not 12" pile, a "not 7 and not 12" pile and, a "not 7 and not 8" pile
we can sort the outer piles 1 time each to find out #7 and #12
we're now at 36 sorts

Eighth level:

there are 4 balls remaining, 1 of which is "not 8" and 1 of which is "not 11"
we can take the "not 11" ball and the other 2 balls and sort them once to find #8
we can then sort the remaining 3 balls once to fill in the rest for a total of 38 sorts

Answer 12

I don't have enough rep to comment, but I wanted to add that I came to the same answer as @Etoplay (29 sorts), just without the specific math behind it and his solution is more attractive than mine (easier to keep track of positions than possible weights).

I did it by hand in a sort of Sudoku way, essentially you have 15 balls of 15 possible weights. Split them into 5 groups of 3 and sort them. Basically, whenever you sort a group of balls they will range from the lowest min possible weight of any ball in the group to the highest max, so initially it's 1-15 for all balls in all groups. When sorting a group, you can eliminate the highest 2 weights of that group from the lightest ball, the top and bottom from the middle, and the lightest 2 from the bottom. This leaves you with 3 groups: Not 1/2, Not 1/15, Not 14/15.

From there you continue and you sort groups as "perfectly" as you can (where all 3 balls have the exact same possible ranges). In a situation where you don't have 3 with the exact same range, take a ball that has the opposite end line up. For example: 2 balls with range 4-12 and a ball with range 4-10 (nothing else with a range including 4). The 4-10 ball loses the information that it can't be 11-12 since you can't identify it when they come out, but you end up with 1 ball that is definitely 4, 1 that is 5-11, and 1 that is 6-12.

You continue this way narrowing it down from the ends until you're left with 3 balls and the final sort finishes the ordering.

I did feel like I may have done it sub-optimally as part-way through I sorted the interior ranges instead of the outer ranges which I felt might have wasted a sort (or 2) to lost information later, but if @Etoplay's math is correct it looks like it didn't affect the solution at all.

Answer 13

Leverage that you can sort 3

34

This a little hard to follow but I think it is correct 

5 sort for groups of 3        
a   a   a    
b   b   b    
c   c   c    
d   d   d   
e   e   e   

Sort 6  adb H       
Sort 7  W Sort 6 with de        

1  (have #1)         

Sort 8  adb  L      
Sort 9  L Sort 8 with de        

1           
15  (have # 15)


13 left     4 H cannot be 14 (know from original sort 2 below)
            5 M 
            4 L cannot b 2 (know from original soft 2 above)
            **critical trick**

3 sorts of 4H + 5M          
Sort 10 3 H     
Sort 11 1 H 2M      
Sort 12 2 M     
Sort 13 Sort W of 3 above   

1           2 H
2           3 M
15          4 LA    3 LB

Sort 14 3 LA        
Sort 15 1 LA 2 LB       
Sort 16 L L 1LB     

1       2 H 
2       3 M 
14      6 L 
15          

Sort 17 3 M     
Sort 18 W 2H         
(may need to add a sort with the 2 H from sort 14 and 15)

1       4 M H   
2           
3       6 L 
14          
15          

Sort 19 3 L     
Sort 20 3 L     
Sort 21 L L     

1       5 M H   
2           
3       5 L 
13          
14          
15          

mix and sort 9          
Sort 22         
Sort 23         
Sort 24         
Sort 25 H H H       
Sort 26 L L L       

1       2 H 
2       3 M 
3       2 L 
4           
12          
13          
14          
15          
Sort 27 3 M     
Sort 28 W 2H        
1       2 H 
2       2 M 
3       2 L 
4           
5           
12          
13          
14          
15          
mix and 2 set of 3      
Sort 29         
Sort 30         
Sort 31 2 H     
Sort 32 2 L     

1       1H  
2       2 M 
3       1 L 
4           
5           
6           
11          
12          
13          
14          
15          
Sort 33 1H 2M   

1       2 M 
2       1 L 
3           
4           
5           
6           
7           
11          
12          
13          
14          
15          
Sort 34 Last 3      
1           
2           
3           
4           
5           
6           
7           
8           
9           
10          
11          
12          
13          
14          
15          

another try I know hard to follow but I think I got in in 30

H high   M is middle and L is low       

sorts count     position known (1 high)
5   Create 5 groups of 3 (a,b,c,d,e,f)  
6   sort aH bH cH   
7   sort high of 6 with dH eH   1
8   sort aL bL cL   
9   sort low  of 8 with dL eL   1,15
10  sort aM bM cM   
11  sort 10H with dM eM 
12  sort 11H with soft 6M sort 7M   1,2,15
13  sort 10 Lwith dM eM 
15  sort 13L with sort 8M sort 9M   1,2,14,15
16  sort 13M with left over from sort 12 keep L 
17  sort 12M with left over from sort 11 keep H 
    now down to 9   
18  group a 
18  group b 
20  group c 
21  sort aH bH cH   
22  sort 21H 21M with 16    1,2,13,14,15
23  sort aL bL cL   
24  sort 23L 23M  with 17   1,2,3,13,14,15
25  sort aM bM cM   
26  Sort 25H with 16M 16L   1,2,3,12,13,14,15
27  sort 27L with 17M 17L   1,2,3,4, 12,13,14,15
28  sort the three that are the 3 left over from 26 and 27  
29  Sort 28H with 26    
30  Sort 28L with 27    done

Answer 14

I'm 3 years late to this puzzle, but I think I just solved it in 29 steps, and I'm too gosh darned proud to not post my answer. Especially since I struggled to follow some of the other answers.

For the sake of my work, I label the balls as W1-W15, with the W1 being the lightest and W15 being the heaviest.

Sorts 1-5:

Select balls randomly, three at a time, and sort them. Place balls into three groups based on the sorting. All of the heaviest balls go in the H group. All of the lightest balls go in the L group. All of the middle balls go in the M group. Our goal will be to place balls W1-W5 in the L group, balls W6-W10 in the M group, and balls W11-W15 in the H group.

There are a few very important facts that I derived regarding this sorting they are:

One:

W1 must be in the L group and W15 must be in the H group.

Two:

Only one ball from the W11-W15 group can be in the L group, and only one ball from the W1-W5 group can be in the H group.

Three:

The L and H groups must contain a minimum of two balls that belong to the appropriate set. it is impossible for them to contain any fewer.

Four:

The M group must contain at least one ball in the appropriate set. That ball will also have the middle weight of the five balls initially in that set.

Sorts 6 - 7:

Select 3 random balls from the L group and sort them. Mentally label the heaviest of the three as LH1 (Light-Heaviest, in my nomenclature). Take the lightest from that weighing and weigh it against the remaining two. Mentally label the heaviest of the three as LH2. Remove the lightest of the three as W1, the lightest weight.

Sorts 8 - 9:

Select 3 random balls from the H group and sort them. Mentally label the lightest of the three as HL1. take the heaviest and weigh it against the remaining two unweighed balls. Label the lightest as HL2. Remove the heaviest of the three as W15.

Sorts 10-12:

Select 3 random balls from the M group and sort them. Label the heaviest and lightest as MH and ML, respectively. Weigh MH against the two remaining balls. Take the heaviest from that weighing and add it to the H group. Take the lightest from that weighing and weigh it against ML. Place the lighter of the two in the L group.

Sort 13:

Weigh the remaining three balls in the M group against one another. Remember our fourth consideration from the start of this-- this ball for sure belongs to the group W6-W10. Label it as MM and set it aside; we won't be weighing anything against it for a while.

Sort 14:

In the H group, weigh the ball from the M group against the balls that are not HL1 or HL2. Remove the heaviest as W14. Label the lightest as HL3.

Sort 15:

In the L group, weigh the ball from the M group against the balls that are not LH1 or LH2. Remove the lightest as W2. Label the heaviest as LH3.

Sorts 16 and 17:

Sort the HL balls against one another, and sort the LH balls against one another. Place the lightest and heaviest respectively in the M group.Label the middle ball from each sort as HM and LM, respectively.

Sorts 18-19:

In the M group, weigh three randomly selected balls that are not MM. Weigh the heaviest and the lightest from this group against the remaining ball that is not MM. Transfer the heaviest of the result to the H group, and the lightest of the result to the L group.

Sorts 20 and 21:

Recognize that balls HM and LM cannot be W13 or W3. Weigh the three other balls in the H group against one another and select the heaviest as W13. Repeat this for LM in the L group, removing W3.

Sorts 22 and 23:

There are 3 balls remaining in the L and H groups. Sort the L group against itself and the H group against itself. Remove the lightest and heaviest, respectively, as W4 and W12. Label the middle balls in each sort as LL and HH, respectively.

Sorts 24 and 25:

Weigh LL against the two balls in the M group that are not MM. Remove the lightest as W4. Weigh the two other balls from that weighing against HH, and remove the heaviest as W12.

Sorts 26 and 27:

Combine the five remaining balls. Remove all mental labels. Weigh three random balls against one another. Label the lightest as L1. Weigh the heaviest against the remaining unweighed balls. Remove the heaviest as W10. Label the lightest as L2

Sort 28:

Weigh L1 against L2. Remove the lightest as W6.

Sort 29:

There are 3 remaining balls. Weigh these three against one another, and select them in order as W7, W8, and W9.