In: Math
There are 9 balls out of which one ball is heavy in weight and rest are of the same weight. In how many occurrences will you find the heavy ball?
There are 9 balls total named A1 A2 A3 A4 A5 A6 A7 A8 A9
Presently we will partition every one of the balls into 3 groups
Group1 – A1 A2 A3
Group2 – A4 A5 A6
Group3 – A7 A8 A9
1. Now measure any two gatherings. We should expect we pick Group1 on left half of the scale and Group2 on the correct side.
So now when we measure these two groups we can get 3 results.
1. Weighing scale tilts on left - Group1 has a heavy ball.
2. Weighing scale tilts on right - Group2 has a heavy ball.
3. Weighing scale stays adjusted - Group3 has a heavy ball.
Lets expect we got the result as 3. i.e Group 3 has a heavy ball.
2. Now measure any two balls from Group3. Lets expect we keep A7 on left half of the scale and B8 on right side.
So now when we measure these two balls we can get 3 results.
1. Weighing scale tilts on left - A7 is the heavy ball.
2. Weighing scale tilts on right - A8 is the heavy ball.
3. Weighing scale stays adjusted - A9 is the heavy ball.
Let us assume for simplicity that we do indeed know in advance whether the oddball is heavier or lighter.
Take note of the significance of three Groups :
Given three balls and the knowledge that one of them is an oddball, only one weighing is required to identify the oddball (see step 2 in each scenario above; weighing two of the three is sufficient to figure out which one is the oddball). Note encourage that this manage holds even at a progressive level: given three "gatherings of three balls" (i.e. A1 A2 A3, A4 A5 A6, A7 A8 A9 above) and the information that one of them contains a odd ball, just a single weighing is required to distinguish which gather contains the crackpot (see stage 1 above; measuring two out of the three gatherings of three is adequate to restrict the area of the weirdo to one of the three gatherings). Given this group of three, one more weighing is required to identify the oddball, so that with nine balls to start, two weighings are required, as above. Following this pattern, it is easy to show that if we are allowed n weighings, then we can find the oddball amongst 3n balls.
We then have to weigh either of A1 or A2 against A3. As a concrete example, suppose we find A1 < A2. Then we weigh A1 versus A3. If we find A1 < A3, then A1 is the oddball (and lighter). If we find A1 = A3, then A2 is the oddball (and heavier).
So up to two weighings are required to resolve an oddball from a group of three. oddball amongst half as many balls as before, or approximately 3n/2.
In fact, with n weighings we can only find and classify an oddball amongst (3n−1)/2 balls.
Finally as a result, if we are to be able to identify the oddball with unknown bias, we have to be able to do it based on only 3n−1 pieces of information.
At last, imagine a scenario in which we don't know ahead of time whether the crackpot is heavier versus lighter AND we additionally need to order its inclination as either. This is the hardest variety of the issue, yet the thinking is comparable. The majority of the above thinking helps through, yet now three out of the 3n conceivable results of n weighings give no data: when all weighings adjust (as previously), yet additionally when either all weighings are left overwhelming or all weighings are correct substantial. These last two results never again give the required measure of data, since while they would permit the ID of the odd ball, they would not enable us to characterize whether the crackpot was heavier or lighter. Along these lines, for this situation, given n weighings the greatest number of balls among which we can both distinguish and arrange a odd ball is (3n−3)/2.