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):
- Xrrc onyyf ahzorerq 1, 2 naq 3 ba bar cna naq 4, 5 naq 6 ba gur bgure.
- Vs gurl onynapr, gurl ner nyy abezny naq bar bs 7 naq 8 vf gur bqq onyy. Jrvtu 7 ntnvafg 1.
- Vs gurl onynapr, 8 vf gur bqq onyy naq lbh pna svaq vgf bqqvgl ol jrvtuvat vg ntnvafg 1.
- Vs gurl qba'g onynapr, 7 vf gur bqq onyy naq lbh jvyy vzzrqvngryl xabj vs vg vf urnivre be yvtugre guna gur bguref.
- 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.
- Xrrc 1 naq 5 ba bar cna naq 4 naq 2 ba gur bgure. Xrrc 3 naq 6 nfvqr.
- 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.
- Vs gurl onynapr, 6 vf gur bqq onyy naq vf yvtugre guna gur bguref.
- Vs gurl qba'g onynapr, 3 vf gur bqq onyy naq vf urnivre guna gur bguref.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
|
|
Tweet |
|
A few people in the offiice here sat down to crack these problems. We cracked
ReplyDeletethe 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.
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.
ReplyDeleteIgor: 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!
Stuart,
ReplyDeleteI 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
Stuart,
ReplyDeleteThat'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... :)
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".
ReplyDeleteFor n=3, 12 is indeed the maximum number of balls that can give a solution given the constraints.
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.
ReplyDeleteMy 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>
I want to say thank you for every thing
ReplyDelete