15
$\begingroup$

There are $15$ balls. Each of them has a different weight. You want to sort them according to their weights.
You have a friend who will help you with his scale to do this. At each weighing process, you will give $3$ balls to him. Then he will specify the order of weights of these $3$ balls. But, he will not say the weights of the balls. (for example: For three balls, he will say only order: $a \gt b \gt c$ )

At least how many weighing are needed to ensure that all the balls are correctly ordered by their weights?

Improve this question
$\endgroup$
4
  • $\begingroup$ Can we ask your friend to weigh in group, like (a,b,c), (d,e,f), (g,h,i) resulting (a,b,c) > (d,e,f) > (g,h,i) ? $\endgroup$
    – Jamal Senjaya
    Commented Aug 23, 2016 at 22:17
  • $\begingroup$ @JamalSenjaya No, by how the puzzle is stated and by how everybody understood it. $\endgroup$
    – yo'
    Commented Aug 23, 2016 at 22:30
  • $\begingroup$ I am not sure to understand well (English is not my native language): can you confirm that "at least" means "minimum" ? So if we are lucky, what is the minimum weighing count? I ask, because I do not see really an answer about that. Am I wrong? $\endgroup$
    – lemon
    Commented Aug 26, 2016 at 11:36
  • $\begingroup$ @lemon: there is also the phrase "to ensure", so the question is asking "What is the minimum number of weightings such that for all cases, you can always find the order of the 15 balls?" $\endgroup$
    – justhalf
    Commented Sep 19, 2016 at 9:19

6 Answers 6

Reset to default
11
$\begingroup$

I can do it in

22 weighings.

Step 1: use 5 weighings, each with 3 new balls, yielding 5 "stacks" that are sorted (imagine the balls stack like coins).

Step 2: Make a state diagram covering all the cases where we have 5 sorted stacks (if two or more apply, pick the earliest):

  • A: We know the order of the top coins in 3 of the stacks. For example, $a > b > c$.
  • B: We know the order of disjoint two pairs. For example, $b > c$ and $d > e$.
  • C: We know one coin is heavier than two others. For example, $d > e$ and $d > a$.
  • X: We know less than any of the above.

We start in state X. Actions to take depending on state:

  • A: Weigh $a, d, e$. This is guaranteed to identify a new heaviest coin. Set it aside. If the heaviest coin is $a$, then we are now in state B. Otherwise, we remain in state A.
  • B: Weigh $a, b, d$. This is guaranteed to identify a new heaviest coin. Set it aside. If the coin $a$ is heaviest, we remain in state B. If $a$ is middle, we move to state A. If coin $a$ is lightest, we move to state C.
  • C: Weigh $d,b, c$. This is guaranteed to identify a heaviest coin. Set it aside. If $d$ is heaviest, we end up in state X. If $d$ is middle, we are in state C. If lightest, we end up in state B.
  • X: Weigh $a,b, c$. We do not identify a heaviest coin, but are guaranteed to end in state A.

The only way to return to state X is by passing through A to B to C to X. Thus, starting in state X, we can guarantee to identify the next three heaviest coins in at most four weighings. Repeat this four times to use 16 weighings to identify the 12 heaviest coins, leaving 3 left. One more weighing will identify the order of those 3.

So we have 5 weighings in step 1 and at most 17 weighings in step 2, for a total of 22 weighings. Best case is when we never return to state X, for a total of 19 weighings.

Improve this answer
$\endgroup$
10
  • $\begingroup$ I really like this approach, and this was a well written and easy to follow example. I think the result is correct, but the state diagram does not encompass all possibilities. For example, X => a > b > c| A => a > d > e| B => a > b > d| B => a > b > d. Now stack a has been exhausted. We could continue with Action B until, without loss of generality, stack c is also exhausted. Your state diagram would have us stick with action B, however we no longer know b > ?? and d > e since c is gone. It is (I think) possible to get back to X not through C $\endgroup$
    – stevenjackson121
    Commented Aug 23, 2016 at 1:12
  • $\begingroup$ My heart is convinced that you are correct, and I think it will be a minor tweak to make the state diagram cover cases where there are 4 or 3 stacks remaining (3 stacks will always generate a new heaviest coin). I also think you can improve your best case (I know it wasn't in OP question). If 2 piles are exhausted immediately (7 weighings), and you then exhaust a 3rd pile with 3 weighings, you can write a state diagram for the 2 stack case such that if a1 > a2 > b1, you take 2 off _a1 at once. This can get 4 coins off with 2 weighings. 1 more wieghing finishes it. 13 weighings best case $\endgroup$
    – stevenjackson121
    Commented Aug 23, 2016 at 1:25
  • $\begingroup$ I think the best case is far less than 19 weighings. $\endgroup$
    – Tony Ennis
    Commented Aug 23, 2016 at 5:11
  • 1
    $\begingroup$ Good points. I didn't deal with tweaks to improve best case; I was focused on worst case, and proving 22 was enough. Stack exhaustion only makes things easier. I think best case would be 16: 7 to remove the first ball, 5 more to eliminate a total of two stacks, 3 to eliminate six more, and 1 for the last three. $\endgroup$
    – user3294068
    Commented Aug 23, 2016 at 13:47
  • $\begingroup$ I imagine there's an algorithm with a faster worst case. My first 6 checks are ideal: each divides the solution space by a factor of 6. But my 7th check is far less efficient. But a faster algorithm might have to be terribly complex. $\endgroup$
    – user3294068
    Commented Aug 23, 2016 at 13:50
10
$\begingroup$

25 is an upper bound on the number of weighings you need.

Lemma: Fully ordering a pile of 5 stones takes 4 weighings (this is easy to prove but I can do so if necessary).

Fully ordering a pile of 5 stones can be done as follows:

a.) Assign each stone a number.

b.) Weigh stones 1, 2, and 3. Based on the results, renumber the stones so that 1 is the lightest, 2 is second, and 3 is the heaviest of the 3.

c.) Using the new numbers, weigh stones 3, 4, and 5. Based on the results, renumber them if necessary. If stone 3 remained stone 3, you are now done (2 weighings total). If not, stone 5 is at least guaranteed to be the heaviest stone overall.

d.) Again using the new numbers, weigh stones 2, 3, 4 and renumber if necessary. if no reordering was necessary, you are now done (3 weighings total). If not, stone 4 is at least guaranteed to be the second heaviest stone overall.

e.) Now that stones 4 and 5 are in the right place, weigh (using the new numbers) stones 1, 2, and 3 again. Renumber them based on the result, and now all 5 stones are guaranteed to be ordered correctly.

Details:

1.) Split the input stones into 3 piles of 5 stones (No weighings required)

2.) Order each of the 3 piles

(2-4 weighings each, 6-12 total weighings are required)

3.) While there are stones left in each pile (and more than 3 stones left total), weigh the heaviest stone from each pile. Put the heaviest one in the next available spot in the output area. This step will be repeated 12 times (then only 3 stones are left).

3.a) If you are lucky, all of the first 5 heaviest stones will come from the same sub pile (5 weighings done). The 6th heaviest stone is also now clear. You can now compare the 2 heaviest stones from the shorter pile with the single heaviest from the other pile. If you continue to be lucky, the 2 heaviest stones are both heavier than the heaviest from the other pile. Then you can put both into the output area at once. In this way, you can go from piles of 4-5 to 2-5 to 0-5, at which point you need no further weighings. This can skip step 4.

(7-12 weighings total)

4.) Weigh the last 3 stones, and put them in the correct order.

(1 weighing)

.

In the worst case this strategy requires 25 weighings. If you are given completely sorted input (or randomly generate the piles very luckily) step 2 will only take 6 weighings and step 3 will only take 7. Best case is 13 weighings, worst case is 25 under this strategy.

Improve this answer
$\endgroup$
9
  • $\begingroup$ I believe this method has a range of 16-25 weighings required. Step 2, with good fortune, can be done in 9, and Step 3 in 12. Excellent algorithm. $\endgroup$
    – Sconibulus
    Commented Aug 22, 2016 at 19:38
  • $\begingroup$ I arrived at the same totals you did: 16-25 weightings required. However, I believe you meant to say Step 2, with good fortune, can be done in 6. With the specific method I outlined in my edit, the "good fortune" case actually corresponds to sorted input, so this method should perform better the closer to sorted the input already was. $\endgroup$
    – stevenjackson121
    Commented Aug 23, 2016 at 0:46
  • $\begingroup$ @user1540815 It is a good adhoc approach, kudos :) $\endgroup$
    – ABcDexter
    Commented Aug 23, 2016 at 4:38
  • 1
    $\begingroup$ I'm not sure I understand. In step 3, by "no more than 3 stones left" do you mean "more than 3 stones left"? And please could you clarify "the 3 heaviest stones from each pile"? Which 3 stones, exactly? $\endgroup$
    – Rosie F
    Commented Aug 23, 2016 at 6:14
  • $\begingroup$ Wow, I typo'd my comment pretty horribly, my initial thought was 9/7 split between steps 2 and 3, skipping step 4. You've shown me a 6/7 split, which I've suggested an edit to add to your answer. 13-25 is pretty good, considering the absolute minimum best case is 7. $\endgroup$
    – Sconibulus
    Commented Aug 23, 2016 at 13:03
5
$\begingroup$

It should be at least (the strict lower bound) :

$\lceil \log_6(15!)\rceil$ = $16$

Its reasoning:

Total possible orderings are: $15!$ i.e. factorial(15)
At least $\log_6(15!)$ is needed because at a time three weights are used and out of 6 possibilities, one is output.

Using the Quick sort (the median of three pivot) algorithm (I might be completely wrong in using this algorithm, 3 partition merge sort with an ad-hoc merge function would be better). Each call to the ordering(weighing) function gives you one ordering(a tuple of 3 weights).
So, after running on Ideone, $28$ is output.

The actual answer showing optimal comparisons needs a better algorithm.

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ My answer (I believe) hits that lower bound! Would you mind giving it a quick look to see if there are any obvious errors? $\endgroup$
    – stevenjackson121
    Commented Aug 22, 2016 at 19:32
  • 4
    $\begingroup$ Why are you using 3 as the base of the logarithm? There are 6 possible outcomes of each 3-ball weighing operation, so the base of the logarithm should be 6. (As an example of why the base isn't the number of balls involved in a weighing, consider how many operations it takes to sort 15 balls with a 15-ball weighing operation.) $\endgroup$
    – user2357112
    Commented Aug 22, 2016 at 20:37
  • 2
    $\begingroup$ @TonyEnnis Well, the answer is a lower bound for the worst case, not for the best case. Of course, the best case is 7 because you can verify they are ordered in 7 steps: $1<2<3$, $3<4<5$, $5<6<7$, $7<8<9$, $9<10<11$, $11<12<13$, $13<14<15$. But that's not the interesting side. $\endgroup$
    – yo'
    Commented Aug 23, 2016 at 15:18
  • 1
    $\begingroup$ @ABcDexter You should IMHO take the ceil, not the floor, i.e., it shall be 16. $\endgroup$
    – yo'
    Commented Aug 23, 2016 at 15:19
  • 1
    $\begingroup$ Well, simply put: you can't sort 2 balls in $\lfloor\log_6(2!)\rfloor=0$ measurements ;-) The rule says that the information obtained from $n$ measurements is surely (non-strictly) less than $n\,\mathrm{sit}$ ($1\,\mathrm{sit} = \log_2 6\,\mathrm{bit}$), i.e., $n\geq \log_6 15!$. $\endgroup$
    – yo'
    Commented Aug 23, 2016 at 18:12
4
$\begingroup$

I found a an interesting article about that 15 balls article. Acording to this source,

we need a 20 weightings to sort the 15 balls.

They are unable to proove it is the minimum possible number. But they say 16 is a proven lower bound. I won't within the details of all demonstation but just show the main results and the final demonstration.

Firstly they proove the minimum weighting for number of balls up to 9.

3 weighings suffice to sort 4 marbles.
4 weighings suffice to sort 5 marbles.
5 weighings suffice to sort 6 marbles.
6 weighings suffice to sort 7 marbles.
8 weighings suffice to sort 8 marbles. 9 weighings suffice to sort 9 marbles.

Then, they go on the 15 balls problem with this set of intermediate demonstation

Lemma1: 4 weighings suffice to sort six marbles containing two disjoint chains of length 2.
Lemma2: 5 weighings suffice to sort seven marbles containing three disjoint chains of length 2.
Lemma3: 13 weighings suffice to sort 15 marbles ordered as presented there:
15 marbles
Lemma4: 6 weighings suffice to sort eight marbles ordered as presented there:
8 marbles
Lemma5: 12 weighings suffice to sort 15 marbles as presented there:
15 marbles

Final proof using all theorems:

20 weighings suffice to sort 15 marbles.

Partition the 15 marbles into five groups of three, and weigh them. Use a sixth weighing to compare the middle marbles of three groups, and let a denote the middle one. The following graph illustrates the situation.
enter image description here
Use a seventh weighing to compare a,b and c. Without any loss in generality, assume that b is heavier than c . Three cases need to be considered.

Case 1: a is the middle marble of the seventh weighing.
The marble b is heavier than a , and c is lighter than a . The situation is exactly that of Lemma3, and therefore 13 additional weighings suffice for a total of xx.
enter image description here

Case 2: a is the heaviest marble of the seventh weighing.
With an eighth weighing, compare the three shaded marbles. Since these three marbles are lighter than a , the resulting graph is exactly that of Lemma 5, and 12 additional weighings suffice, for a grand total of xx.
enter image description here

Case 3: a is the lightest marble.
The situation is isomorphic to the previous one, where the roles of heaviest and lightest are reversed.

Improve this answer
$\endgroup$
1
$\begingroup$

I believe the answer is

55

because

Arbitrarily choose the first three balls and determine their weights. This operation costs one weight, and we now know where they are in comparison to each other. For the sake of example, call them A, B, and C such that A < B < C. Now we introduce a fourth ball, D. Compare D with A and B. If it is the smaller than or in between A and B, we know its exact location. If not, we must compare it with C to see if it is smaller or larger. This costs two additional operations. Say we now have A < B < C < D. When introducing E, following the same process will yield another two operations (compare to A and B, if that doesn't help, then compare to C and D). Introduce a new ball, follow the same process, this will now cost us three operations. The patterns of required operations to determine the new ball's location is as follows: 1, 2, 2, 3, 3, 4, 4, 5, 5, etc. This yields: 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 + 7 = 55 for 15 balls.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think this is the strict upper bound. (forming k-combinations from set of 15 unlabeled elements, with k=2.) $\endgroup$
    – ABcDexter
    Commented Aug 22, 2016 at 19:53
  • $\begingroup$ Yes, if using this strategy, this is the maximum number of operations we would need to do, which would also be the minimum to ensure that we'll be able to order everything correctly. That being said, my answer anyway got beaten out by everyone else :) $\endgroup$
    – Kiwi
    Commented Aug 22, 2016 at 20:09
  • $\begingroup$ I think the upper bound is far less than 55. $\endgroup$
    – Tony Ennis
    Commented Aug 23, 2016 at 5:35
1
$\begingroup$

My answer do not give exact numbers of weighting, but nice algorithm to attack the problem.

Take a ball as pivot, like A, than, weight all remaining ball with A.
You will get a group of 3 [balls lighter than A] , [A] , [balls heavier than A].

than

Now from balls lighter than A do the same algorithm.
Also do the same algorithm with balls heavier than A.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is known as Quick sort with worst case complexity O($N^2$) $\endgroup$
    – ABcDexter
    Commented Aug 24, 2016 at 10:55

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