wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> 12 balls variation
        
(Message started by: WRX on Jul 29^th, 2002, 2:52pm)

Title: 12 balls variation
Post by WRX on Jul 29^th, 2002, 2:52pm

The 12 balls riddle is very similar to a slightly different (and I think more interesting ;D ) riddle I've heard before.

Use 13 balls, everything else the same. Also you DON'T have to know whether the unique ball is lighter or heavier.

In my solution there is only one distinct case where you don't know it, BUT I'm not totally convinced that you can't come up with a way so that you do know whether it is heavier or lighter.

I'm hoping someone here can find a better way then my solution where you ALWAYS know whether the unique ball is heavier or lighter.

Good luck.

Title: Re: New riddle -- 12 balls variation
Post by AlexH on Jul 29^th, 2002, 10:07pm

This 12 ball problem can be solved by a non-interactive method. Consider scale readings as digits and associate each reading of digits with one combo of ball # and heavier/lighter (so 12*2=24 possiblities). The two requirements are that you associate ball n heavier with the opposite reading as ball n lighter, and that you balance the L's and R's so that you don't wind up with equal numbers of balls on each side of the scale. For example if you're associating ball 5 heavier with (left, even, right) as the output of the scale, then ball 5 goes on the left side in measurement 1, off to the side in measurement 2, and on the right side in measurement 3. The inverse (right, even, left) is now the code for ball 5 lighter. You don't want to use the combination (even, even, even) because that is its own inverse and it wouldn't tell you if the ball associated with it was heavier. You can use all other 13 measurement and inverse pairs to determine weights with 1 caveat --- you'll need one spare reference ball to balance matters.

For example
1H = LRR, 2H = LER, 3H = LRE, 4H = LEE,
5H = RLR, 6H = ELR, 7H = RLE, 8H = ELE,
9H = RRL, 10H = ERL, 11H = REL, 12H =EEL

Weighing 1: 1,2,3,4 vs 5,7,9,11
Weighing 2: 5,6,7,8 vs 1,3,9,11
Weighing 3: 9,10,11,12 vs 1,2,5,6

When we add 13H= LLL then we add it to the left side of each weighing and add our reference ball to the right side so that we have 5 balls on each side. If we don't need to know heavier vs lighter then we can set 13H = 13L = EEE and we don't need the reference ball. Given the reference ball method we could add a 14th ball which is EEE and we don't get to learn heavier/lighter but we can determine if it is the odd one.

Even if we're given the ability to be interactive we still can't do it without a reference ball. If the first measurement is 4v4 then an even result leaves 10 possiblities, while if its 5v5 then an uneven result leaves 10 possiblities. Given only 2 measurements remaining we can only distinguish 9 different cases.

Title: Re: New riddle -- 12 balls variation
Post by WRX on Jul 30^th, 2002, 7:45am

Thanks, that sounds right to me.

Title: Re: New riddle -- 12 balls variation
Post by kenny on Jul 30^th, 2002, 12:26pm

One trick I've used to determine whether a puzzle of this type is solvable is to count possibilities.

Since each weighing gives 3 possible states, 3 weighings gives 27 (= 3 cubed) possible outcomes.

In the original puzzle, one of the 12 balls is different, and it is lighter or heavier. Thats 2x12 = 24 possibilities. So it should be possible (and is).

Thus, it seems like 13 balls could also be possible, since 13 x 2 = 26 < 27.

Unfortunately, it's not. Consider the first weighing. You must put the same number of balls on each side, so an odd number of balls is left out.

If you weigh 4 on each side, that's 5 left. If the balance is even, then you have to determine between 5 balls, lighter or heavier, for 10 possibilities. Since 10 > 9 (3 squared), you can't determine that in 2 weighings.

If you weigh 5 on each side, then if it tilts, you still have 10 possibilities (one of the 5 on the down side is heavier or one of the 5 on the up side is lighter). Still impossible.

If, however, you add a 14th ball, which you know to be of the correct weight, you can solve it.

-- Ken

Title: Re: New riddle -- 12 balls variation
Post by mook on Aug 18^th, 2002, 1:49pm

it is easy to figure out which ball is different if you can tell whether the ball is heavier or lighter than the others(which I cannot figure out)
1st weighing-6 and 6
lets call the 6 balls that weigh more together heavy and the others light.

2nd weighing-3 from light side vs 3 from heavy side

if they weigh the same, discard them and use the other six balls, if they are different, use them again for weighing 3

3rd weighing-weigh one heavy ball and one light ball vs one heavy ball and one light ball

the ball that's different is either the heavy ball from the heavy side or the light ball from the light side, or if both sides are equal it is either the heavy ball or light ball left from the original group of 3 light, 3 heavy.

if you know whether the different ball is lighter or heavier than the rest, then you know which one of your 2 options to choose from. does anyone know how to figure this out?

alex- after rading your post again, maybe you do have it, but i'm just not getting it, can someone explain it differently so my thick head can comprehend it?

Title: Re: New riddle -- 12 balls variation
Post by Jonathan_the_Red on Aug 18^th, 2002, 2:12pm

The general case is: in N weighings, you can distinguish between (3^N - 3) / 2 balls. (With N=3, this formula gives 12). Here's an algorithm, with examples for N=3.
(If you don't care about the general case solution, skip to the end for a quick and easy solution for N=3)

Step 1: write down all 3^N combinations of N digits consisting only of 0, 1, or 2. For N=3, this gives you:

000
001
002
010
011
012
020
021
022
100
101
102
110
111
112
120
121
122
200
201
202
210
211
212
220
221
222

Step 2: cross out the 3 combinations consisting of a single digit repeated N times, leaving you with 3^N - 3 combinations:

001
002
010
011
012
020
021
022
100
101
102
110
112
120
121
122
200
201
202
210
211
212
220
221

Step 3: cross out all of the combinations that aren't of one of these forms:

One or more 0s, followed by a 1, followed by anything
One or more 1s, followed by a 2, followed by anything
One or more 2s, followed by a 0, followed by anything

This eliminates half of the remaining combinations, leaving you with (3^N-3)/2 left. Number them.
01: 001
02: 010
03: 011
04: 012
05: 112
06: 120
07: 121
08: 122
09: 200
10: 201
11: 202
12: 220

Now, read down each of the N columns to determine your N weighings. If a ball has a 0 in a given column, it goes on the left pan for that weighing. If it has a 2, it goes on the right pan, and if it has a 1, it stays off the scales. This gives you:

Weighing 1: 1, 2, 3, 4 vs. 9, 10, 11, 12
Weighing 2: 1, 9, 10, 11 vs. 6, 7, 8, 12
Weighing 3: 2, 6, 9, 12 vs. 4, 5, 8, 11

After each weighing, write down a 0 if the left pan is heavy, a 1 if the scales balance, a 2 if the right pan is heavy. When you're done, you'll have written an N-digit number. If you find that number in the list, the corresponding ball is heavy. If it's not in the list, change each 0 to a 2 and each 2 to a 0 and try again. The corresponding ball is light.

For the special case where N=3, you can solve the problem like this:

Label each ball with a letter from the set (ACDEFIKLMNOT). Your weighings are:

Weighing 1: MADO vs. LIKE
Weighing 2: METO vs. FIND
Weighing 3: FAKE vs. COIN

("Ma, do like me to find fake coin.") This will produce a unique outcome for each of the 24 possibilities of oddball and lightness/heaviness.

Title: Re: New riddle -- 12 balls variation
Post by Eric Yeh on Aug 19^th, 2002, 9:37pm

BTW, there's a thread on this topic somewhere in easy or medium. It definitely doesn't belong in hard...

Title: Re: New riddle -- 12 balls variation
Post by Chronos on Aug 27^th, 2002, 4:45pm

It looks to me like nobody's addressed the first puzzle that WRX presented. Namely:

We have 13 balls, one of which is different.
The oddball is either heavier or lighter, but we don't know which.
Furthermore, we don't care whether the oddball is heavy or light.
We have three weighings.

Now, as in the 12 ball problem, we have three "trinary bits" of information, enough to (potentially) distinguish between 27 states (in the 12-ball problem, three of these states can be considered "error codes" which tell us that our scale is broken). In WRX's 13-ball problem, we only need to distinguish between 13 different states, so we have a glut of information. Probably, in many cases, we will also be able to determine whether the oddball is heavy or light, but that's not necessary for the solution.

As an example, in WRX's problem, if we first weigh six against six and find that they balance, we're done, because we know that the one left off the scale is the oddball, and we don't care if it's heavy or light.

Title: Re: New riddle -- 12 balls variation
Post by Jonathan_the_Red on Aug 27^th, 2002, 5:15pm

on 08/27/02 at 16:45:01, Chronos wrote:

This trivially reduces to the 12-ball problem. Just perform the 12-ball solution, leaving the thirteenth ball off the scales. If all three weighings balance, the thirteenth ball is the oddball.

Title: Re: New riddle -- 12 balls variation
Post by Chronos on Aug 28^th, 2002, 3:21pm

At least, it reduces to some forms of the 12-ball solution (your mnemnonic 4-on-4 solution will do the trick, for instance). But there are forms of the 12-ball solution which will not work here: Some forms of the solution rely on the knowledge that exactly one of the balls is odd. And in any event, it's only polite to the thread starter to point out that we've actually answered his question.

By the way, did you come up with that mnemnonic yourself? It's rather clever.

Title: Re: New riddle -- 12 balls variation
Post by AlexH on Aug 28^th, 2002, 3:47pm

on 07/30/02 at 07:45:36, WRX wrote:

Thanks, that sounds right to me.

He thought his question was answered a while back ;). I addressed the 13 ball situation in my post.

Btw, unless you assume you have a reference ball then you have to assume there is exactly 1 odd ball to do the 13 ball problem. The only way learn that a ball is the odd one and yet avoid learning whether it is heavier or lighter is for it to be the one you never weigh and just infer it is odd from the fact that none of the others are.

Title: Re: New riddle -- 12 balls variation
Post by Jonathan_the_Red on Aug 28^th, 2002, 5:01pm

Quote:

By the way, did you come up with that mnemnonic yourself? It's rather clever.

I wish I could take the credit, but I can't. Once upon a time I was the FAQ keeper for the Usenet newsgroup rec.puzzles, and the ol' 12-balls problem was frequently posted.

Another mnemonic is:

Label the balls from the set MAN FIRED SHOT

Weigh RAFT vs. DIME
Weigh FIRE vs. SHOT
Weigh MOAN vs. STIR

This one has the advantage that the set of 12 letters is easy to remember, but the disadvantage that the weighing words are arbitrary and need to be memorized. I prefer the single sentence version.

Title: Re: 12 balls variation
Post by william wu on Jan 28^th, 2004, 10:59pm

Three spirited words which make the set of 12 letters in "Ma do like me to find fake coin" easy to remember are: FAKE MIND CLOT. Also from rec.puzzles :)

Title: Re: 12 balls variation
Post by Nigel Parsons on Apr 4^th, 2004, 7:45am

I remember seeing this in the early eighties in a UK magazine "Games & Puzzles" The solution to the 12 ball puzzle was the same (3 weighings of 4v4) but the mnemonic was (possibly) more memorable.

Label the balls "THE KP FORMULA", then:
TAKE v FOUR &
PARK v THEM, then
HALF v MORE

Nigel