It's cool to balance the eggs. Part II
There is a total of 9 eggs, out of which 8 have identical weights and one has a different weight. We do not know if the different egg is lighter or heavier.
Using a balance, what is the minimum number of weighings required to guarantee that you'll be able to determine the egg with different weight?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
10 solutions
I have to sheepishly thank you for pointing out explicitly to remember the 2nd weighing--I kept missing that little gem.
Log in to reply
yes i figured out all of it but that and i was confused how you could do scenario 3 with only 3 weighs. when he said how i felt a little silly for not figuring that out
We just need to find the egg. Heavy or light isn't mentioned.
Not so lucky, you would still need a third weigh to find if the single egg is heavier or lighter than the other eight
I agree with this - after second weighing you will either know the odd egg, but not if it is heavier or lighter, or you will have two eggs that do not balance. Since you do not know if the odd egg is heavier or lighter you have to make a third weighing to find the odd egg.
I missed the important fact that we don't know if the egg is heavier or lighter.
The answer is incorrect, the problem never states whether we need to determine if the egg is heavier or lighter, just find it. And if we say the minimum number of weighs then we have to assume best case scenario. Best case is just two. 3 is not the correct answer.
Log in to reply
The best case scenario logic doesn't apply. The question asks for the minimum number of weighs to guarantee determining the egg with a different weight, implying a 100% chance of finding it regardless of the case. Thus, this actually assumes the worst-case scenario which would require a minimum of 3 turns.
minimum means here least weighings covering all scenarios not just best case.
Split the eggs into three groups of three each. Balance any two groups.
Case 1 :They balance.
The third group contains the odd one . Weigh any two eggs from the odd group. If they are equal then the third one is odd. Else weigh it again using the last one of the group .With these weighings we can find the odd one.
Case 2 : They don't balance.
Balance the lighter group with the left aside group(which now clearly has no odd egg). If they balance, then we will know which group has the odd egg and also that the egg is heavier . Similarly if they don't balance we can know that the odd one is lighter. Now from the odd group,weigh any two eggs.If they balance, the odd egg is the left out one. If they don't the odd is the one which is heavier or lighter as found from previous observations .
Hence total number of weighings is 3.
In Case1 if they balance, the third group has the odd one,weigh the two from the third group, if again the balance, the third one in the third group is the lighter one, else the one in the lighter side will be lighter one.. hence three weighing is not needed
Log in to reply
It doesn't says whether the odd egg is lighter or heavier.So three weighings is necessary.
Log in to reply
The question states that 8 are identical in weight and 1 is lighter. So out of the final group of three when you know where the lighter one is you choose any of the 2 eggs. If one is lighter then that is the lighter egg. If not, then the one you didn't balance must be the lighter one
Log in to reply
@Jason Jiang – The question said, "8 have identical weights and one has different weight," and "different" could be either lighter or heavier. The question has never mentioned the "different" egg MUST be lighter than the rest. Please read the question one more time carefully.
yes ....i also thought the same...third reading not required
The author did not explain the situation clearly. If you cannot use visualization then you cannot split them into groups otherwise you would be able to visualize that they are in groups. From the authors description, you assume that you are taking these eggs from a bag (which you cannot see into) and when you're done weighing those eggs you put them back into the bag where they are mixed up so you never know which eggs you just weighed. Ultimately you would never know which egg is different since when you do find an uneven measurement you have to put those eggs back without knowing which one is different. Problems like these lead to assumptions which leads to assumed answers, no one wins
There should only be 2 weighings in total. The first will narrow the choices from 9 eggs to 3, and the second will tell you which of the 3 is the odd egg out.
If you balance 4 eggs on each side and they balance then you are left with one which is odd weight. Hence in this case you need 1 try. Otherwise 3 is the right answer if the four eggs on each side don't balance.
Log in to reply
While the case you outlined would require only one balance (and Suresh Tharayil's case requires only two balances), it can be safely assumed that the author meant "What is the minimum number of balances you must make to GUARANTEE you find the odd egg in ALL CASES."
I've learned that on this site, it is often the case that the problems' authors do NOT describe the question perfectly; that is, frequently, the author makes some assumption (or uses some particular shade of meaning) that is not explicitly stated. You've got to read between the lines a bit, and in this case, given that neither 1 nor 2 is a possible answer, you've got to try to deduce what the author actually meant.
While I agree that the question should've been written more precisely so that no assumptions or subtext must be analyzed, it sort of adds another layer of reasoning to the problem! "I found a case in which only 1 (or 2) balances would identify the odd egg, but neither of those answers is a possible choice... so, did the author mean something slightly different? Is he just flat out wrong?" etc.
Cheers :)
Log in to reply
Since it's minimum, it should be one. You could even be sure that the left over egg was different if you balanced two of a group of four on both sides of the balance.
Yes but if they are unbalanced then you will have to take the unbalanced group of 4 eggs and split them into two groups of two eggs. Once you weigh these two groups you will find out which two has the unbalanced egg and have to weigh these two eggs to find the culprit. So in best case your algorithm works better but the 3 groups of 3 works better on average.
Actually. After the first weighing, you still don't know which group has the odd egg, since u don't know if the egg is heavy or light
I agree and that is the problem with this question. It's worded so that 1 is the correct answer.
Technically speaking, you only need one weighing to determine the light egg, with 4 eggs in each pan and the light egg left over. The worst-case scenario is three. It should be noted that there is another problem like this one which uses coins instead of eggs, and claims that 2 is the correct answer.
The coin problem is different because it tells you the coin is lighter. This one just says the weight is different.
Shouldn't both questions have the same answer?
Log in to reply
No because one tell you if it's lighter or heavier but this one doesn't tell you.
the question is not asking whether or not you can get lucky and choose the right egg, it is asking what the minimum number of times you can weigh the eggs is, with 100% accuracy each time. The lowest possibility for this is two. You weigh two groups of three, and if one of them is lighter, then you weigh one of the eggs in that group with another from that group, and if the two are the same, the lighter one is the one you left out.
I was confused about the answer too because I literally just did the coin question-
I think the worst case scenario is 2 If we group the eggs in 3-3 groups and weigh two groups and if the group that weighs lighter could be identified Then one last weighing is required to identify the lighter egg
Moreover, if you put two eggs in the balance, one which is normal, and the other one is light weighted, it is easily determined that the side where balance will be more leaned is the normal weight one, since the odd one out has less weight than the normal one.
Log in to reply
How do you know that the odd one out is lighter than the rest?
You need 2 split the eggs in 3, wight two groups , if they are equal, take two eggs from the remaining group and mesure, if they are equal the remaining egg is the odd egg
How can yu commit(if the two groups are unbalanced) ...that which group contains the odd egg...as we dont know that the odd egg is heavier or lighter than the others...
There are nine eggs and any could be heavier or lighter giving 18 possibilities.
The balance can give one of three results: left down, right down or balance.
Two weighings would give 3 2 = 9 possible combinations.
Three weighings would give 3 3 = 2 7 possible combinations.
So we can see that two weighings will not be enough, and three should be plenty, even without working out a detailed method. Assuming we do go on to work out a method in three steps we can be confident that there is no solution using fewer.
You have to be a little bit carefull with this counting of possibilities as you are only required to find the odd egg. Not whether it is heavier or lighter. Which in principle reduces the number of possibilities you have to distinquish between. However the only time this happens is if the odd egg you identify has never been weighed. As this can only be true for at maximum one egg (it is not possible to distinguish between 2 eggs that have never been weighed) this reduction is at most relevant for 1 egg and thus the number of possibilities is reduced by 1 (at maximum). For 14 eggs instead of 9 eggs in the basket there is then 2 14-1=27 possibilities and interestingly enough it is actually possibly to come up with a weighing scheme with 3 weighings to find the odd egg if you have (or can borrow) an extra egg you know is not odd. In this case you would say there where 2 14=28 possibilities, but only 27 combinations. Let me go over the details in the simpler case with just 2 weighings and a basket with 5 eggs one of which is odd and you may borrow a normal egg. Here you say there is 10 possibilities, but only 9 combinations. In the first weighing you weigh egg 1 and 2 against egg 3 and the normal borrowed egg. If the weight is not balanced you weigh egg 1 and 2 against each other in the second weighing. If the first weighing is balanced you weigh egg 4 against egg 1 (or the borrowed egg or egg 2 or 3). Here the combination where both weighings balances corresponds to the fifth egg being odd, but you do not know whether it is lighter or heavier. For all other combinations you know which egg is either heavier or lighter.
You may hypothesize that the maximum number of eggs you can find an odd egg among with the help of n weighings is (3^n+1)/2 if you can borrow a normal egg and (3^n-1)/2 if you are not allowed to borrow a normal egg. This is certainly upper limits as your argument shows, but can they be attained for n larger than 3. I have not checked. That (3^n-1)/2 is an upper limit if you can not borrow a normal egg follows from that in the first weighing you can at maximum leave (3^(n-1)+1)/2 eggs unweighed and there has to be an even total number of eggs on the scale.
Wouldn't the minimum to guarantee a solution (not getting lucky) be two? split into three groups of three, if they equal then measure the two of the remains three in the last group, if they equal then the odd egg out is it. and if they don't equal you know where the.... never mind, you wouldn't know if the odd egg is heavier or lighter... I get it now
No minimum does in fact mean getting lucky. The answer is two, the question is wrong.
Yeah it would be two.
You take the 9 eggs, split them into 3 groups of 3.
Weight Group 1 and group 2.
They balance: then group three has the egg.
They DON'T balance: which ever side is weighed down had the odd egg.
With the knowledge of the group with the odd egg. You now repet the process but only with signal eggs.
Log in to reply
Omg..icthe two groups dont balance.....how can yu get to know which group is containing the odd egg...... Plz read the question first....it doesn't say that the odd egg is lighter or heavier as compared to the others.....
In fact the original version of the problem did mention to find out the odd egg and also determine whether it is lighter or heavier. Let us suppose the eggs are numbered from 1 to 9. This leaves us with 18 possibilities depending upon which egg is odd and whether it is heavier or lighter.
We will divide the eggs in three groups of threes and the first two weighings will narrow down the possibilities and identify the group with abnormal egg and also tell us whether it is lighter or heavier. 1. Weigh one group against the other. There are two possibilities a. It balances out thus telling us that the abnormal egg is in the third group and it is either lighter or heavier thus the possibilities coming down to 6. b. One side is heavier meaning either the odd one is on that side and it is heavier or it is on other side and is lighter. 2. a. Weigh the third group against any of these "normal" groups. If it is heavier then the odd egg is heavier thus narrowing the possibilities down to either of the three eggs being heavier. b Replace the heaver side with three remaining eggs. There are two possibilities. i. It will balance out meaning that the odd egg was among the three we removed and it is heavier. ii. Heavier side remains heavier meaning that the abnormal egg was on the other side and it is lighter. So we have now identified the group of three eggs with the abnormal one in it and also found out if it is heavier or lighter. 3. Now take two eggs from the three which have been identified as containing the abnormal one and weigh them against each other (we suppose this group was heavier but would work equally well if was lighter only replacing the word heavier with lighter in this part of solution). If they are equal then the third one is abnormal and we knowit is heavier. Otherwise the heavier of the two is the abnormal one.
Split 8 eggs into piles of 3,3, & 2 eggs each.
-
weigh first and second pile together, if they are same, then take one egg from last pile and weigh it with any one egg from previous piles, if they are same then the remaining egg from last pile in the different. ( Takes 2 tries to find the different one, best case scenario). Weigh any of the egg in the winner set with any other pile egg to determine whether its heavy or light (3 tries)
-
In case of the piles from the previous is heavy, take two eggs from that pile and make one new pile. Take the remaining egg and any one egg from the lighter pile to form second new pile. Weigh the two piles, if they are same then the remaining two eggs have the lighter egg, take any one egg from that and any egg from the previous to weigh them, if they are same then the last remaining egg is the lighter one. (3 Tries).
-
In case, the second pile is heavy in previous then the egg selected from heavy pile is heavy one (2 Tries).
-
In case, the first group is heavy, then weigh the eggs together in that pile, the heavy egg is the heavy one (3), but if the weigh comes out to be same, the egg from the light pile in the second new pile is the light one (3 Tries).
At max, 3 tries will give us the heavy or the light egg.
Split the eggs to three groups of 3: A,B, C: First, balance A and B: if they are balanced you know that C is the odd one. To make a short cut. You may determine whether the odd egg is heavier or lighter by balancing group C with either A or B and observing whether group C is heavier or lighter. Then, taking group C and balancing two of its members. if they balance, the third egg is the odd one. Otherwise, you can determine which one is the odd based on your previous observation of which group is heavier (C or A) . The second scenario when group A and B don't balance, you will make a second step observing the balance between A and C. From which, you can determine which group is odd and whether the odd egg is heavier or lighter than the rest. Then, balancing two eggs of the odd group will reveal the odd one (as you now know whether the odd egg is heavier or lighter).
Two balances are enough; split the eggs in 3 groups of 3 and balance 2 groups and there are 2 posibilities: ~1 one of the two groups weights more and in this case you balance 2 eggs from that group ~2 the two groups have the same weight=> the third one is heavier => weight two random eggs and if those are equal=> the third egg is heavier
But we dont know that the odd egg weighs less or more than the others do......so there is a need to get what actually the weight of rhe odd one(lesser or more)....and for that...we have to use the weing machine again
The answer is 2.
I think it's 2. The "correct" answer here is wrong!
No the answer is 3. Because at the end of 2nd weighing we would be knowing that one of those 2 weighing eggs is lighter than another one. But we dont exactly know that the third egg which is outside the weighing machine is actually lighter one or heavier one. So to determine exact anomaly, we would have to measure third egg also. Thats why this need to be done with 3 attemps at least.
Log in to reply
Andere 2 has to be right!
I think 2 is the correct answer in this question
The answer is 2
There was a question about coins and I thought the answer was 3 but it was 2. Now we've changed to eggs and suddenly it takes 3 weights! Wtf!
The question is worded tricky. Had the question stated that one egg was lighter or heavier then the answer would definitely be 2 but since it says one egg has a "different weight", unless we got lucky, we would need to run an additional test to find out if by "different" they meant heavier or lighter.
Split the eggs into 3 groups of 3; groups A, B, and C.
Scenario 1; 1st weigh: Weigh A and B. If either those two balance then you know that group C has the odd egg. 2nd weigh: Take 2 of the 3 eggs from group C and balance them; again if they balance you know the 3rd egg is the different one. *Congratulations you got lucky and did it in 2 weighs *
Scenario 2; 1st weigh: Balance A and B. If either of those two balance then you know the group C has the odd egg. 2nd weigh: Take 2 of the 3 eggs from group C and balance them; if they don't balance you... 3rd weigh: Weigh the 3rd egg against one of two and find the different one. (If they balance you know it's 1/2 eggs you first weighed, if they don't balance the odd egg will do the same thing with the 3rd egg that it did with the other egg you first weighed it with). *3 weighs *
Scenario 3; 1st balance: Balance A and B. If they don't balance... 2nd weigh: Weigh one of them against C. If the one (A or B) that you chose balances with C then you know the other is the off group. Remember if the off group went up or down, this will be important for the... 3rd weigh: Weigh 2/3 eggs from the off group, if they balance, you know it's the 3rd egg. If they don't balance then you know it's one of the two you are weighing. (Going back to remembering your result. If the off group is heavier or lighter the same will apply to the off egg) *3 weighs * I hope this made sense.