Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. 26 Jan '05 06:47 / 4 edits
    All RHP -ers are familiar with the classic '12 Marbles puzzle', in which one has to detect and find the odd one out of the 12 identical looking marbles (out of which only one is slightly different in weight) , by using a balance only 3 times. Most RHP-ers can solve it easily. In the 12 marbles puzzle , you can not only locate the odd one out , but also you can definitely tell whether the odd marble is heavier or lighter than the rest.

    This one is a slight upgradation. Now you have 13 marbles ,out of which only one is slightly different from others in weight. You have to locate the odd- man- out by using a balance only thrice.
  2. 26 Jan '05 08:59
    Is the odd marble heavier or lighter?
  3. Standard member TheMaster37
    Kupikupopo!
    26 Jan '05 10:18
    Originally posted by yevgenip
    Is the odd marble heavier or lighter?
    You don't need to know:

    name the marbles 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13.

    First weigh 1, 2, 3, 4 against 5, 6, 7, 8 We can have three possible outcomes:

    = ; The odd marble is 9, 10, 11, 12 or 13. Weigh 1, 9 against 10, 11.
    We have again, three possibilities;
    = ; The odd one is among 12, 13. Weigh one of them with 1, If
    they're equal, 13 is the odd one, else 12 is the odd one and
    you can tell if it's lighter of heavier.
    < ; The odd one is among 9, 10, 11. Weigh 10 against 11. If
    they're equal 9 is lighter. If they're not equal then the odd
    marble is the heavier of the two.
    > ; The odd one is among 9, 10, 11. Weigh 10 against 11. If
    they're equal 9 is heavier. If they're not equal then the odd
    marble is the lighter of the two.

    For the cases < and > nothing changes from the 12 marble problem. I can post it if you want
  4. 26 Jan '05 13:03
    Originally posted by TheMaster37
    You don't need to know:

    name the marbles 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13.

    First weigh 1, 2, 3, 4 against 5, 6, 7, 8 We can have three possible outcomes:

    = ; The odd marble is 9, 10, 11, 12 or 13. Weigh 1, 9 against 10, 11.
    We have again, three possibilities;
    = ; The odd one is among 12, 13. Weigh one of them with 1, If ...[text shortened]...
    For the cases < and > nothing changes from the 12 marble problem. I can post it if you want
    Yes, that works. However, I think there is slight change from 12 marble problem though. In 12 marble problem you not only have to locate the odd one out , you also have to find out whether it is heavier or lighter than the others.

    In 13 marbles problem above, you only need to just locate the odd man out. In 13 marbles case , using 3 weighings, you cannot decide whether the odd one is heavier or lighter with certainty in every eventuality, which is possible in the 12 marbles case..
  5. 26 Jan '05 13:21 / 1 edit
    Originally posted by TheMaster37
    You don't need to know:

    name the marbles 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13.

    First weigh 1, 2, 3, 4 against 5, 6, 7, 8 We can have three possible outcomes:

    = ; The odd marble is 9, 10, 11, 12 or 13. Weigh 1, 9 against 1 ...[text shortened]... g changes from the 12 marble problem. I can post it if you want
    You get it. Show that 13 is the largest number of marbles from which one odd -man- out can be located using 3 weighings.

    Also show that , if 4 weighings are permitted, one odd marble out of as many as 40 marbles can be located. And 40 is the highest number for 4 weighings .With any number less than 40, you can also tell whether the odd marble is heavier or lighter than the rest of the lot.
  6. Standard member TheMaster37
    Kupikupopo!
    26 Jan '05 13:49
    Originally posted by neverB4chess
    Yes, that works. However, I think there is slight change from 12 marble problem though. In 12 marble problem you not only have to locate the odd one out , you also have to find out whether it is heavier or lighter than the others.

    In 13 marbles problem above, you only need to just locate the odd man ...[text shortened]... with certainty in every eventuality, which is possible in the 12 marbles case..
    No change whatsoever, the only case that you cannot determine the difference is when marble 13 is the odd one out. All other marbles are determined as i showed.

    Above procedure shows exactly wich marble is the odd one out, and if that marble gets number 1 through 12 you can also determine if it's heavier or lighter.
  7. Standard member TheMaster37
    Kupikupopo!
    26 Jan '05 13:52
    Originally posted by sarathian
    You get it. Show that 13 is the largest number of marbles from which one odd -man- out can be located using 3 weighings.

    Also show that , if 4 weighings are permitted, one odd marble out of as many as 40 marbles can be located. And 40 is the highest number for 4 weighings .With any number less ...[text shortened]... also tell whether the odd marble is heavier or lighter than the rest of the lot.
    Well, if you try above procedure with 14 marbles, there is a case in wich you cannot determine wich marble is the odd one out (namely first and second weighing equal). But that's no proof, I never tohught about proving general cases...I shall try, but promise no answer!
  8. Standard member The Plumber
    Leak-Proof
    26 Jan '05 18:07
    Originally posted by TheMaster37
    Well, if you try above procedure with 14 marbles, there is a case in wich you cannot determine wich marble is the odd one out (namely first and second weighing equal). But that's no proof, I never tohught about proving general cases...I shall try, but promise no answer!
    I suspect the sum of powers of 3 will be involved in your proof. I.e.:

    3^0 + 3^1 + 3^2 = 13
    3^0 + 3^1 + 3^2 + 3^3 = 40
  9. 27 Jan '05 06:28
    Originally posted by sarathian
    You get it. Show that 13 is the largest number of marbles from which one odd -man- out can be located using 3 weighings.

    Also show that , if 4 weighings are permitted, one odd marble out of as many as 40 marbles can be located. And 40 is the highest number for 4 weighings .With any number less ...[text shortened]... also tell whether the odd marble is heavier or lighter than the rest of the lot.
    I think , with 4 weighings , the maxikum number of marbles can at most be 37. With 40 marbles I don't see how one can do it in 4 weighings?
  10. 28 Jan '05 07:16 / 1 edit
    With 37 marbles, divide them in three groups X, Y, and Z containing 12, 12 and 13 marbles respectively. Let us number them X1,X2,.....,X12; Y1,Y2,.......,Y12; and Z1, Z2, ....,Z13. I would use these symbols for their respective weights too ,for convenience.
    FIRST BALANCING :-

    Weigh the 12 marbles X1+X2+.....+ X12 on LHS against the 12 marbles Y1+Y2+.....+Y12 on RHS.
    CASE (a1)If LHS=RHS ; then the odd one is in Group Z.
    Hence, in further 3 'weighings' , the odd one can be located as in
    the 13 Marbles problem (as shown by TheMaster37 above).


    CASE (b1)If not equal, without loss of generality, let X-side be the heavier one. Then
    SECOND BALANCING uder (b1) case:-

    Weigh (X1+X2+... +X8)+(Y1+Y2+Y3+Y4) on LHS against (X9+X10+X11+ X12)+(Z1+Z2+.....+Z8) on RHS.
    I now deal with the 3 sub-cases as below-
    (b11)LHS=RHS; (b12)LHS&gt;RHS;(b13)LHS&lt;RHS.
    CASE (b11) If LHS=RHS; then the odd one is among the 8 marbles Y5 to Y12 and is lighter than the remainig lot.
    THIRD BALANCING uder (b11) case:-

    Weigh ( Y5+Y6+Y7) on LHS against (Y8+Y9+Y10) on RHS &amp; examine the sub-cases (b111)LHS=RHS ;(b112)LHS not equal toRHS; .

    CASE (b111) If =; then the odd one is among the 2 marbles Y11, &amp; Y12. In FOURTH BALANCING, weigh Y11 against Y12. The lighter of the two(Y11 &amp; Y12) is the odd one out.
    In (b112) ; the odd marble is one of the 3 on the lighter side and can be located , in just one balancing.

    CASE (b12) LHS&gt;RHS implies that the odd one is one of the 8 Marbles from among X1 to X8 and is heavier than the rest. In further 2 balancing( weighing ) as above the culprit can be nabbed as in case(b11).
    Case (b13)LHS&lt;RHS implies that the odd one may be one of Y1, Y2, Y3 , Y4 if it is lighter, or it may be from among X9,X10,X11, X12 if it is heavier.
    THIRD BALANCING :- Weigh X9+X10+Y1 on LHS against X11+X12+Y2 on RHS. IfLHS =RHS; the culprit is one of the two Y3 or Y4 , and is lighter , and can be located by weighing them against each other. If LHS&gt;RHS, the odd one is one of the three- X9, X10 or Y2 and can be located by balancing X9 against X10. (X-group is the &quot; heavier possibility&quot; group and Y-group is the &quot;lighter possibility &quot; group)
    If LHS&lt;RHS then the odd one is one of Y1,X11 or X12. The odd one ,in this case, can be decided by weighing X11 against X12.

    Thus , the odd one from among 37 marbles is locatable in 4 weighings.
  11. 28 Jan '05 11:00
    Originally posted by CoolPlayer
    With 37 marbles, divide them in three groups X, Y, and Z containing 12, 12 and 13 marbles respectively. Let us number them X1,X2,.....,X12; Y1,Y2,.......,Y12; and Z1, Z2, ....,Z13. I would use these symbols for their respective weights too ,for convenience.
    FIRST BALANCING :-

    Weigh the 12 marbles X1+X2+.....+ X12 on LHS ...[text shortened]... hing X11 against X12.

    Thus , the odd one from among 37 marbles is locatable in 4 weighings.
    You are right. But 37 is not the maximum number of marbles for 4 weighings. I have found a method for locating the odd -man -out from among 39 marbles, by using the balance only 4 times..
  12. 28 Jan '05 17:06 / 1 edit
    Originally posted by The Plumber
    I suspect the sum of powers of 3 will be involved in your proof. I.e.:

    3^0 + 3^1 + 3^2 = 13
    3^0 + 3^1 + 3^2 + 3^3 = 40
    Is that a heuristic guess?

    Or do you have the proof of the actual underlying mathematical basis too? If yes please give the mathematical basis .
  13. 28 Jan '05 17:16
    Originally posted by ranjan sinha
    You are right. But 37 is not the maximum number of marbles for 4 weighings. I have found a method for locating the odd -man -out from among 39 marbles, by using the balance only 4 times..
    I can only say that even 39 is not the highest number of marbles for 4 weighings. The highest number of marbles with 4 times use of the balance, is 40.

    As Plumber has already hinted , there is a solid theoretical basis for that. One only has to decipher the mind boggling permutations and combinations of , and the numbers of , the different marbles to be chosen at the 4 different stages of the BALANCING act.
  14. Standard member The Plumber
    Leak-Proof
    28 Jan '05 22:43
    Originally posted by sarathian
    Is that a heuristic guess?

    Or do you have the proof of the actual underlying mathematical basis too? If yes please give the mathematical basis .
    &quot;I have discovered a truly remarkable proof which this margin is too small to contain.&quot;
  15. 29 Jan '05 07:39 / 1 edit
    Originally posted by sarathian
    I can only say that even 39 is not the highest number of marbles for 4 weighings. The highest number of marbles with 4 times use of the balance, is 40.

    As Plumber has already hinted , there is a soli ...[text shortened]... be chosen at the 4 different stages of the BALANCING act.
    Let me put forth my steps. Am I missing something? Where ?
    Let us have 4 boxes named U, E, H &amp; L , for keeping the marbles for the following different categories.
    (i)U-box - undecided; the odd marble may be in this group and it is not known whether it is heavier or lighter.
    (ii)E-box- for marbles with weight equal to the norm; The odd marble is decidedly not in this group.
    (iii)H-box- for marbles which may contain the odd marble if it is heavier.
    (iv)L-box- for marbles which may contain the odd marble if it is lighter .
    In the case of 39 marbles the initially contents of the boxes are-
    U- 39, E -0, H- 0, L-0.

    The contents of these boxes will change after each stage of balancing as a consequence of the inference of that weighing.
    First WEIGHING: (13 U marbles on LHS) &lt;-vs-&gt; (13 U marbles on RHS).
    Case( C1)LHS=RHS =&gt;U-13, E-26, H-0, L-0.
    (In this case the odd marble can be decided in next 3 weighings as in the 13-marbles puzzle).
    Case(C2)LHS.NE.RHS =&gt;U-0, E-13, H-13, L-13.
    Second WEIGHING: ( 9H+6L on LHS)&lt;-vs-&gt;(3H+12E onRHS).
    Case(C21)LHS=LHS=&gt;U-0, E-31, H-1, L-7.
    Third WEIGHING under C21: (3L on LHS)&lt;-vs-&gt;(3L on RHS).
    Case(C211)LHS=RHS=&gt;U-0, E-37, H-1, L-1. In one further weighing the odd one out of the H-1 &amp; L-1 can be decided.
    Case(C212)LHS.NE.RHS=&gt;U-0, E-35, H-0, L-4.In this case too, one additional weighing locates the odd one.
    Case (C22)LHS&gt;RHS=&gt;U-0, E-30, H-9, L-0.
    Third WEIGHING under C22: (3H on LHS)&lt;-vs-&gt;(3H on RHS).
    Case(C221)LHS=RHS=&gt;U-0, E-36, H-3, L-0(In next 1 weighing the odd one gets decided).
    Case(C222)LHS.NE.RHS=&gt;One of the 3 in the heavier side contains the odd one and can be decided in next weighing.
    Case(C23)LHS&lt;RHS=&gt;U-0, E-30, H-3, L-6.
    Third weighing under C23: (3L on LHS)&lt;-vs-&gt;(3L on RHS).
    Case (C231)LHS=RHS=&gt;U-0, E-36, H-3, L-0. And last 1 weighing locates the ghost.
    Case(C232)LHS.NE.RHS=&gt;One of the three on the lighter side contains the culprit and can be nabbed in 1 last weighing.

    This decides and locates the demonic odd marble out of 39. If there are 40 marbles containing an odd one , then after the first stage of weighing , in case C1 you will have U-14, E-26, L-0, H-0. And with 14 undecided category marbles, you cannot decide the odd one out in 3 weighings, as has been shown above by one poster above(TheMaster37).

    Am I missing something?