*** MOVED ***

NOTE: I have merged the contents of this blog with my web-site. I will not be updating this blog any more.

2006-08-14

Balancing Acts

You are given 8 billiards balls, numbered 1 to 8, identical in shape and size. All but one weigh exactly the same. The odd ball is either heavier or lighter than the others. Using just three weighings on an ordinary two-pan balance, find the odd ball out as well as whether it is heavier or lighter than the others.

If you solve the previous puzzle, solve the same problem for 12 billiards balls (instead of 8) while keeping the maximum weighings to just three. Yes, there is a solution for this puzzle - if you give up, you can find the solution here.

For the first puzzle (with just 8 billiards balls), here is my solution (obfuscated using rot-13):
  1. Xrrc onyyf ahzorerq 1, 2 naq 3 ba bar cna naq 4, 5 naq 6 ba gur bgure.
  2. Vs gurl onynapr, gurl ner nyy abezny naq bar bs 7 naq 8 vf gur bqq onyy. Jrvtu 7 ntnvafg 1.
  3. Vs gurl onynapr, 8 vf gur bqq onyy naq lbh pna svaq vgf bqqvgl ol jrvtuvat vg ntnvafg 1.
  4. Vs gurl qba'g onynapr, 7 vf gur bqq onyy naq lbh jvyy vzzrqvngryl xabj vs vg vf urnivre be yvtugre guna gur bguref.
  5. Vs gur onyyf qba'g onynapr va fgrc #1, bar cna jvyy tb qbja. Jvgubhg ybff bs trarenyvgl, nffhzr guvf vf gur bar pbagnvavat 1, 2 naq 3. Rvgure bar bs 1, 2 naq 3 vf urnivre guna gur bguref be bar bs 4, 5 naq 6 vf yvtugre guna gur bguref.
  6. Xrrc 1 naq 5 ba bar cna naq 4 naq 2 ba gur bgure. Xrrc 3 naq 6 nfvqr.
  7. Vs gurl onynapr, bar bs 3 naq 6 vf gur bqq onyy. Sebz fgrc #5, jr pna pbapyhqr gung rvgure 3 vf urnivre guna gur bguref be 6 vf yvtugre guna gur bguref. Jrvtu 3 ntnvafg 1.
  8. Vs gurl onynapr, 6 vf gur bqq onyy naq vf yvtugre guna gur bguref.
  9. Vs gurl qba'g onynapr, 3 vf gur bqq onyy naq vf urnivre guna gur bguref.
  10. Vs gur onyyf qba'g onynapr va fgrc #6, rvgure gur cna jvgu 1 naq 5 jvyy tb qbja be gur cna jvgu 4 naq 2 jvyy tb qbja.
  11. Vs gur cna jvgu 1 naq 5 tbrf qbja, sebz fgrc #5 jr pna pbapyhqr guna rvgure 1 vf gur bqq bar bhg naq vf urnivre guna gur bguref be 4 vf gur bqq bar bhg naq vf yvtugre guna gur bguref.
  12. Jrvtu 1 ntnvafg 8. Vs gurl onynapr, 4 vf gur bqq bar bhg naq vf yvtugre guna gur bguref. Vs gurl qba'g, 1 vf gur bqq bar bhg naq vf urnivre guna gur bguref.
  13. Vs gur cna jvgu 4 naq 2 tbrf qbja va fgrc #10, sebz fgrc #5 jr pna pbapyhqr gung rvgure 2 vf gur bqq bar bhg naq vf urnivre guna gur bguref be 5 vf gur bqq bar bhg naq vf yvtugre guna gur bguref.
  14. Jrvtu 2 ntnvafg 8. Vs gurl onynapr, 5 vf gur bqq bar bhg naq vf yvtugre guna gur bguref. Vs gurl qba'g, 2 vf gur bqq bar bhg naq vf urnivre guna gur bguref.
  15. Va fgrc #5, vs 4, 5 naq 6 tb qbja, pneel bhg gur erznvavat fgrcf ol fjnccvat 1, 2 naq 3 jvgu 4, 5 naq 6 erfcrpgviryl.
I confess that I had to finally give up while trying to solve the 12-ball variation in the second puzzle.

13 comments:

  1. I haven't un-rot13'd your solution but here's mine.

    Place 2 of the balls on each side of the scale. If these come out equal, the different ball is not among them; if they come out different, it is. Either way you now have a set of 4 balls (set A) that are known not to contain the mystery ball, and a set of 4 (set B) that are known to contain it.

    Take three balls from set A and three from set B, and put them on each side of the scale. If these come out equal, then the mystery ball is the one remaining ball from set B, so weigh it against any one of the other balls to determine if it's heavier or lighter.

    If the three from A are *not* equal to the three from B, the mystery ball is one of the three from B, and it's known to be either heavier or lighter based on whether that set was heavier or lighter than the three from A.

    In that case, weigh any two of the candidates against each other. If they're equal, the mystery ball is the other one. If they're different, pick the one that is heavier or lighter as determined in the previous paragraph.

    I haven't even attempted a solution to 12 balls yet, because I'm supposed to be working ;)

    ReplyDelete
  2. A few people in the offiice here sat down to crack these problems. We cracked
    the first one pretty fast, in the same way as Stuart in the above comment.
    The second one (12 balls) took us a while, and while I was the one to finally
    find the solution, it was building on a lot of thinking by other people. These
    people are: Lillian Angel, Tony Balkissonn, Andrew Cagney, and Adam Jocksch.

    So here's the solution:

    LS == left side of the scales, RS == Right side of the scales, Out == out (not being weighed).
    G == good balls (all normal weight), B == Bad balls (one of the balls is not normal weight).
    H == A ball that we suspect is Heavier
    L == A ball that we suspect is Lighter
    N == A ball we know is Normal/Neutral

    First Weighing:
    ===============

    LS:||| RS:||| Out:
    1 2 3 4 | 5 6 7 8 | 9 10 11 12

    We have 2 cases:

    1. LS == RS, then we realize that one of the Out balls is Bad, and we can use
    the technique from Stuart's solution above with 3 of the Good balls and 3 of the
    Bad to solve the problem.

    2. One of the sides is down, and the other is up. We don't care which one is
    which since these cases are entirely symmetrical. We assume that the LS is down
    (Heavier) and we label the balls as follows:


    1 2 3 4 5 6 7 8 9 10 11 12
    H H H H L L L L N N N N

    We throw out balls 10, 11, and 12 because we don't need them anymore, and keep
    the rest. The second weighing is as follows:

    Second Weighing:
    ================

    LS: RS: Out:
    1 5 6 2 7 9 3 4 8

    Now lets label the balls with their previously found properties, as follows:

    LS: ||| RS: ||| Out:
    1 5 6 | 2 7 9 | 3 4 8
    H L L | H L N | H H L


    Now we can have 3 cases again:

    1. LS == RS
    2. LS up, RS down
    3. LS down, RS up

    Lets look at them in turn.

    1. LS == RS
    -----------
    We now know that all these balls are the same weight. So we will have our
    third weighing as follows:
    LS: RH:
    3 --- 4
    H --- H

    If they are the same, then we know that ball 8 is the odd ball and it's light.
    If not we know that the heavier one of (3, 4) is the odd ball and is heavy.


    2. LS up, RS down
    -----------------
    We now know that either one of balls 5 or 6 is light or that ball 2 is heavy.
    We have our third weighing as follows:
    LS: RH:
    5 --- 6
    L --- L

    If they are the same we know that ball 2 is the odd ball, and it's heavy.
    If not, we know that the lighter ball is the odd ball, and is light.

    3. LS down, RS up
    ----------------
    We know that either ball 1 is heavy of ball 7 is light.
    We have our third weighing as:
    LS: RS:
    1 --- 9
    H --- N

    If ball 1 is heavier, then it is the odd ball, and it's heavy.
    If both balls are equal, then we know ball 7 is the odd ball and it's light.

    ReplyDelete
  3. Stuart and Igor: Your solution to the 8-ball problem is the most elegant I have seen so far. All the people to whom I have asked this puzzle and who make any progress towards the solution have chosen the initial weighing as shown in my solution.

    Igor: Once again, this is a different solution to the one I normally see (if at all) for this problem. You might want to contrast your solution with the one given in the linked-to page.

    Guys, I didn't mean you to try these out during work hours! ;-)

    Very impressive nonetheless!

    ReplyDelete
  4. I carefully didn't look at Igor's solution (or the linked one) to 12 yet; here's mine.

    Place four balls on each side. If these are all equal then you have a set of eight known not to contain the mystery ball and a set of four known to contain it - use these as sets B and A and do the remaining weighings as in my first solution.

    Otherwise, take two off the heavier side and one off the lighter side and add a ruled-out ball to what was the heavier side, and ALSO switch one that was originally on the left with one that was originally on the right. If the balance switches sides it's one of the two that was switched (scenario 1). If the balance becomes equal the mystery ball is one of the three that was taken off (scenario 2). And if it stays the same it's one of the three that was left alone (scenario 3).

    Scenario 1: based on which side was heavier in the first weighing it's known which of the two switched balls is heavier than the other. Weigh the heavier of them against one of the balls that has been ruled out: if they're different it's that one and it's heavier; if they're equal it's the other one and it's lighter.

    Scenario 2: We have two balls that are possibly heavier, and one that's possibly lighter. Weigh the two that are possibly heavier against each other. If they're equal it's the other one and it's lighter. If they're different it's the heavier one.

    Scenario 3 is the opposite of scenario 2 (two possibly lighter, one possibly heavier) and is solved in the corresponding way.

    Does that work?

    ReplyDelete
  5. I think I got A and B backwards in the first paragraph of my solution to 12. Oops. I switched the order of the sentences to make it simpler by putting A and B in the right order, then forgot to actually switch A and B ;) You got the idea though.

    Anyway looking at Igor's solution and the linked one I think all three of our solutions are equivalent; Igor's and the linked one just number the balls differently, and mine gets away without numbering them at all. But I think the actual weighings that get done are equivalent to each other. I could be wrong though, I have a hard time keeping track of all the numbers in the other two solutions ;)

    ReplyDelete
  6. Stuart,

    I haven't looked at the provided solution, but yours looks equivalent to mine, although in far fewer words. :)

    I think I actually came up with another, simpler (I think), solution but I'm gonna see if there really aren't any holes in it before I post it.

    Igor

    ReplyDelete
  7. I wonder if there's a solution to 13.

    With three weighings and three ways each weighing can go, you can get up to 3-cubed = 27 different outcomes. And given that each ball can be either heavier or lighter, for n balls there are 2n outcomes. So the puzzle for 12 has 24 possible answers and three possible outcomes of the weighings that are unused, impossible or duplicated; 13 - if it's solvable - would have 26 answers and one unused/impossible/duplicated, and 14 is definitely unsolvable.

    I can identify the three impossible outcomes but I don't think I can see any way to use any of them to identify a 13th ball:

    1) In the third weighing of the case where the first solution gets used and "the mystery ball is the one remaining ball from set B", "equal" is not a possibility.

    2) In "scenario 1" where you "weigh the heavier of them against one of the balls that has been ruled out", it's not possible for the ruled out ball to turn out heavier.

    3) The same as 2. Because that situation arises for each of the two ways the initial weighing could come up as different.

    Anyone able to either find a solution to 13 or prove that a solution can't be found?

    ReplyDelete
  8. Stuart,

    That's a good point, I haven't thought about it. But I think that my other way of solving the 12 problem (which I've verified now) can be extended to solve 13. Lets see if I can make it work... :)

    ReplyDelete
  9. I'm thinking about this too much in worktime ;)

    I think I can prove that 13 is unsolvable.

    The key is that after the first weighing each of the three possible outcomes must leave the problem solvable in two weighings, which means no more than nine possible answers.

    The solution for 12 works because the initial weighing partitions the 24 answers into three groups of eight. If the balance is equal, the eight answers are the four unweighed balls in each possible direction. If it's not equal, it's four of them in one direction and the other four in the other direction.

    But if you have 26 answers the only way to partition that into three groups, without any of them having more than nine members, is if it were possible to get 9,9,8. The 8 would have to be the "equal" case, since the other two outcomes are symmetric, which means it would have to involve leaving exactly 4 balls unknown. But that leaves 9 balls that need to be on the scale and you can't do that and get a useful answer, because there need to be equal numbers on each side.

    So the only possible ways to partition the answers with thirteen balls and one weighing is 8,8,10 (four on each side, five off) and that leaves the "equal" case with ten possible answers and hence unsolvable in two weighings - or 10,10,6 (five on each side, three off) which is even worse.

    QED.

    ReplyDelete
  10. 13 is solvable if you add the extra bit of information "ball 1 is not heavier". Proving this is left as an exercise for the reader ;)

    ReplyDelete
  11. I have read in many places (though I can't locate a proof right now) that the maximum number of balls that yield a solution in a puzzle of this type for 'n' weighings is given by the formula "(3^n - 3)/2".

    For n=3, 12 is indeed the maximum number of balls that can give a solution given the constraints.

    ReplyDelete
  12. I have solved the 12 ball problem. It might be helpful to note that the solution requires log2(12)+1=4.585 bits of information, and each weighing yields a maximum of log2(3)=1.585 bits of information. The main idea while solving is trying to make sure the three possible results of each weighing are as simarly probable as possible, maximizing the information obtained.

    My solution is represented below. The balls are labelled alphabetically from a to l. The notation should be obvious. Note that x marks a contradiction.


    abcd<efgh abe<cfi af<ij a<
    abcd<efgh abe<cfi af=ij b<
    abcd<efgh abe<cfi af>ij f>

    abcd<efgh abe=cfi dg<ij d<
    abcd<efgh abe=cfi dg=ij h>
    abcd<efgh abe=cfi dg>ij g>

    abcd<efgh abe>cfi c<i c<
    abcd<efgh abe>cfi c=i e>
    abcd<efgh abe>cfi c>i x


    abcd=efgh ij<ka ik<ab i<
    abcd=efgh ij<ka ik=ab j<
    abcd=efgh ij<ka ik>ab k>

    abcd=efgh ij=ka l<a l<
    abcd=efgh ij=ka l=a x
    abcd=efgh ij=ka l>a l>

    abcd=efgh ij>ka ik<ab k<
    abcd=efgh ij>ka ik=ab j>
    abcd=efgh ij>ka ik>ab i>


    abcd>efgh abe<cfi c<i x
    abcd>efgh abe<cfi c=i e<
    abcd>efgh abe<cfi c>i c>

    abcd>efgh abe=cfi dg<ij g<
    abcd>efgh abe=cfi dg=ij h<
    abcd>efgh abe=cfi dg>ij d>

    abcd>efgh abe>cfi af<ij f<
    abcd>efgh abe>cfi af=ij b>
    abcd>efgh abe>cfi af>ij a>

    ReplyDelete
  13. I want to say thank you for every thing

    ReplyDelete

Note: Only a member of this blog may post a comment.