wu :: forums - Print Page


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

        riddles >> hard >> HARD: 12 balls
        
(Message started by: srowen on Jul 26^th, 2002, 4:42pm)

Title: HARD: 12 balls
Post by srowen on Jul 26^th, 2002, 4:42pm

In the spirit of wu's post I'll add the reasoning that leads pretty quickly to this solution.

You are trying to differentiate between 24 possible situations (any one of the 12 balls could be heavy, or light). You have only 3 weighings, each of which has 3 outcomes, for 27 possibilities. So you will have barely enough info to do this.

You have to select each weighing carefully. After your first, no matter what happens, there must be 9 or less possibilities remaining, or else you have no hope of figuring out which one is the case with just 2 more weighings.

That observation will help you quickly sift through possibilities that can't work.

So here's a way to do it - there may be others.

For convenience, number the balls 1 to 12. For notational convenience I'll refer to the situation that 1 is heavy as "1H", that it's light as "1L", and likewise for "2H", "2L", etc.

First weighing:
1,2,3,4 vs. 5,6,7,8

If they balance:
The only possibilities left are that one of 9-12 is the odd one.
9H,9L,10H,10L,11H,11L,12H,12L
If the left side is heavier:
Either one of 1-4 is heavy, or 5-8 is light.
1H,2H,3H,4H,5L,6L,7L,8L
If the right side is heavier:
Same thing as above, but reversed, so I won't repeat it further.

Good so far - in all cases I have 8 possibilities left.

Second Weighing if First balances:
1,2,3 vs. 9,10,11
If they balance:
12H, 12L
12 is the odd one; third weighing weighs 1 vs. 12 to figure out whether it's heavy or light
If the left is heavier:
9L,10L,11L (1,2,3 are definitely not the odd one, remember)
Third weighing puts 9 vs. 10 - you either find that one is lighter, and it's your ball, or that they balance and 11 is light.
If the right is heavier:
9H,10H,11H - same thing.

Second Weighing if left is heavier on First weighing:
(similar to what happens if right is heavier)
1,2,5 vs. 3,4,6
If they balance:
7L,8L
Third weighing puts 7 vs. 8 to see which is the light odd one
If the left is heavier:
1H,2H,6L
Third weighing is 1 vs. 2 to find one heavier, or that 6 must be light.
If the right is heavier:
5L,3H,4H
Same thing - 3 vs. 4

The second weighings always leave 2 or 3 possibilities remaining, so that a third weighing can then find which possibility is the case.

Note that this reasoning show you can't possibly figure out the odd ball among 14 with just 3 weighings, etc.

Title: Re: HARD: 12 balls
Post by Thanatos on Oct 10^th, 2002, 5:53pm

Me and some friends have been mulling this one over and our interpretation of the riddle has us at odds with the solution you present.

in the riddle they go out of the way to mention that the balls are 'identical-looking balls'. Since the appearance shouldn't be a determining factor when dealing with weight, we took this to mean that the balls can not be distinguished from each other visually during any part of the weighing. This meaning that the problem should be solved without giving the balls any sort of identifying mark that would distinguish them off of the scale (ie a visible mark / number )

This becomes a problem as soon as you group the balls together because if you put a ball into a group you would be unable figure out exactly which one it was and take it out later.

Are we misreading the riddle?

???
j

Title: Re: HARD: 12 balls
Post by S. Owen on Oct 10^th, 2002, 8:25pm

Yeah, what you're getting at is can you do it without remembering which is which, so to speak? There is a thread called "12 balls variation" or something that goes into that.

Title: Re: HARD: 12 balls
Post by Eric Yeh on Oct 12^th, 2002, 4:29pm

Thanatos,

"Identical-looking" just means you can't tell them apart at first glance. You can always remember which is which after weighings.

Are you a Marvel guy?

Best,
Eric

Title: Re: HARD: 12 balls
Post by NeedQTIP2StabBrain on Nov 5^th, 2002, 12:52am

When I was in High School, the math I was enrolled in was called IMP. It was a program that was developed by UC Berkley. This problem was given during the sophomore year of the class. Took a while for me to figure out.
IMP dealt with mainly word problems. They figured that it's what you would recieve in "Real Life" Not just a list of math problems. Sadly, this program was stopped shortly after I graduated. It was more fun than doing regular math problems anyways.

Nick

Title: Re: HARD: 12 balls
Post by Guest on Nov 11^th, 2003, 8:36pm

In case there are 13 balls, we can still find out the odd ball but we wont be able to say if its heavier or lighter in one case. 13*2 = 26 < 27 but after first weighing of 4-4 balls, we are left with 5*2 = 10 > 9 possibilities. Even then, we can find the odd ball. What differentiates this from the case where we have 14 balls?

Title: Re: HARD: 12 balls
Post by Gate2Math on Sep 13^th, 2004, 2:45pm

In your solution. Somewhere in the middle, you typed:

Second Weighing if left is heavier on First weighing:
(similar to what happens if right is heavier)
1,2,5 vs. 3,4,6
If they balance:
7L,8L
Third weighing puts 7 vs. 8 to see which is the light odd one
If the left is heavier:
1H,2H,6L

Now, what if 5 was the ODD ball here, and you did not consider it??

Title: Re: HARD: 12 balls
Post by S. Owen on Sep 13^th, 2004, 7:02pm

on 09/13/04 at 14:45:04, Gate2Math wrote:

Now, what if 5 was the ODD ball here, and you did not consider it??

You didn't quote the last piece of that section of the solution:

If the right is heavier:
5L,3H,4H
Same thing - 3 vs. 4

The case where 5 is light is covered there, right?

Title: Re: HARD: 12 balls
Post by giridhart on Sep 14^th, 2004, 12:45am

consider we have divided 12 coins into 4 groups of 3coins each.
Name them (1) (2) (3) (4)
each coin can be named as
(1).1
(1).2
(1).3
(2).1
etc

Name the left pan as LP
Name the right pan as RP

for first weighing we will have
LP = (1) , (4).1
RP = (2) , (4).2

for second weighing
LP = (2) , (4).1
RP = (3) , (4).2

by now we will know which group contains the bad one and also whether it is HEAVIER or LIGHTER

suppose in both weighings if LP or RP is lighter then (4).1 or (4).2 is the coin and
it can be found out easily with another weighing

suppose in first weighing LP is lighter and in second heavier then (2) has the coin and heavier

suppose in first weighing LP is lighter and in second equal then (1) has the coin and is lighter

suppose in both weighings are equal then (4).3 is bad and we can find it out in third weighing whether it is heavy or light

if we want for 39 coins then
divide it into 3 parts having 12 coins each and one more with 3 coins each

we can follow the same procedure

in general

let us suppose there can be W weighings
and f(W) be max number of coins we can test
then

f(2) = 3;
f(3) = 12;
f(4) = 39;
f(W) = 3 * f(W-1) + 3

no of weighs can be not less than log(base 3) N
N is no of balls.....

Title: Re: HARD: 12 balls
Post by nixie24 on Dec 2^nd, 2004, 6:58am

Put four balls (ABCD) on one side, and (EFGH) on the other side. If it is skewed, take the four balls on one side (eg EFGH), and split them into two and two and put them on each side (EF and GH). If it is still skewed, then you know that the heavier or lighter ball is one of these four. Remove one ball from each two (so balls left on the scale are F and H. If they’re still skewed, you know it’s one of the two. Remove F and put E back. If it is still skewed, the different ball is H, depednign on whether it goes up or down. If it becomes straight, then, F is the odd one, and depending on if it was going up or down, the ball is heavier or lighter.

If it becomes straight when you remove E and G from each side, then, either E or G is the odd one. Again, remove F and put E back on. If it’s becomes skewed, then E is the odd one, if it stays straight, then G is the odd one, and which ever way they go, up or down, then the ball is heavier or lighter. (removing a ball is not counted as weighing!)

If when you put EF and GH on either side, it becomes straight, then you know that the different ball is either A, B, C or D. And depending on whether the side with ABCD went up or down when you weighed it the first time, you’ll know if the odd ball is heavier or lighter. Take EF and GH off. And put AB and CD on either side, and it should become skewed. Take off A and C, if it stays the same, then either A or C, whichever one moved in the same direction as the ABCD side moved at first is the odd one. If it skews after you take A and C off, then either B or D, whichever one moves in the same direction as ABCD first did, is the odd one.

If when you’re measuring ABCD and EFGH, it’s straight, then it’s one of the four that you’re not measuring (IJKL). Take all of them off, put on IJ on one side, and KL on the other. The scales will become skewed. Remove I and K. If it remains skewed, then it is J or L. Remove J and put I on. If it’s still skewed, the odd one is L, and whichever way it’s going determines if the ball is heavier or lighter. If it’s straight, then J is the odd one, and the direction it was going determines if the ball is heavier or lighter. If the scales become straight when you remove I and K, then you know that it’s one of them. Take off J and put I on. If the scale now become skewed, then it’s I. If it stays straight, then it’s K.

Title: Re: HARD: 12 balls
Post by rmsgrey on Dec 2^nd, 2004, 8:11am

If I'm reading this right, you are taking 4 weighings to solve the problem. It is possible to do it in three.

Title: Re: HARD: 12 balls
Post by pcbouhid on Nov 17^th, 2005, 7:08am

My method: number the balls from 1 --> 12.

1)First weighing: (1)(2)(3)(4) x (5)(6)(7)(8)

1.a) balanced. So the odd ball is (9), (10), (11) or (12). Second weighing: (1)(2)(3) x (9)(10)(11). If balanced, then (12) is the odd ball, and in the third weighing (12) x (x) you´ll find if it´s lighter or heavier.
If doesn´t balance, you know that the odd ball is (9) or (10) or (11) and that it´s heavier or lighter, depending on what side they are. Only one more weighing (example (9) x (10)) will suffice.

1.b) doesn´t balance (so the odd ball is in the balance). WLOG, suppose left side lighter. Remove (1), (2) and (3), move (5), (6) and (7) to the other plate (where were (1), (2) and (3)), and put (9), (10) and (11) in the plate where (5), (6) and (7) were.

1.b.1) balanced: The odd ball was removed from the balance. So, it´s (1) or (2) or (3) and you know that it is lighter. One more weighing, (1) x (2), done.

1.b.2) unbalancing remains: the odd ball is still in the balance. So, it´s (4) and is lighter, or (8) and it´s heavier. One more weighing (with (4) or (8)), done.

1.b.3) the unbalancing changes: the odd ball changed plate. So, it´s (7), (8) or (9) and it is heavier. One more weighing (7) x (8), done.

Title: Re: HARD: 12 balls
Post by pcbouhid on Nov 17^th, 2005, 7:12am

I´m new here, so I dont know why when typing an eight, appeared that wink.

Title: Re: HARD: 12 balls
Post by Grimbal on Nov 17^th, 2005, 9:25am

on 11/17/05 at 07:12:08, pcbouhid wrote:

I´m new here, so I dont know why when typing an eight, appeared that wink.

Because 8) is how you write the smiley.

If you don't want it, check the box "[] Check this if you'll be adding code (or don't like smileys)." when you compose your message.

Title: Re: HARD: 12 balls
Post by pcbouhid on Nov 17^th, 2005, 11:16am

Tk you Grimbal, I figured it out when I was posting the question. My previous post is already corrected.

Title: Re: HARD: 12 balls
Post by JocK on Nov 17^th, 2005, 11:27am

You don't need to post a corrected version: you can simply edit your original posting (just click on 'modify' and make the required changes).

Title: Re: HARD: 12 balls
Post by pcbouhid on Nov 17^th, 2005, 12:29pm

Tk you, Jock.

One day I´ll learn how to place a nice "I don´t know how do you call them" below my name.

Title: Re: HARD: 12 balls
Post by Icarus on Nov 17^th, 2005, 3:07pm

I've lobbied before for William to change the code for that smiley, but he doesn't want to because it means all the places where it was used intentionally will no longer display it. Myself, I think it would be worth the loss to not have to deal with this all-too-common problem in the future.

You can personalize your posts with pictures, signatures, or mottos by clicking on the "Profile" link on the toolbar at the top of the page. To get a changing picture like Grimbal has, you need to link to your own picture, and set up the code as Grimbal explains here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_suggestions;action=display;num=1096325830).