 85239 |
 35211 |
|
|
||
|
|
|||||||
| Welcome to the Exploding Garrmondo Weiner Interactive Swiss Army Penis. |
|
GFF is a community of gaming and music enthusiasts. We have a team of dedicated moderators, constant member-organized activities, and plenty of custom features, including our unique journal system. If this is your first visit, be sure to check out the FAQ or our GFWiki. You will have to register before you can post. Membership is completely free (and gets rid of the pesky advertisement unit underneath this message).
|
 |
|
|
Thread Tools |
 Member 3320 Level 5.11 Mar 2006 
|
Which egg is the oddball?
Try to solve this problem:
You have 9 eggs that are all of the same weight except one. How can you determine which of the eggs is the oddball by setting up only three configurations on a balance? In each configuration, all the eggs are placed simultaneously onto the balance (i.e., you cannot place the eggs one by one onto the balance). Jam it back in, in the dark.
Last edited by eraemia; Sep 19, 2006 at 05:06 PM.
|
Member 41 Level 38.30 Mar 2006
|
Ha! I had this puzzle when I got interviewed by Microsoft and later with a smaller start-up company called Hillcrest Labs. I won't post the solution since I already knew it. It's a pretty simple problem. I began with a "what-if-I-do-this" and then everything else followed through.
Actually, with Microsoft, the first puzzle they asked me wasn't actually this set up. First was how would it be done if you could only put one ball (they used balls instead of eggs), on each side at a time, as well as the Big O of the algorithm, and best case/worst case analysis. That took all of about 20 seconds. Then they asked for the most efficient way (least weighings), without limitations. So they didn't ask your question exactly, but made me think of that problem and the answer. The other company just asked me your question straight-up. It was fun to act like I was thinking for that one. Edit: Also, for your problem, if you state whether the oddball egg is heavier or lighter, it can always be done in 2 configurations There's nowhere I can't reach. |
Member 56 Level 24.48 Mar 2006
|
I'd stack the eggs in a pyramidal formation centered above the fulcrum of the see-saw. Assuming the odd one out was heavier than the others, the see-saw would tip to the side containing the heavier egg, unless the egg happened to be in the dead-centre, in which case you'd have found it in one move. Assuming the see-saw does tip though, you have narrowed it down to four possible eggs.
Next you stack the pyramid as before but with the group of four suspected eggs laid down last, at the top. Depending on which side the see-saw tips this time, you have either found the odd egg, or narrowed it down to two possibilities. In the third and final configuration, the two potential eggs are stacked at the top, and whichever way the pyramid tips betrays the egg that is heaviest. It's a binary-search of some kind. This thing is sticky, and I don't like it. I don't appreciate it.  |
Member 41 Level 38.30 Mar 2006
|
Ugh.. "see-saw." He should've put a blance, as in those beam balances/lab balances, that "see-saw" to figure out the mass of objects.
To hot-link off wiki, this:  Not a see-saw see-saw. ;_; Now, try again, Ulysses, or anyone! I am a dolphin, do you want me on your body? |
Member 255 Level 20.88 Mar 2006
|
You take one egg as your "Standard" This egg will always stay in one of those saucers of the balance. Next, take every other egg and compare them one by one to the "Standard" by challenging their weights. The oddball should show the least decent in distance of height from the surface that balance's base rests on. And if the oddball is the "Standard," well then, all the trial results should of come out same-similar without any noticable differences.
I was speaking idiomatically. |
Member 41 Level 38.30 Mar 2006
|
That's a correct way! But that's the "brute-force" way. It has a best case of 2 mesaurements and worst case of 8 measurements.
There is a way to do where it will always take only 2 measurements given the oddball is heavier/lighters; let's say heavier. (Otherwise it could always be done in at most 3 measurements). What kind of toxic man-thing is happening now? |
Member 2043 Level 29.93 Mar 2006
|
I think the solution goes something like this.....
Side A and Side B for the balances.... Randomly choose 2 eggs, and put them each on the scale on opposite sides. More than likely, you chose 2 regular eggs and they balance out. If, by chance, you chose the abnormal egg, The weights will not be even. Take either one off and replace it with another egg, if it does the same behavior, the one you left on the balance from the first measurement is the abnormal egg. If it becomes balanced with the second measurement, then the one you took off is the abnormal one. If your initial reading was balanced, the two you used in the beginning are regular. That being said, place both of those eggs on one side and take two more random eggs and put them on the opposite side. If the scale is still balanced, then one of the remaining two eggs are abnormal. In this case, take one of your 4 regular eggs that you have deduced already and compare it to one of the remaining 2. If it is balanced, obvioiusly, it's a regular egg as wel and the one you haven't checkd yet is the abnormal. If it's unbalanced, then the egg you just compared to a regular is abnormal. If the second measurement is unbalanced, then one of the two you just put on is the abnormal one. Measure one of the questioned eggs with a known regular egg. If it's balanced, it's regular and the one you didn't measure is abnormal, If it's not balanced, then the one you measured last is abnormal. Man....let's give it shot practically, shall we? Eggs labeled 1, 2, 3, 4, 5, 6. Eggs on the balance will be in the format of Side A and Side B. So If you're measuring 1/2 and 3/4, Eggs1/2 will be on Side A, Eggs3/4 will be on side B. Measure Eggs 1 and 2. -If Unbalanced, either 1 or 2 is abnormal, so take off 2 and put in 3. If it becomes balanced, 2 is abnormal. If it's still unbalanced, 1 is abnormal. -If Balanced, Measure Eggs 1/2 and 3/4. **If Balanced, then either 5 or 6 is abnormal. Take off 1/2/3/4 and measure 1 and 5. If Balanced, then 6 is Abnormal, and if not, 5 is abnormal. **If Unbalanced, then either 3 or 4 is abnormal. Take off 2/4, so you should be measuring 1 and 3. If Balanced, 4 is abnormal, if not, 3 is abnormal. FELIPE NO
Last edited by Omnislash124; Sep 19, 2006 at 02:46 PM.
|
Member 360 Level 25.07 Mar 2006
|
Did you get the job from Microsoft....?
What, you don't want my bikini-clad body?
Thanks to Fjordor for the funny image!
|
Member 3320 Level 5.11 Mar 2006
|
Remember, you can only have three configurations, Omnislash.
Thanks for the correction, nazpyro. Jam it back in, in the dark. |
Member 2043 Level 29.93 Mar 2006
|
Compare 1/2 and 3/4 (measurement 1) If measurement 1 is BALANCED... Then the oddball is in 5/6/7/8/9. Take off 4 and put 1/2/3 together. Check that with 5/6/7 (Measurement 2). If it's still balanced, compare either 1/2/3/4/5/6/7 with 8(Measurement 3). If that's balanced, 9 is the oddball. If not, 8 is the oddball. If Measurement 2 is Unbalanced, then the oddball lies within 5/6/7. Take note of the result of measurement 2. If 5/6/7 is higher than 1/2/3, the oddball is lighter. If 5/6/7 is lower than 1/2/3, the oddball is heavier. Now, Compare 5 and 6 (Measurement 3). If they're balanced, the oddball is 7. If they're not balanced, then it's either 5 or 6. If Measurement 2 told you the oddball is lighter, the lighter one is the oddball. likewise if measurement 2 told you the oddball is heavier, the heavier one is the oddball. If measurement 1 is UNBALANCED... Compare 1 and 4. (Measurement 2) If that's balanced, then the oddball is either 2 or 3. Compare 2 and 4 (Measurement 3) If it's unbalanced, then 2 is the oddball, if it is, then 3 is the oddball. If that's not balanced, then the oddball is either 1 or 4 obviously. Check 2 against 4 (measurement 3). If it's unbalanced, then 4 is the oddball. If it is balanced, then 1 is the oddball. There's nowhere I can't reach.
Last edited by Omnislash124; Sep 19, 2006 at 10:09 PM.
|
Member 3320 Level 5.11 Mar 2006
|
How ya doing, buddy? |
Member 2043 Level 29.93 Mar 2006
|
I am a dolphin, do you want me on your body? |
Member 41 Level 38.30 Mar 2006
|
 How ya doing, buddy? |
|
Larry Oji, Super Moderator, Judge, "Dirge for the Follin" Project Director, VG Frequency Creator
Member 2731 Level 1.34 Mar 2006
|
Hmm, I'm assuming that the odd egg is 'heavier' than the others.
If that's the case then you take 4 eggs and place 2 on each side of the scale. If they balance out, then that's 4 normal eggs. Repeat again with another 4 eggs and once again if they balance then the 9th egg is the odd egg. If in either the first or second measurement it turns out to be unequal, then the 'heavier' side will contain the odd egg and hence you just take those 2 and place one on each side and you'll have the odd 'heavier' egg. That would be in maximum 3 measurements i think but it the odd egg is 'heavier' :P What kind of toxic man-thing is happening now? |
Member 41 Level 38.30 Mar 2006
|
Omnislash124 ~ While I haven't seen that solution (because I never tried it where you don't know if the oddball is heavier/lighter), I checked yours and it works. Nice.
cookie ~ Yeah that works, but... If you know the oddball is heavier (or lighter), it can be found in a maximum of 2 measurements. So, assume the oddball is heavier. Now come up with a more efficient solution! Most amazing jew boots |
Member 2043 Level 29.93 Mar 2006
|
That's a pretty good riddle by the way, nothing but pure logic. I like those kinds of riddles. Riddles with some wierd catch or something random suck.
What, you don't want my bikini-clad body? |
Member 3320 Level 5.11 Mar 2006
|
Good work, omnislash. Anyone with a different solution?
Most amazing jew boots |
Member 41 Level 38.30 Mar 2006
|
I can't resist anymore, so I'm gonna put the 2-measurement solution given that the oddball is heavier.
Solution:
There's nowhere I can't reach. |
|
Larry Oji, Super Moderator, Judge, "Dirge for the Follin" Project Director, VG Frequency Creator
Member 2731 Level 1.34 Mar 2006
|
Okay, how about this solution:
Eggs: A,B,C,D,E,F,G,H,I place ABC and DEF if (ABC == DEF) then use the other 2 measurements to determine where in GHI is the odd egg else if (ABC != DEF) then remove A and D swap E and B /* this now means we're measuring EC to BF */ if ((EC > BF) && (ABC > DEF)) then /* this means E == B and C || F is the odd egg */ replace C with A if (AE > BF) then F is the odd egg else if (AE == BF) then C is the odd egg damn, the tabs don't show up... makes it hard to read the solution. How do I get the tabs to show up? How ya doing, buddy?
Last edited by cookie; Sep 25, 2006 at 03:37 PM.
|
Member 2043 Level 29.93 Mar 2006
|
Trying to put it into Programming Code? Yeah It's a pain since the tabs don't show.
There's an increase Indent button you can use in the Advanced one.... if (ABC > DEF) Then Blah. I am a dolphin, do you want me on your body? |
Member 634 Level 32.09 Mar 2006
|
Wow, just saw this one.
My answer: Alright, there are at least three ways to do this. Brute force is lame. Let's move on. The old, "half/half" is common, but let's do one better. Divide the eggs into three groups of three. Weigh them. If both are the same weight on each side, then the heavier egg is one of those of the three that were not weighed. If one side IS heavier than the other, than one of those eggs of that side is the heavier egg. Now, repeat. That means, take one egg each and leave out off the scale. If they weigh the same, then the heavier egg is the one not weighed. Else, the heavier egg will be the one that is shown by the scale. How ya doing, buddy? |
Member 14 Level 54.72 Feb 2006
|
My solution is a lot simpler.
Break all the eggs open into a bowl. Stir briskly and make an omelette. Now the problem no longer matters and you've got something much better than a math problem. What kind of toxic man-thing is happening now?  |
Member 41 Level 38.30 Mar 2006
|
True... but the problem doesn't provide you with a bowl. You'd have to break it onto the weighing scale, and then how you plan to cook it is beyond me. ;_;
FELIPE NO |
Member 3730 Level 13.52 Mar 2006
|
Great, I come to the Place of Laugh and games to take a break from work...and now I am hungry...Damn you Crash! I hope you can never cook those damned eggs of yours!
What, you don't want my bikini-clad body?
I forgot my old sig...
|
Member 5982 Level 14.90 Apr 2006
|
I just saw this just now. I didn't look through all the solutions, but I think I've got a good idea.
(This could be done much quicker had you said if the oddball were heavier or lighter) Pick 6 eggs at random put 3 on one scale and 3 on the other, if they balance your oddball is in the remaining three. If the scales don't balance pick either side and balance it with the remaining three (I'll call that *3)[we also know *3 is normal]. If *3 and your remaining pick balance you know the oddball is in the one you took off if *3 and the other side don't balance you know it's in the other group. You now are down to 3 suspects. You take two at random and take 2 from *3 if they balance the remaning one is the oddball. If they don't then you just balance each of the two 1 - 1 with an egg from * 3. Knowing if the egg is lighter or heavier definitely saves steps. Actually if you do it this way and you get lucky (i.e. the 3 eggs you don't select contain the oddball and you don't way the oddball in the 2 - 2 step) this can be done in two steps. At worst you'll do 5. Knowing if the egg is lighter or heaver means that at worst it'll take 4 steps. edit: To avoid seeing solutions I didn't see that we were assuming the oddball was heavier. Someone posted a solution for that, but my way will work even if you don't know whether or not it's lighter or heavier. Jam it back in, in the dark.
Last edited by Hotobu; Sep 28, 2006 at 09:27 PM.
|
eraemia 
nazpyro 
Mojougwe 
