Author |
Topic: HARD: 12 balls (Read 3904 times) |
|
S. Owen
Full Member
Gender: 
Posts: 221
|
 |
HARD: 12 balls
« on: Jul 26th, 2002, 4:42pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
Thanatos
Guest
|
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
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: HARD: 12 balls
« Reply #2 on: Oct 10th, 2002, 8:25pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: HARD: 12 balls
« Reply #3 on: Oct 12th, 2002, 4:29pm » |
Quote Modify
|
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
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
NeedQTIP2StabBrain
Newbie
  
Gender:
Posts: 4
|
|
Re: HARD: 12 balls
« Reply #4 on: Nov 5th, 2002, 12:52am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
Guest
Guest
|
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?
|
|
IP Logged |
|
|
|
Gate2Math
Guest
|
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??
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: HARD: 12 balls
« Reply #7 on: Sep 13th, 2004, 7:02pm » |
Quote Modify
|
on Sep 13th, 2004, 2:45pm, 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?
|
|
IP Logged |
|
|
|
giridhart
Newbie
Posts: 1
|
|
Re: HARD: 12 balls
« Reply #8 on: Sep 14th, 2004, 12:45am » |
Quote Modify
|
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.....
|
|
IP Logged |
|
|
|
nixie24
Newbie
Posts: 1
|
|
Re: HARD: 12 balls
« Reply #9 on: Dec 2nd, 2004, 6:58am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
  
Gender:
Posts: 2873
|
|
Re: HARD: 12 balls
« Reply #10 on: Dec 2nd, 2004, 8:11am » |
Quote Modify
|
If I'm reading this right, you are taking 4 weighings to solve the problem. It is possible to do it in three.
|
|
IP Logged |
|
|
|
pcbouhid
Uberpuzzler
Gender:
Posts: 647
|
|
Re: HARD: 12 balls
« Reply #11 on: Nov 17th, 2005, 7:08am » |
Quote Modify
|
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.
|
| « Last Edit: Nov 17th, 2005, 2:59pm by Icarus » |
IP Logged |
Don´t follow me, I´m lost too.
|
|
|
pcbouhid
Uberpuzzler
Gender:
Posts: 647
|
|
Re: HARD: 12 balls
« Reply #12 on: Nov 17th, 2005, 7:12am » |
Quote Modify
|
I´m new here, so I dont know why when typing an eight, appeared that wink.
|
|
IP Logged |
Don´t follow me, I´m lost too.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: HARD: 12 balls
« Reply #13 on: Nov 17th, 2005, 9:25am » |
Quote Modify
|
on Nov 17th, 2005, 7:12am, 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.
|
|
IP Logged |
|
|
|
pcbouhid
Uberpuzzler
Gender:
Posts: 647
|
|
Re: HARD: 12 balls
« Reply #14 on: Nov 17th, 2005, 11:16am » |
Quote Modify
|
Tk you Grimbal, I figured it out when I was posting the question. My previous post is already corrected.
|
|
IP Logged |
Don´t follow me, I´m lost too.
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: HARD: 12 balls
« Reply #15 on: Nov 17th, 2005, 11:27am » |
Quote Modify
|
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).
|
| « Last Edit: Nov 17th, 2005, 11:29am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
pcbouhid
Uberpuzzler
Gender:
Posts: 647
|
|
Re: HARD: 12 balls
« Reply #16 on: Nov 17th, 2005, 12:29pm » |
Quote Modify
|
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.
|
|
IP Logged |
Don´t follow me, I´m lost too.
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: 12 balls
« Reply #17 on: Nov 17th, 2005, 3:07pm » |
Quote Modify
|
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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove