29
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ The title is clearly clickbait. :^) $\endgroup$ – Num Lock Oct 11 '16 at 8:23
  • $\begingroup$ By my intuition, the worst case scenario is going to be akin to a ternary heapsort which should have a worse case of n log n (log base 3 in this case because of our 3-way sorting machine). 15 log3 15 rounds to 37, so I'm inclined to think your count is low and might use a dataset that favours your algorithm rather than proving a worst case. $\endgroup$ – Danikov Oct 11 '16 at 16:39
  • $\begingroup$ @Danikov: The sorting machine provides more than 1 trit of information: it returns a complete ordering of the three balls inserted. Some of that information gets lost on repeated weighings, but not all of it. $\endgroup$ – user3294068 Oct 11 '16 at 17:01
  • 1
    $\begingroup$ This sounds like a job for a sorting network... except that traditional sorting network comparators are two-way. Still, many of the same ideas apply. $\endgroup$ – user2357112 Oct 11 '16 at 18:02
  • $\begingroup$ I found this as 22 if I did not do any serious mistake. I will post my answer soon, but I have guaranteed that it will be less than 25 anyway, are you sure the answer is 29? $\endgroup$ – Oray Oct 23 '16 at 15:01

13 Answers 13

12
$\begingroup$

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}$

$\endgroup$
  • $\begingroup$ I'm trying to understand what your resulting weights are doing. (I was also working on an improved solution.) Is it right to assume that the first two terms in each block are supposed to be in a bracket? $\endgroup$ – Murch Oct 11 '16 at 20:27
  • $\begingroup$ @Murch Yes there were some brackets missing. I used some tex to make it better readable. This formulas makes first all three weights equally bad (by taking the min) and then only make them better by maxing with the new value not adding since I don't know if they are different weights. $\endgroup$ – Etoplay Oct 11 '16 at 21:10
  • $\begingroup$ That looks impressively efficient. $\endgroup$ – Gareth McCaughan Oct 11 '16 at 22:13
  • $\begingroup$ This is the most efficient algorithm I've seen, but I am not sure how to evaluate its accuracy. $\endgroup$ – user3294068 Oct 12 '16 at 14:01
  • $\begingroup$ @Etoplay: I've redone my solution so it actually works but need 31, so it seems yours is the most efficient solution so far! Congrats! Still looking to find a bit more efficiency in my solution, though! ;) $\endgroup$ – Murch Oct 12 '16 at 14:41
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I claim only that the single lightest is the single lightest, and similarly for the heaviest. So in your case we start with 168 and 9AC. We put 19 and 8C into the box, identifying 1 and C as lightest and heaviest, and now have 689A in unknown order except that we know 9 isn't overall heaviest and 8 isn't overall lightest. So now we put 69A into the box, discovering that 6 is the lightest of our four (to repeat, 8 wasn't a candidate, having been heaviest of the first group), giving 16xxxC. Now put the three remaining balls into the box. Done. $\endgroup$ – Gareth McCaughan Oct 11 '16 at 7:53
  • $\begingroup$ Ok, I'm still having a hard time following your description, but I figured I'd get some PHP practice and got to the nine-tuple and sex-tuple part. I put the code on pastebin. You can copy/paste the RAW Paste Data (very bottom of the page) into phpfiddle to see it in action. (Scroll down, hit "Get the Code", delete everything in the box, paste the stuff from pastebin, hit Run. You can click "Code Space" then "Run" to generate a new random list.) $\endgroup$ – MichaelS Oct 11 '16 at 10:11
  • $\begingroup$ I'm pretty sure step 2a works fully, because the lightest 2 balls are guaranteed to be within the 4 balls made from the lightest 2 of each triplet. This means the 3 leftover to sort are guaranteed not to contain the lightest 2, nor the heaviest 1, so we can slot it into the middle. $\endgroup$ – Samthere Oct 11 '16 at 10:17
  • $\begingroup$ "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" - sorry, which are these latter three? $\endgroup$ – Andrew Savinykh Oct 11 '16 at 10:26
  • $\begingroup$ @AndrewSavinykh When you have the ordered pair and two left over, you take the heavier of the pair and both of the leftovers. $\endgroup$ – Samthere Oct 11 '16 at 10:29
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ While this is certainly one answer, I'm not sure that it's the best one: you're potentially discarding useful information by pooling all discarded balls. $\endgroup$ – Danikov Oct 11 '16 at 15:56
  • $\begingroup$ FWIW, this is a bidirectional selection sort. It is also possible to perform the analog of a bubble sort, which also requires 49 weighings. $\endgroup$ – PellMel Oct 11 '16 at 21:15
5
$\begingroup$

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
$\endgroup$
  • $\begingroup$ So does "lighter" mean "known not to be the heaviest" and "heavier" mean "known not to be the lightest"? (In each case, of course this means "among the balls not yet conclusively placed".) $\endgroup$ – Gareth McCaughan Oct 11 '16 at 11:41
  • $\begingroup$ This might be better conveyed as a ternary heapsort? $\endgroup$ – Danikov Oct 11 '16 at 16:42
  • $\begingroup$ @GarethMcCaughan: Yes $\endgroup$ – tehtmi Oct 11 '16 at 17:43
  • 2
    $\begingroup$ @Danvikov: Bubble (pop) in a heap is difficult here because the nature of the scale. It isn't the same as a traditional comparison. Trying to use the scale on a node leaves both branches "dirty". As for ternary heapsort, I see some similarity, but I don't see immediately how my answer can be fully framed in that way. $\endgroup$ – tehtmi Oct 11 '16 at 17:50
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note that you actually have 4 + 1 -2-> done, i.e. one step less than you claimed for that case. You weigh the 1 with the two heavier of the 4 to get the two heaviest of the five. Then you weigh the other 3 to establish their relative order. But since you don't use that rule, it doesn't affect your result. $\endgroup$ – PellMel Oct 11 '16 at 21:35
  • $\begingroup$ Yup, quite right. I think I even used that construction in my other answer, so it's particularly embarrassing to have missed it here :-). $\endgroup$ – Gareth McCaughan Oct 11 '16 at 22:06
  • $\begingroup$ @GarethMcCaughan: I was going to post a comment that, in challenges like this one, it’s conventional to state your numerical result (i.e., score) as a <h1>headline</h1> at the top of your answer, not hidden (spoilered), as, for example, we (Puzzling Stack Exchange) did here, and as Programming Puzzles & Code Golf (where you lurk) does it all the time. But then I saw that everybody was doing it, even the 6th highest user on the site! Do you believe that scores should be hidden or highlighted, and, if hidden, why? $\endgroup$ – Peregrine Rook Oct 14 '16 at 3:07
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ FWIW, this is essentially a bubble sort. $\endgroup$ – PellMel Oct 11 '16 at 21:23
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You created "DEF" from comparing three of the A, therefore E is also disqualified from being the second smallest, as it was bigger than the associated BC. $\endgroup$ – Murch Oct 11 '16 at 22:15
  • $\begingroup$ @Murch that's a good point, although I think that disqualifies E from being the second largest, not smallest. J would similarly not be the second smallest. There may be more optimizations like that as well, it's sort of hard to keep track of what everything could be. $\endgroup$ – Kokiomot Oct 11 '16 at 22:39
  • $\begingroup$ Since E came from ABC, there are at least two balls that are heavier. Since it is now in second position in DEF, it can't be largest, but it still could be second largest. $\endgroup$ – Murch Oct 11 '16 at 22:54
  • 1
    $\begingroup$ Sorry, I meant lightest instead of largest. A is lighter than B… So, since E derives from an A, there are a B and a C that are heavier than E. On the other hand, E is heavier than D. Therefore, it cannot be the lightest, and there must be at least two heavier than it. $\endgroup$ – Murch Oct 11 '16 at 23:07
  • 1
    $\begingroup$ I've just tried it with tracking the next two lightest candidates and two heaviest, it still takes 31. Either there is a better order or you were already tracking sufficient information: pastebin.com/NtEDz5cw $\endgroup$ – Murch Oct 12 '16 at 17:37
1
$\begingroup$
  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.

$\endgroup$
  • $\begingroup$ So BubbleSort? Couldn't you pick sets of three instead of just two so balls can move two spaces per weighing? $\endgroup$ – Murch Oct 12 '16 at 7:50
  • $\begingroup$ @Murch Yes, but with a pool of 15 items, it takes the same number of actions to use that procedure. If the sorting machine's capacity was not a factor to the size of the pool, then your method would be used anyways so as to accomodate the excess. I honestly chose this method because it has faint elegance within the parameters. $\endgroup$ – can-ned_food Oct 17 '16 at 1:18
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I don't think this works. When you weigh 3 balls from a cell (L, H) against each other, you don't always get to move them to (L+2, H), (L+1, H+1), and (L, H+2), because you might have already weighed some of those balls against each other before. Re-weighing balls you've already weighed against each other doesn't let you increase their L and H numbers. $\endgroup$ – user2357112 Oct 11 '16 at 18:12
  • $\begingroup$ Oh no! Good point! I was feeling so clever for a moment. :-( $\endgroup$ – Murch Oct 11 '16 at 18:16
  • $\begingroup$ @user2357112: I've improved my solution. It should work in 31 operations now. $\endgroup$ – Murch Oct 12 '16 at 14:56
  • $\begingroup$ I don't follow you table $\endgroup$ – paparazzo Oct 13 '16 at 13:05
  • $\begingroup$ @Paparazzi: If there is a ball known that is heavier than our ball, we can move our ball to the right, to 1H. If a ball is known that is lighter than our ball, move our ball to 1L. I.e. if we weigh three balls, from the 'nothing known' pocket (0L,0H) the heaviest will go to (2L,0H) (at least two are lighter, zero known to be heavier), middle one goes to (1L,1H) and lightest to (0L,0H). $\endgroup$ – Murch Oct 13 '16 at 19:58
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You actually have only created three sorted groups of five balls. You can't just place them after each other to form the total order, because there is no guarantee that e.g. 2A is smaller than 1B. You only know that 2A is smaller than 1A. Counter example: A: [(1),(2),(3)], B.[(6),(7),(8)]. 2A is not smaller than 1B. $\endgroup$ – Murch Oct 12 '16 at 7:46
  • $\begingroup$ @Murch, Yes you are correct. I guess I have to think in some other way.. thanks for your response. $\endgroup$ – Ankit Sharma Oct 12 '16 at 12:07
  • $\begingroup$ Edited my Answer, seems to be correct this time, but not sure if this is the most optimum one. $\endgroup$ – Ankit Sharma Oct 12 '16 at 12:48
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This sounds pretty similar to Kokiomot's solution and my attempt to improve it. I have typed it up here: pastebin.com/NtEDz5cw It took 31 tries though, so if you see where I could have saved two tries, I'd be happy if you told me. :) $\endgroup$ – Murch Oct 13 '16 at 7:22
0
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ I think this could do with being explained more clearly. $\endgroup$ – Gareth McCaughan Oct 11 '16 at 11:39

protected by Aza Oct 12 '16 at 9:55

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.