Tous les deux
Suppose there are 10 balls identical in appearance, where 8 of them each have a mass of x grams, and each of the other two ( x + δ ) grams. Now, δ ( > 0 ) is so small that the difference can't be detected using your own hands, and can only be detected by the precise balance scale you have been provided with. You can put any number of balls in each pan of the scale.
What is the minimum number of weighings you will need to make to guarantee the identification of both of the heavier balls?
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.
2 solutions
To prove it can't be lower than 4, just use the standard proof: There are ( 2 1 0 ) = 4 5 cases to be distinguished, and each weighing gives lo g 3 bits of information, so you need at least lo g 3 lo g 4 5 > 3 weighings, thus 4 weighings.
Log in to reply
Great! Thanks for the confirmation. :)
This is Brilliant™
Can you help by telling where you got this proof from and some other applications. Would be of help to me.
Log in to reply
This is a simple application of Pigeonhole Principle. Suppose we need to distinguish n cases. Each weighing gives 3 possible outcomes. Thus in total, if we perform k weighings, we get at most 3 k possible outcomes. We need to distinguish all n cases, so we need n ≤ 3 k (otherwise two cases will fall to the same outcome and we can't distinguish them). Taking logarithm of both sides gives lo g n ≤ k lo g 3 , or k ≥ lo g 3 lo g n .
If each weighing gives a different number of outcomes (for example, it's impossible to be equal, so only left pan heavier or right pan heavier), change the 3. And of course, n depends on the problem. Sometimes there are multiple cases but you don't need to distinguish them all; for example, if you have n balls, one of which is counterfeit (heavier or lighter), but you only need to find the counterfeit ball and not whether it's heavier or lighter, you need to distinguish n cases, not 2 n cases.
I think it can be done in 3 weightings. 1)Take 8 balls and place 4 balls in each pan. Case 1)If they weigh equal then we weigh the other 2 balls and identify the ball with more weight. In this case only 2 weighings are required. Case 2)If they weigh unequal then take the 4 ball which weigh more and place 2 on each pan. Take the balls which weigh more and place each on 1 pan you will identify the ball with more weight. In this case 3 weighing are required. So I think answer must be 3, if not please find error in my solution.
Log in to reply
There are two balls that are heavy, not one.
Further challenge: Is there a method with only four weighings, where the first step is not to put three balls on each pan?
Log in to reply
Yes; in fact, each of 2 vs 2, 3 vs 3, 4 vs 4, and 5 vs 5 can be the first step.
Log in to reply
Do you have a solution that has 5 vs 5 as the first step and then only 3 more steps? I haven't taken the time to work it out one way or the other, but I'm slightly surprised because if that first step balances, then you have 25 possibilities left -- just shy of 27, so future steps will have to be "very efficient" as one might say.
Log in to reply
@Peter Byers – That is indeed true, but it's still possible. Suppose we weigh ABCDE vs PQRST and it turns out balanced.
Weighing 2: ABPQ vs CDRS.
If left heavier: C, D, R, S are all light. One of A, B, E is heavy, and one of P, Q, T is heavy, but not E and T (that would make it balanced). Third and fourth weighings are simply A vs B, and P vs Q.
If balanced: Either A or B, and R or S, are the heavy ones; or C or D, and P or Q, are the heavy ones; or E and T are the heavy ones.
Weighing 3: AR vs CP.
- Left heavier: A or R is heavy; either way, we have the case "A or B, and R or S, are the heavy ones", except that B and S can't be both heavy. We're distinguishing AR, AS, and BR; just compare B vs S.
- Balanced: It's impossible for one from each side to be heavy, so A, C, P, R are all light. The remaining cases are BS, DQ, or ET; just compare B vs D.
Log in to reply
That is indeed true, but it's still possible. Suppose we weigh ABCDE vs PQRST and it turns out balanced.
Weighing 2: ABPQ vs CDRS.
etc.
Nice.
How did you get that log3 term?
PRE -
; separates two pans. The measurements are proceeding, with useful pan or both. a and b and heavy balls.
SOLUTION-
Choose 8 balls and measure.
-
Both balls get on the same pan.(4;2+a+b)
-
Each gets on different.(3+a;3+b)
Now choose 4 balls and measure.
1.1 Again, both get on same pan.(2;a+b) 1.2 Both get on different pan.(1+a;1+b)
2.1 Measure two times. One is heavier every time.(2;1+a)(2,1+b)
Now have 2 balls and measure.
1.1.1 You have your two balls.(a+b)
1.2.1 Measure two time. Each time you get your heavy ball.(1;a)(1;b)
2.1.1 Measure two times.Each time get a heavy ball.(1;a)(1;b)
Since any of case may occur thus we the max. of measurement we need i.e. for 2.1.1 or 1.2.1. The no. of measurements being 4.
A worthy attempt, but it's not complete.
This shows that 4 is possible. But unfortunately, you didn't show that 1, 2 or 3 can be the answer. Do youk now how to complete this?
First choose 6 balls at random and place 3 on each pan of the scale. There are two possible outcomes:
(A) If the two groups of 3 balls balances, then there are two possibilities: either all 6 balls have mass x or each group of 3 has one ball of mass x + δ . Now take one of these groups and weigh them against 3 of the remaining balls. This second group cannot weigh the same as the first, as either the first group has one of the heavier balls, in which case the second group is composed of just mass x balls, or the first group has none of the heavy balls, in which case the second group must have at least one of them. So looking at these two cases:
(i) if the second group is lighter, then the initial two groups each have one mass x + δ ball. For each of these two groups choose two balls to weigh against each other; if one ball is heavier then we have one of the heavier balls, and if the two balls balance then the remaining ball is the heavy one. So as each group requires 1 weighing to identify the heavier ball, the total number of weighings in this case is 4.
(ii) if the second group is heavier then it has at least one of the heavier balls. Now choose two balls from this group to weigh against each other. If they balance then either both are light or both are heavy, so weigh one against the third ball to see which is the case. If the third ball is heavier then that ball and the 10th ball remaining are the heavier ones, and if the third ball is lighter then the first two balls are heavy. Either way we have identified the two heavy balls in this case in a total of 4 weighings.
(B) Now if the initial two groups of 3 do not balance, then the heavier of the two has at least one of the heavier balls. Next, split the remaining 4 balls into pairs and weigh them against each other. As there is at most one heavy ball among the 4 either one of the pairs is heavier, in which case one of that pair is heavy, which will require one weighing to identify, and one of the balls in the first group of 3 will be heavy, which require one more weighing to identify, for total of 4 weighings. If the two pairs balance, then the first group of 3 has both of the heavy balls, which will require one more weighing to identify, resulting in a total of 3 weighings.
So in all cases we need no more than 4 weighings.
Note: I have tried other weighing sequences and ended with the same minimum, but was not able to find any way of getting the minimum down to 3. It may still be possible, so if you have found such a method please let me know or file a report so that we can get the correct answer posted, if in fact it is not 4.
Edit: As Ivan Koswara notes in the comments below, each weighing give lo g 3 bits of information, so at least lo g 4 5 / lo g 3 > 3 weighings are required. So as it is shown above that the identification can be done in 4 weighings, we can conclude that 4 is indeed the minimum.