Try your problem solving skills.
Here is the problem I was presented with at the SharePoint Connections 2007. For some reason SharePoint folks did not want to hang out with me, so I've found myself in the company of "SQL Geeks" ... SQL is my OTHER favorite thing...
So here is the thing, one of the SQL gurus tells me the "problem" he had to solve at his job placement interview, he also specifically mentioned that the problem might not have a solution, it is just a way to explore your way of thinking.
Here it is:
1. you have 8 balls. all of them are of the same weight, but one.
2. you do not know if this one ball is heavier or lighter then the others
3. you have the scale to measure the weight of these balls, but you can measure it only 3 times.
I'm opening the competition for all of you to tell me the right answer. Send you ideas in form of comments.
The reason why I want to post it is that I've given this problem to my 11 year old son, who in turn was trying to get away from dong his extra curriculum activities (like vocabulary enhancement).
To make the story short he solved this problem in 1 hour!!!!!!
Hellooooooo, in ONE hour. it took me the whole flight from Orlando to New York to even overcome the fact that this "problem" might have a solution.
Try your self out, I'll post the solution next week.
14 comments:
2 cubed = 8, so this should tell you the ball thats different, I think.
Divide the number of balls into 2 groups of 4 and weigh them. Take the side that tips the scale and divide the group in 2. Place the 2 on each side of the scale. Take the side that tips the scale and weigh them. The one that tips the scale is your odd ball.
eric
Nope. you are not accomplishing anything by that first step :-)
You need three groups ... left side (3), right side(3), and table(2). Weigh them. If equal the lighter ball is on the table. If one side tips down that side has the lighter ball.
Depending on the outcome, move the balls and repeat the above with left side (1), right side(1), and table(1/0).
In two passes you'll find the one odd man out.
You need three groups ... left side (3), right side(3), and table(2). Weigh them. If equal the lighter ball is on the table. If one side tips down that side has the lighter ball.
Depending on the outcome, move the balls and repeat the above with left side (1), right side(1), and table(1/0).
In two passes you'll find the one odd man out.
I did say that the ball might be lighter OR heavier than the others. You don’t know what is the case here all you know is that it is not like the rest
Start with 2 balls on left, 2 balls on right, and 4 on table. If there is equilibrium, your ball is on the table. If not, it's on the scale.
Out of those 4 balls, take 1 on the left, 1 on the right. If there is equilibrium, your ball is still on the table, if not, it's on the scale.
Take the two balls it could possibly be, and replace one of them with a ball we know is not the odd ball (put a mark on it or something). If there is equilibrium, the odd ball is the ball that you just replaced. If there is not, your ball is on the scale. (The one without the mark)
Make 4 groups of 2 balls each (A, B, C, and D). Measure (1) two of the groups (A & B). If these two groups are the same, then the odd-ball is in one of the two groups you didn't measure (C or D). If the scale tips, then the odd-ball is in one of the two groups you measured (A or B).
If the scale tips, remove one ball from each side of the scale and measure (2). If the scale tips, remove one of the balls and replace it with another. If the scale tips again, then it is the ball you left. If the scale doesn't tip, then it is the ball you replaced. If the scale doesn't tip in measurement 2, then the odd-ball is one of the balls you removed. Take one of the balls from measurement 2 and test it against one of the balls you removed. If the scale tips, the odd-ball is the ball you tested but had removed earlier. If the scale doesn't tip, the odd-ball is the ball you removed earlier and didn't test.
Going back to measurement 1, if the scale doesn't tip, leave one of the "good" groups on the scale and measure (2) one of the other groups (test A against C for example). If the scale tips, then the odd-ball is in group C. If the scale doesn't tip, then the odd-ball is in group D.
If it is in group C, measure (3) the two balls in group C against each other. If the scale tipped upwards in measurement 2 (group C was heavier than group A), then the odd-ball will be the heavier of the two. If the scale tipped downwards in measurement 2 (group A was heavier than group C), then the odd-ball will be the lighter of the two.
If it is in group D, measure (3) one ball from group D against a ball from group A. If the scale tips, the odd-ball is the ball you tested from group D. If the scale does not tip, the odd-ball is the ball you have not tested yet.
Aside from typos and hard to read and understand English, I think that's it.
SCENARIO 1
Grab 4 balls, and weigh them in groups of 2 (1st try). If all the same put aside, otherwise jump to scenario 2.
From the remaining 4 balls, grab two and weigh them against two of the ones you put aside (2nd try).
If all the same, your different ball is one of the two you haven't weighed, otherwise jump to sub-scenario 1. Grab
any of the remaining two and weigh
it against any of the 6 you have already weighed (3rd try) if the same, the diff ball is the one you haven't weighed.
If different, you got your diff ball.
SUB-SCENARIO 1
If on your second try you got different weights, grab one ball from the different side and weigh against any of the
four you put aside (3rd try). If different, you got your ball. If the same, the one you didn't weigh is your different ball.
SCENARIO 2
Your groups are of different weight. Take one of the groups off the scale and put aside. Take two more balls and weigh (2nd try)
If the same, then the group you took off the scale has your different ball, otherwise jump to sub-scenario 2. Take any
ball from the group of two you originally took off of the scale and weigh against any of the other 6 balls (3rd try). If the
same, the ball you didn't weigh is your different ball otherwise you got your ball.
SUB-SCENARIO 2
If you are in this scenario you have used 2 tries to weigh 3 sets of 2 balls and have gotten the same result. From the group
of 2 that has different weight, grab one ball and weigh against any of the other 6 balls (3rd try). If the same, the ball
you didn't weigh is the different ball, otherwise you got your ball.
I hope my explanation is clear enough, it's not that easy to explain.
You divide the 8 balls in 4 groups of 2 (A, B, C and D):
Weigh A and B
1-if they balance, weigh A and C
1.1-if they balance, the odd ball is in D. Weight one ball from A with one ball of D
1.1.1-if they balance the odd ball is the other one in D.
1.1.2-if they don't balance, the ball from D is the odd one, and you can even tell if it's heavier or lighter.
1.2-if they don't balance, the odd ball is in C. Weight one ball from A with one ball of C
1.2.1-if they balance the odd ball is the other one in C.
1.2.2-if they don't balance, the ball from C is the odd one, and you can even tell if it's heavier or lighter.
2-if they don't balance, weigh A and C
2.1-if they balance the odd ball is in B, Weight one ball from A with one ball of B
2.1.1-if they balance the odd ball is the other one in B.
2.1.2-if they don't balance, the ball from B is the odd one, and you can even tell if it's heavier or lighter.
2.2-if they don't balance the odd ball is in A, Weight one ball from B with one ball of A
2.2.1-if they balance the odd ball is the other one in A.
2.2.2-if they don't balance, the ball from A is the odd one, and you can even tell if it's heavier or lighter.
Caligari
1) take 4 balls and measure (2 on each side of the scale)
* if the weights are equal, you know that the odd ball is in the other 4 balls
* of the wieghts are not equal, then you know the odd ball is in this goup of 4
Either way, now you have 4 only balls. Throw the other 4 away, you won't be needing them anymore.
2)take 2 balls out of the 4 that are left and measure them (one on each side of the scale)
* if the weights are equal then you know that the odd ball is in the other 2 balls
* if the weights are not equal you know that the odd ball is one of these two
3) Take one ball from the group of two that were equal weights and put it on the left side of the scale and one ball from the not equal group and put if on the right side of the scale
* if the weights are equal then you know the ball you didn't measure is the odd ball :)
* if the weights are not equal than the ball on the right side of the scale is your odd ball :)
Took me 10 mins ;) 15 to describe it. I hope somebody will understand what I was trying to say :/
Put 4 balls on one side of the scale and 4 on the other. One side will be lighter. Take the 4 balls on the lighter side and split them into 2 groups of two and weigh them. One side will be lighter. Take the lighter 2 balls and weigh them. The lighter of these two will be the lightest.
The problem doesn't have a solution because you didn't ask for one. You just said that you have 8 balls, one is a different weight, and you can make measurements only three times. You don't ask find the odd ball, but more importantly, you don't ask to find the heaviest or lightest ball. So it's not a problem, but a situation. Not only that, but a situation that asks for no results.
Solution:
Step1. Put 2 balls and 2 balls on the scale. We will find group of 4 balls with "different" ball.
If scale not in balance - we got correct group, if scale in balance - rest of 4 balls to work with.
Step2. Put 1 and 1 ball on the scale from group from step1. Same logic. If balls are equal - rest of 2 balls have "different" ball and we also have "normal" ball which is one on the scale right now. If balls are not equall - we have correct group to work with, and we have "normal" ball in the rest of the ball.
Step3. Now we are down to 2 balls from step2 which has "different" ball. Take ANY ball from this group and put in the scale with ANY ball from the rest of the ball which guaranty to be "normal". If scale is not in balance, we got our "different" ball. If scale is in balance - second ball which is not currently on the scale is "different".
Happy Thanksgiving Natasha, see you tomorrow :)
Binary Search :)
Post a Comment