Subscribe via feed.

Three-tray scale

Posted by Zorglub on April 5, 2012 – 7:56 pm

There are 15 marbles with different colors. Their weight are all different, but the only way to rank them is by using a three-tray scale. The scale accepts exactly 3 marbles, one in each tray, and only indicates which of the three weighs the most, the least and consequently the one in between.
What is the least number of weighings necessary to rank the 15 marbles from lightest to heaviest ?

P.S. I have a strategy that ranks the 15 marbles, but I do not have a proof that no strategy can ensure it with fewer weighings.


This post is under “SharedPuzzle” and has 38 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

38 Responds so far- Add one»

  1. 1. Wizard of Oz Said:

    Weigh any three marbles and line up the others.
    Put aside the middle-weighing one, replace it with the next in line and weigh again.
    Repeat this process, discarding the middle-weighing one each time until all marbles have been weighed in this manner.
    After 13 such weighings we have the heaviest and lightest of the marbles plus 13 others.
    Repeat this process with the remaining 13 marbles to get the second heaviest and second lightest after 11 weighings.
    Continue this process until one final weighing is needed to rank the 7th, 8th and 9th marbles.
    Total number of weighings = 13+11+9+7+5+3+1 = 49.
    I’m sure someone will come up with a smarter way than this!

  2. 2. cazayoux Said:

    I’ve got a method that requires 30 weighings.
    In a meeting at the moment. I will expound in a bit.

  3. 3. cazayoux Said:

    uhh … might be only 25 weighings. (one less iteration)
    Need to verify before I post.

  4. 4. cazayoux Said:

    Consider 15 marbles: ABCDE FGHIJ KLMNO and three scales: XYZ.
    Let us assume as an example that A is the heaviest through O being the lightest.
    We measure ABC, DEF, GHI, JKL, MNO and make three piles: heavy, mid, light
    The heavy pile has ADGJM, mid has BEHKN, light has CFILO.
    Repeat by distributing to the three scales starting with heavy, mid, then light
    next five weighings are ADG, JMB, EHK, NCF, ILO
    and again we separate into three piles of heavy, mid, light
    The heavy pile has AJENI, mid has DMHCL, light has GBKFO.
    I’ve represented 2 iterations of weighing and sorting.
    With 5 iterations we recover the order of heaviest to lightest ABCDEFGHIJKLMNO.

    ABC
    DEF
    GHI
    JKL
    MNO

    ADG
    JMB
    EHK
    NCF
    ILO

    AJE
    NID
    MHC
    LGB
    KFO

    ANM
    LKJ
    IHG
    FED
    CBO

    ALI
    FCN
    KHE
    BMJ
    GDO

    These 25 measurements give us the following weight order of ABCDE FGHIJ KLMNO

    AFK
    BGL
    CHM
    DIN
    EJO

  5. 5. cazayoux Said:

    okay … may have been too quick on the trigger.
    still working…

  6. 6. DP Said:

    I’m glad you say that. In an effort to prove your method, I was trying it out myself by randomly assigning “weights” 1 through 15 to marbles A through O. I’m up to 9 itertions and it isn’t looking good. Getting closer, but not close enough.

  7. 7. DP Said:

    @ Wiz…is there a way you could even reduce the number of weighings more? Such as make 3 piles from the “discarded” marbles in the first round. Let’s say you remove the middle-weight, and replace it with one that is lighter than the 2 currently on the scale. The now middle-weight used to be the light one, so can we call it “lighter than the previously removed marble” and stick it in a light-middle-weight pile? Same with the heavy ones…
    Maybe it doens’t garantee anything, because you may have “randomly” selected the Heaviest and Lightest to start with, so the remaining comparitor marbles are all middle-weights.

  8. 8. cazayoux Said:

    :) I have a max 25 weighings (could be less) strategy.

    since we have 3 trays, I want to order three groups of 5 marbles.

    I can take any 5 marbles and get their weight order within 4 weighings.

    ABC, as Wiz suggested replace the middle with another.
    ACD
    ADE
    These three weighings would give the heaviest and lightest
    BCD
    This fourth weighing gives us the order of the middle three
    So we know the order from heaviest to lightest is ABCDE.

    Do the same for another group of 5 and then the last five.
    This is 12 weighings so far.

    So we have 3 groups of five marbles, and in each group we have the weight order.

    Now weigh the heaviest of the three groups.
    This is our heaviest overall

    Now weigh the heaviest of the three groups.
    This is our next heaviest overall.

    Continue until, at worst, you have one remaining from each of the three groups. Ths scale gives us the lightest three in order.

    This is, at most, 13 more weighings.

  9. 9. cazayoux Said:

    Okay … more than 15 minutes have passed and I’m still happy with my last post (#8).

    It showed 12 + 13 = 25 max weighings necessary.

    It could be less if we get lucky.
    The worst case is if we deplete the three groups evenly.
    It’s possible though that one group of five marbles is depleted well before the others.

    At this time we would weigh two marbles from one group and one marble from another group. This could result in knowing the next 1 or 2 heaviest marbles.

    Once the second group of five is depleted, no more weighings are necessary since we already know the order within each group.

    If by chance, group 1 has the five heaviest, group 2 has the middle, and group 3 has the five lightest, only 7 weighings are needed after the in-order is determined. (for a total of 19 weighings)

    In final, the strategy will provide the order of weight in 19 to 25 weighings.

    Now … for Chris … what is the probability that 19 weighings are required? 20? … 25?

    Happy Easter!

    michel

  10. 10. Zorglub Said:

    Cazayoux,

    your strategy is very close to mine. However, there is a way to slightly improve it by one. Look closely at the first half of your process.

  11. 11. cazayoux Said:

    :) Zorglub … mentally wrestling to see how to get the order of a group of five in less than four weighings, but coming up empty. I’m still trying, though.

  12. 12. cazayoux Said:

    I think I can get the weight order of five marbles in three weighings 6/10ths of the time.

    consider five marbles of unknown weight: Red, Orange, Yellow, Blue, Green

    I pick any three to weigh.
    Red – Orange – Yellow (Red is heaviest, Yellow is lightest)

    Weight the remaining two with the middle (Orange).
    Following heaviest to lightest, there are three possibilities for where Orange ends up.

    If Orange is lighter than Blue and Green, we know the two lightest are Orange and Yellow. We only need to weigh Red, Green, and Blue to get the order of the three heaviest.

    If Orange is heavier than Blue and Green, we know the two heaviest are Red and Orange. We only need to weigh Yellow, Green, and Blue to get the order of the three lightest.

    That’s only three weighings for these two situations.

    However, if Orange is in the middle again, we need one more weighing between the two that are heavier than orange and one more weighing between the two that are lighter than orange.

    This means four weighings for this last scenario.

    There are 10 ways to start with three marbles out of five for the first weighing. Four of these ten require a fourth weighing.

    There’s no guarantee, but it’s possible that to order each of the three groups of five marbles can be done in as few as 9 weighings. Worst case is still 12 weighings, though, with this approach.

    If we are lucky, this means a minimum of 9 + 7 = 16 weighings and a maximum of 12 + 13 = 25 weighings for me.

    Now I wonder if my four-weighing scenarios actually allow me to learn something about a marble from another group that might lessen my need for stage two and reduce that 13 weighings.

  13. 13. Zorglub Said:

    You are right about this:

    > cazayoux wrote:
    > Now I wonder if my four-weighing scenarios actually allow me to learn
    > something about a marble from another group that might lessen my need
    > for stage two and reduce that 13 weighings.

    While sorting the three groups, you can get additional information.

  14. 14. cazayoux Said:

    I was playing on the whiteboard a little more yesterday.
    (Conference calls allow for much fiddling on the whiteboard)

    There are scenarios in which I can come up with the order of 7 marbles in 5 weighing, but still need to figure out how helpful it is to introduce additional marbles in other scenarios.

    So I’m not sure, yet, how to quantify the additional information I can get from those ‘four-weighing’ scenarios while I order a group of 5 marbles.

    I’m anxious to see your solution.

  15. 15. Zorglub Said:

    Given a group of 5 marbles, weigh three of them and denote the lightest one a1, and the middle one a2. Weigh the heaviest of the three with the remaining two, and denote the lightest one a3, the middle one a4 and the heaviest a5. At this point, we are certain that the heaviest of the five marbles is a5. The lightest is either a1 or a3.

    Do the same operations to the second and third groups of 5 marbles. We have

    a1 or a3 is the lightest and a5 the heaviest of group A
    b1 or b3 is the lightest and b5 the heaviest of group B
    c1 or c3 is the lightest and c5 the heaviest of group C

    Up to now, we used the scale 6 times.

    The trick is to use the scale six more times to order the marbles inside their group, but to detect the overall lightest while doing that.

    Weigh a1-a3-a5 and call the lightest d0.
    Weigh the heaviest of a1-a3 with a2 and a4, and this gives you an ordering for all the marbles of group A.

    Now, weigh d0-b1-b3 and call the lightest e0.
    Notice that e0 is the lightest of the union of groups A and B.
    Weigh the heaviest of b1-b3 with b2 and b4, and this gives you an ordering for all the marbles of group B.

    Finally, weigh e0-c1-c3 and call the lightest f0.
    Notice that f0 is the lightest of the union of the three groups.
    Weigh the heaviest of c1-c3 with c2 and c4, and this gives you an ordering for all the marbles of group C.

    Therefore, after 12 weighings, we have sorted three groups of five disjoint marbles, and have identified the overall lightest.

    Now, move on to the second stage of the process where you iteratively weigh the lightest of each group. With 12 additional weighings you order the entire list.

  16. 16. cazayoux Said:

    I like it! … I was focusing on the mid-weight object. Your focus on the lightest allows a more meaningful use of that extra spot on that third weighing.

    Your method requires a definite 12 weighings for ordering the groups of five marbles (stage 1), but saves you one weighing in the second stage.

    With my method there was a 6/10ths chance that a group of 5 needs only 3 weighings. (10.2 weighings for the three groups of 5)

    So there is a chance of 9 weighings in stage 1 which means up to 13 weighings for stage 2.

    Want to play with the probabilities for stage 1 requiring less than 12 weighings.
    It will require that I shift my focus to lightest or heaviest rather than mid to take advantage of that possible extra space.

    Thanks!

  17. 17. slavy Said:

    In general I am not that good with such kind of problems (I tend to overestimate the answers and include unnecessary steps), so I will be careful here and not give any quick answer. However, definitely the strategy above cannot be optimal and the answer should be less than 24!

    Why do I think so? First of all, let us argue about what is special in 15. 15=2^4-1, hence is 1111 as dyadic number. The beauty of the latter is that we have a marble of middle weight, each of the two ¨heavy¨ and ¨light¨ groups themselves has a ¨middle-weighed¨ marble, and each of the new 4 groups has again a middle-weighed marble. Thus, I believe the strategy should be in finding the middle-weighed marble among the 15 given marbles. This will automatically split our marbles into 2 ¨disjoint¨ groups of 7 marbles, where by disjoint I mean that every marble from one of the groups is within the same relation with every marble of the other group. Now, the problem is broken into two independent sub-problems of the same type – order 7 marbles, in stead of 15. Again, by using the ¨middle¨ strategy one can show that 6 weighings are enough for the sub-problem, meaning that if we need X weighs for finding the middle element of the original 15-marble problem, the overall answer is at most X+2*6=X+12 I highly doubt that X is 12! And even if in the worse-case-scenario it is indeed 12, then we have some additional information about the sub-problems and we will not need all the 6 measurements there…

    Last remark: in my opinion an important observation is that in the case of 5 marbles, you can either find the middle one after two measurements, or (if you fail) you completely order all the 5 marbles (not simply find the middle one!) in 3 steps.

  18. 18. cazayoux Said:

    Help me to better understand.
    I can appreciate that 15 is special as it is in the series for 2x[n-1]+1: 1,3,7,15,31… (2^x-1).
    x[n-1] is the iterative
    x0=1
    x1=2(x0)+1 = 3
    x2=2(x1)+1 = 7
    x3=2(x2)+1 = 15 … didn’t really know how to show this simply :)

    I do not see an efficient way to determine the middle of the 15. It really is hit or miss. It seems the best way to find the middle marble is to order all 15.

    It’s more significant to me that 15 is divisible by three and we are using a three-tray scale.
    So the strategy is to set up for stage 2.

    Zorglub’s method requires 12 weighings in stage 1, which reduces stage 2 weighing by at least one. (possibly more since we do have another proper weight order for one marble from two different groups)

    My original method for ordering 5 marbles (keeping the middle marble of first weighing) had a 6/10ths chance of using three weighings and a 4/10ths chance of using four weighings.
    [3(6/10) + 4(4/10)] * 3 = 10.2 average weighings for stage 1.
    The four-weighing scenarios offer opportunity for additional information that may reduce stage 2.

    I reworked my original method to keep the heaviest and found there is a 1/10th chance that only 2 weighings are needed, 3/10ths chance that 3 weighings, and a 6/10ths chance that 4 weighings are needed.
    [2(1/10) + 3(3/10) + 4(6/10)] * 3 = average 10.5 weighings for stage 1.
    The four-weighing scenarios offer opportunity for additional information that may reduce stage 2.
    There are more chances for a four-weighing scenario in this method, but a cost of 0.3 weighings.

    I still need to quantify the value of having that extra bit of information.
    Consider three groups ABCDE, FGHIJ, KLMNO and I know the order of each group of five.
    It is only a chance that knowing D is heavier than N is useful to me and could possibly save me one stage 2 weighing.

  19. 19. cazayoux Said:

    I wanted to show the scenarios for ordering 5 marbles.
    ABCDE in order where A is the heaviest and E is the lightest.
    There are 10 ways to select three of these for the first weighing.

    Each column is a weighing.
    The order of the three marbles show the heaviest on the left, lightest on the right … but you know the order already: ABCDE.

    ‘x’ or ‘y’ is a marble from another group of five marbles.

    Method 1 – Keep the heaviest (same result for keeping lightest)
    ABC – ADE – BDx – CDE
    ABD – ACE – BCx – CDE
    ABE – ACD – BCx – CDE
    ACD – ABE – BCx – CDE
    ACE – ABD – BCx – CDE
    ADE – ABC – BDx – CDE
    BCD – ABE – CDE
    BCE – ABD – CDE
    BDE – ABC – CDE
    CDE – ABC

    6 require four weighings (but provide one bit of info)
    3 require three weighings
    1 requires two weighings

    Method 2 – Keep the middle
    ABC – BDE – CDE
    ABD – BCE – CDE
    ABE – BCD – CDE
    ACD – BCE – ABx – DEy
    ACE – BCD – ABx – DEy
    ADE – BCD – CDE
    BCD – ACE – ABx – DEy
    BCE – ACD – ABx – DEy
    BDE – ACD – CDE
    CDE – ABD – CDE

    4 require four weighings (but provide two bits of info)
    6 require three weighings

  20. 20. slavy Said:

    The benefit of estimating (and thus working with) the middles is that each weighing gives you information in two directions. Plus, for each measurement you have 3 possibilities: one of the three measured marbles is the middle one – intuitively such information is very helpful for the localization of the latter; all three of them are either bigger or smaller than the middle – then this measurement will be used after finding the middle one as one of the necessary measurements in the corresponding subgroup; two are bigger/smaller, and one is smaller/bigger – this again helps localizing the middle one. I expect the answer to be around 20 (possibly even less!).

    Let me illustrate the technique on one very special partial case: I will use the notation (a,b,c) for a measured triple if the relation a<b<c is satisfied. Moreover, I will use digits for the marbles, not letters.

    First 7 measurements of the strategy are "global", i.e., do not depend much on the outcome. Split the marbles into 5 disjoint triples and measure each of them: (1,2,3) (4,5,6) (7,8,9) (10,11,12) (13,14,15). Now we want to find the middle of the 5 middles. We compare three of them. Since everything so far is symmetric and equivalent after re-numeration, w.l.o.g let (2,5,8). Now we take the middle of the middles and compare it to the remaining two middles. There are two options the same middle lies in the middle of the next triple, as well (again w.l.o.g. let (11,5,14)) or it does not (again w.l.o.g. (11,14,5)). The first case already gives us that 1 is lighter than 8 marbles {2,3,5,6,8,9,14,15}, so it cannot be the middle one. Analogously for 10, and reciprocally for 9 and 15. Now we measure 3,4, and 12. If 4 is the heaviest, i.e., (3,12,4) then automatically 2,3,11,6,8,14 cannot be the middle one (I leave the argument as a homework), and thus we are left with only 5 candidates {4,5,7,12,13} with the additional information that (12,4,5). Moreover, we know that all 1,2,3 are lighter than the middle one, so our first measurement (1,2,3) will be used for ordering the lighter group, i.e., was not in vain. Now we compare 4,7, and 13. If 4 is again in the middle, i.e., (7,4,13) then 4 is lighter than 7 marbles and heavier than 7 marbles, thus it is in the middle. Moreover, the lighter group is {1,2,3,10,11,12,7), while the heavier group is (5,8,9,13,14,15,6). So after only 9 measurements we know the middle one, we have two ordered triples in both the groups ((1,2,3) and (10,11,12) in the first one, and (5,8,9) and (13,14,15) in the second one), plus additional information ((3,12) in the lighter group, and (5,6), and (5,14) in the heavier one). Even without using the additional information, we need only 4 extra measurements in each subgroup (2 to find the middle, and 2 to order the heavier, respectively the lighter triple). Hence in total we are done with only 17 measurements (as I said maybe we can decrease the number even more, if we use the additional info)! Of course, this was a relatively easy case, but the others are not much more complicated. It just needs more time and concentration. If I have the time to work on it tomorrow, I will post more…

  21. 21. Zorglub Said:

    Slavy,

    this seems like a promising approach. I am looking forward to see the complete analysis.

    For sure, there are no strategy that require fewer than 16 measurements in the worst case scenario. The reason is that there are 15! ways to arrange the marbles. Each measurement distinguishes at most 3! = 6 cases.

    The justification is that the smallest integer number p such that 6^p > 15! is 16.

  22. 22. slavy Said:

    Hi Zorglub,

    thanks for the computation! I try to avoid the use of computer in my solutions, and I gave up on finding that lower bound :) As I said before, I expect something within the range of 19-21, but analyzing step by step is extremely slow, ugly, and dumb :( Unless the problem was posted by a person who didn´t know the solution in advance, there should be some more structural/theoretical approach. My first also involved permutations. Namely the fact from Algebra that every permutation can be represented as a product of cycles of length 3. But even if I find the overall minimal number of multiples required for the representation of every permutation of 1-15, I still don´t see how to relate the latter to our problem. Moreover, I´m not quite sure that we can prove that 16 is a lower bound, because our measurements are not independent of each other, and weighing 3 marbles usually gives us also additional information regarding the total order, not only the relation between the 3 involved marbles. For example, if we were extremely lucky and the order was (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15), then after the following 9 scalings (1,2,3), (4,5,6), (7,8,9), (10,11,12), (13,14,15), (3,4), (6,7), (9,10), (12,13) we are done, meaning that not always at least 16 measurements are needed.

    My second idea was the ¨dyadic approach¨, since I still claim that 15 being 1111 should be the key for our strategy. The ¨triadic approach¨ also seems promising, but so far I have nothing in these directions…

    I hope there is some elegant idea/solution and I´m trying to find it. If brute force is the main weapon, then I´m not interested in the problem. Hence what I said in my previous post about ¨time and concentration¨ is not exactly true – I do not plan to attack the problem case by case and after 30 pages of careful computations to claim some number! The latter means that probably I will not publish an answer or a solution soon, since so far I lack ideas how to proceed. However, I strongly believe in the optimality of the proposed strategy, so if somebody wants to take the ¨brute force¨ way – be my guest :)

  23. 23. Zorglub Said:

    Slavy,

    when stating that 16 is a valid lower bound for a strategy, I mean it in the worst case. This signifies that there is a permutation of the marbles that would require at least 16 measurements with that strategy. This does not imply that all permutations require at least 16 scalings.

    The bound 16 is valid, because there are 15! possibilities, and each measurement has 6 possible outcomes. Using a simple calculator gives log(15!) / log(6) = 15.57 as a valid bound. Rounding this number gives 16.

    I agree that sometimes fewer are possible. In your example with (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15) the seven measurements (1,2,3), (3,4,5), (5,6,7), (7,8,9), (9,10,11), (11,12,13), (13,14,15) suffice.

    I also hope that there is an elegant solution to this problem, that does not require brute force. In summary, up to now we have a strategy that requires at most 24 measurements, and we know that no strategy can guarantee less than 16. To make progress we can either derive some arguments to increase the lower bound, or find another strategy that requires fewer than 24. The problem will be solved when both values will be equal.

  24. 24. Wizard of Oz Said:

    Out here in the real world, is there such a thing as a three tray scale? If so, how does it work?

  25. 25. slavy Said:

    OK, I have already spent too much time and efforts on this problem, so let me “report” on my results and leave the others work further.

    The more I think the more certain I become that the problem is actually not pure mathematical, but rather a programming one. And my stubbornness to write routines (as well as my lack of expertise in computational math) stops my progress. What do I mean? The fastest (most efficient) way to sort or work with sorted data is to introduce a binary-tree-structure on it. Let the 15 marbles are numbered with respect to their weight, i.e., 1 is the lightest and 15 is the heaviest:

    8
    4 12
    2 6 10 14
    1 3 5 7 9 11 13 15

    Apart from the linear structure (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15), we also have a balanced binary tree with root 8, children 4 and 12 and so on, as sketched above. For each node, all the nodes in its left sub-tree as lighter, while all the nodes in its right sub-tree are heavier. This structure is compatible with the linear one, since (as we know from the lectures in informatics) if you read the tree in left-root-right fashion you will get exactly the sorted data.

    Our three-tray scale favors the tree structure, because we are able to quickly split the data between the corresponding sub-trees, whenever the root is known. More precisely, assume the information that 8 has the middle weight was given to us a priori. Then after 7 weightings (always using 8 and two other marbles) we completely determine the “lighter” and the “heavier” sub-trees, and split the problem into two identical sub-problems that involve 7 marbles each.

    Now, let’s look in detail the 7-marble-problem. Again, if we had known its root, we would have needed 3 weightings to determine the lighter and the heavier triple, respectively and 2 additional weightings to sort them. In other words – 5 weightings overall. But we don’t have such information and therefore we need to derive it ourselves. This costs us one additional measurement. A possible way to order 7 marbles with 6 weightings is the following:

    ABC, DEF. Take (B,E,G). Up to symmetry there are two main cases: Case 1 – G is with middle weight, i.e., BGE. Then A,B,E,F can not be the root, and weighting the remaining (C,D,G) will give us the answer. Moreover, note that finding the root goes together with separating the marbles into the corresponding two sub-trees! Thus we need only the two additional scalings to order those sub-trees. Overall – 6 weightings. Case 2 – G is not the middle one, e.g., BEG. Again, A,B,F,G cannot be the root and comparing (C,D,E) will give us the root and the two sub-trees. Overall – 6 weightings…

    to be continued

  26. 26. slavy Said:

    I propose the following algorithm (which I hope somebody will implement and report on):

    Create a list with 15 elements of type “marble”, and let each Object has two parameters, i.e., marble(listMarble L, listMarble H), denoting the lighter, respectively heavier marbles in the list.

    Upon initialization, L=H=Empty_list for all marbles.

    In the class marble we have two functions sum = length(L)+length(H) and diff = |length(L)-length(H)|.

    One step of the algorithm: order the marbles ascendingly with respect to their diff value; in case of several marbles with equal diff value, order them with respect to their sum value, again ascendingly. Take the top 3 marbles in the list and weight them. Update the L,H, sum, and diff cells of all the marbles, according to the output of the weighting.

    Such an algorithm guarantees that we work with nodes, as close to the root as possible. Moreover, the first marble to reach sum=14 (i.e., we have compared that marble with all the others) will be exactly the root! Hence, we will automatically have its left and right sub-trees. Once we have the root, we split the list into two, update the cells of the object (for any marble in the left-sub-tree we delete from L and H all the marbles from the right-sub-tree, and re-evaluate sum and diff. Vice versa for the marbles from the right-sub-tree), and apply the same algorithm to the left and the right branch independently. And so on…

    Now take all the 15! possible orderings/permutations (if using symmetries this number can be significantly decreased!) and run the algorithm for each of them. What is the maximal number of weightings that you had to use? From the previous post we see that even knowing the root of the tree a priori, we still need 7+2*6=19 weightings to sort it (7 for finding the sub-trees and 6 for solving the 7-marble problem for each of them). Hence, 19 is a lower bound for the answer! From the cases 3 and 7 (the other balanced binary trees of less elements), we see that the 3-marble problem needs 1 weighting (with lower bound 1), the 7-marble problem needs 6 weightings (with lower bound 5), so a totally wild guess is that the 15-marble problem will need 21 weightings (since the lower bound is 19)…

    As I said before – I am not experienced enough in sorting algorithms, so maybe there is something simpler and faster than my proposal. If so, please let me know, so that I learn something :) If you don’t know other algorithms and you have time to waste, try the one above – I hope I wrote it in the most “algorithmic” way so that you can program it pretty fast.

  27. 27. mo Said:

    I’ve come up with a method that never takes more than 22 weighings, although in testing I’ve never needed more than 21 weighings (it usually gets you there in 18 or 19). It may be possible to prove that a weighing becomes redundant somewhere near the end.

    Here’s how it goes:

    Weighings 1-5:
    Divide the marbles into five groups of 3 and weigh each of them, noting the results.

    1l 1m 1h
    2l 2m 2h
    3l 3m 3h
    4l 4m 4h
    5l 5m 5h

    Weighing 6:
    Weigh any three of the heaviest of their groups, note results.

    1h 2h 3h -> 6l 6m 6h

    Weighing 7:
    Weigh the heaviest of the last weighing with the two other heaviest of their groups.

    6h 4h 5h -> 7l 7m 7h

    7h is the heaviest marble overall.

    Weighing 8:
    Weigh the middle marble of the group the heaviest marble was in with the middle marbles of weighings 6 and 7.

    e.g 1m 6m 7m -> 8l 8m 8h

    8h is the second heaviest marble overall.

    Weighing 9:
    Check weighings 6 and 7 to see if the heaviest and second heaviest marbles where in direct comparison. If so, pick the third marble out of that weighing, otherwise pick any marble you like. Weigh it with the next heaviest marble of the group the second heaviest marble was in and the middle marble of weighing 8.

    e.g. 6l 2m 8m -> 9l 9m 9h

    9h is the third heaviest marble overall.

    Weighings 10-13:
    Repeat steps 6-9 with the three heaviest marbles put aside. This will establish the next three heaviest marbles. (It may take less than 4 steps due to information retrieved from steps 6-9.)

    Weighings 14-21:
    Repeat steps 6-13 from the lighter side working up. This will establish the six lightest marbles. (It probably won’t take 8 weighings to do this due to information retrieved from steps 6-13.)

    Weighing 22:
    If the remaining 3 marbles haven’t fallen into place already, weigh them. They are the 7th, 8th and 9th heaviest marbles. We’re done.

    I’ve thrown a quick weighing simulator together where this and other methods can be tested:
    http://mozone.bugs3.com/misc/marbles.php
    It looks crap and has a few bugs, but it kind of does the job. Don’t look at the code, it’s embarrassing :)

  28. 28. slavy Said:

    Great job, Mo! Nice and simple algorithm with close-to-optimal result! I never thought that such a strategy may be that good. For 6,7, and 9 marbles (if I am not mistaken) your algorithm always uses only one extra weighing (6,7, and 10 weighings for optimal 5,6, and 9, respectively). This in some sick non-mathematical way backs up my expectation for the answer to be in the range 19-21 :)

  29. 29. Zorglub Said:

    Mo, I am impressed by your solution and by your simulator. Your strategy is very efficient.

    Slavy, you mention that the problem with 7 marbles can be done in 6 weighings. I cannot do better than 7 weighings, but I can prove that 5 is not enough. Can you describe how you do it ?

  30. 30. slavy Said:

    Zorglub, I have sketched the solution of the 7-marble problem in the last paragraph of post #25. The general algorithm that I propose in the next post is based on that solution, so if my explicit explanations are not good enough, you may try to manually “execute” the algorithm. Let me know if you need a more detailed post.

  31. 31. Zorglub Said:

    I had missed the end of post 25. Sorry about that. No need to explain further it is perfectly clear.

    Combining this with the fact that 5 weighings is not necessarily sufficient for 7 marbles implies that your algorithm is the best that can be done.

    Proof by contradiction: Suppose that there is an algorithm that solves the 7 marble problems in 5 weighings. Notice that is a pair of marbles is placed twice on the scale (example testing ABC then ABD) then the second time will not be as useful as the first time. This would allow to discern only

    6^4 x 3 = 3888 possibilities which is less than 7!.

    Therefore any pair or marble is only tested once,

    5 weighings means that 15 marbles are tested, and at least one is tested 3 times. Let A be that marble. The first time is ABC. The second time cannot use B or C as it would test twice the same pair. Let ADE be the second and AFG be the third. The fourth weighing needs to be BDF so that no pair is tested twice, and similarly the fifth weighing needs to be CEG. There are no other option.

    With these 5 weighings, it is impossible to distinguish the orderings (A,B,C,D,E,F,G) and (A,B,D,C,E,F,G). Contradiction

  32. 32. Zorglub Said:

    A recent paper in The Mathematical Gazette shows that 20 weighings is enough:

    https://www.dropbox.com/s/gjyvq2d7pub3vah/15billes.pdf

  33. 33. slavy Said:

    Thanks for the info, Zorglub! I’ll have a look at it :)

  34. 34. slavy Said:

    The paper is interesting! However, I already said that the minimal number of moves is 19 and I’m standing on my words. 20 is the number I expected, but this was not mentioned in the article. I’m thankful to know where I can publish such results, so, as long as I have free time to kill, I can work on my theory and finally prove the optimality of the result :)

  35. 35. Zorglub Said:

    Slavy, you must be referring to posts 25 and 26. I agree that if you identify the middle marble, then an extra 2*6 weighing will do the trick. But can you rephrase how you get the middle marble in only 7 weighings ? I read several times these posts, but I don’t understand.

  36. 36. slavy Said:

    Zorglub, I’m just saying that 16 is a very low and unrealistic lower bound. Even if you know a priori the “root” you need 7 weightings to divide the remaining 14 marbles into lighter and heavier halves and then 2*6 weightings to sort them out. I don’t think I can find the root in those first 7 weightings. In the case for 7 marbles, knowing the root a priori leads to 5 weightings (3 to split the marbles into groups and 2*1 to sort them) but, as we saw we needed an extra one to determine it. Here, I also expect 20 to be the optimal number. But the paper and the results look stronger with 19 as a lower bound…

  37. 37. Zorglub Said:

    Slavy,

    I agree that a lower bound of 19 is much better than a lower bound of 16. However, I doubt that you argument is valid, unless I misunderstand it. My interpretation of your claim is that

    1- Every marble needs to be compared with the middle one to be ordered.

    2- Identifying the middle marble takes at least 7 weighings (at best, by comparing the middle one with all 7 other pairs).

    3- If we are lucky, there will be 7 heavy and 7 light marbles requiring each 6 weighings.

    Total 7 + 6 + 6 = 19

    ——–

    Lets apply the same reasoning to the case where we have 9 instead of 15 marbles.

    1- Every marble needs to be compared with the middle one to be ordered.

    2- Identifying the middle marble takes at least 4 weighings (at best, by comparing the middle one with all 4 other pairs).

    3- If we are lucky, there will be 4 heavy and 4 light marbles requiring each 3 weighings.

    Total 4 + 3 + 3 = 10

    However, 9 marbles can always be sorted using 9 weighings… Contradiction.

  38. 38. slavy Said:

    15 marbles (2^4-1) give rise to a complete balanced tree (post 25). To sort such an array the quickest way is to find its root and the corresponding subtrees (which, again, are balanced) and so on. The case of 9 marbles is totally different and there such a strategy is not optimal.

    After the case of 15 – the next interesting case is n=31. There, it will be interesting to see if the pattern remains, and one can sort it out with 15+1+2*20=56 weightings

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0