8
$\begingroup$

This was posted Here and received a good answer, solving the general questions in either $n$ or $n+1$ moves, which is by just half a move on average "less good" than my manual solutions here.


Classic Case

I think we are familiar with the classic problem where we need to find one heavier ball among the rest identical lighter $n$ amount of balls using a scale and the minimum number of weightings.

For this problem we can for any case of any number of $n$ balls follow the same method; by evenly separating the balls in $3$ identical groups, of which two are placed on a balance instrument and the third aside. Then depending if the balance instrument is balanced or not, we can determine which of the three groups holds the heavier ball and repeat the process until we eventually eliminate the rest and find our heavier ball.

Thus this can be done in $k$ weightings, if we compare the total amount of balls to a power of three, such that the total amount of balls is $\le3^k$

This classic case was also discussed on math.stackexchange few times;
$(1)$How many times do we need to weight to find the only heavy ball out of $3^n$ balls?
$(2)$There are 8 balls which appear identical. However, 1 is heavier than the rest. How do you find the ball with 2 weighings?


Separating Heavier from the Lighter Balls

But I'm interested in a variation of this problem.

You have an even number of balls, $2n$ identical balls, and half of them are Heavy balls (weight $=x$) and the rest half are Light balls (weight $=y$). Thus, $x\gt y$.

Find a method to separate the balls into the "Heavy" and the "Light" box with the least weightings as possible. (Using a scale instrument, which from you can read exact difference between the total weight of the right and the left side of the scale.)

What is the minimum number of weightings required if we are given $2n$ balls?

What is the optimal method we can use for any case of $n$ to separate the balls with the least weightings as possible?


My Attempt So Far

I wasn't sure how to look at this problem in general, so I started to look for methods that will provide solutions for specific case of $n$ Balls.

I actually found it quite interesting and fun to work out the specific methods for specific cases, but it didn't really help me or gave me any new ideas for the purposes of the general questions.

"big-list" tag was added; Since I'm now more concentrated on looking for new solutions for specific cases instead of the general solution.

Feel free to take any case of $2n$ balls and work out your own solution for it and post it as an answer, any bit of progress could be useful.

For the following cases, I've found the following minimal number of weightings required;

  • 2 Balls = $1$ Weighting for sure
  • 4 Balls = $2$ Weightings for sure/on average
  • 6 Balls = $3$ Weightings for sure/on average
  • 8 Balls = $4$ Weightings for sure
  • 10 Balls $\approx4.86 $ Weightings on average

Below are the explained methods to get the solutions


$2$ balls case

  • Simply put one ball on each side of the scale and you know for sure which one is the heavy one and which one is the light one.

    Done in $1$ weighting.

$4$ ball case

I found two different methods.

  • $(1)$ Firstly place $1/1$ on the scale; It can either be balanced or weighted on one side.

    If it is weighted, you know $1$ heavy and $1$ light ball.
    Then simply weight the remaining $2$ balls and the outcome is the same.

    If it is balanced, you either have $2$ light or $2$ heavy balls.
    Compare one from the scale and one yet unweighted ball to find out.

    Done in $2$ weightings for all scenarios.



  • $(2)$ Firstly place $2/2$ on the scale; It can either be balanced or weighted on one side.

    If it is weighted, you can for sure tell that the heavier side contains $2$ heavy balls, and the other one $2$ light balls. Thus this scenario is done in $1$ weighting.

    If it is balanced, you have on each side $1$ light and $1$ heavy ball.
    If $A$ is the Heavy, and $a$ is the Light ball, we have $4$ possibilities: $$aA/aA$$ $$Aa/Aa$$ $$aA/Aa$$ $$Aa/aA$$ Then after switching $2$ inner balls we have the following scenarios possible: $$aa/AA$$ $$AA/aa$$ $$aA/Aa$$ $$Aa/aA$$

    Now you can see that after the switch and the second weighting, first $2$ cases weight on one side and resolve, and for the other two cases we simply weight one more time and compare the two balls on the same side to know which case we have. Thus this scenario is done in either $2$ or $3$ weightings.

    This solution is done in either $1,2$ or $3$ weightings, which have each $\frac{1}{3}$ chance of occurring if you calculate the odds of each scenario, which is $2$ weightings on average.

    Thus, done in $2$ weightings on average.

$6$ ball case

I found three different methods.

  • $(1)$ Firstly place $1/1$ on the scale; It can either be balanced or weighted on one side.

    If it is weighted, you eliminated $2$ balls, and then you can proceed to use any of the two methods provided for the case of $4$ balls to solve in the total of $3$ weightings, or $3$ weightings on average.

    If it is balanced, you replace the ball on the right side of the scale with one ball from aside, then you can consider $4$ scenarios; $$a/A+a\dots (AAa)$$ $$a/a+a\dots (AAA)$$ $$A/A+A\dots (aaa)$$ $$A/a+A\dots (aaA)$$

    Here you can notice $2$ weighted and $2$ balanced cases.
    For the balanced cases, you have all the balls sorted out and to find out which ones are heavy or light simply weight one from the each group.
    For the weighted scenarios, you can for sure identify $3$ balls weighted so far, and then simply weight $2$ of the remaining $3$ balls to identify each one of them.

    Done in $3$ weightings.



  • $(2)$ Firstly place $2/2$ on the scale; It can either be balanced or weighted on one side.

    If it is weighted, you "turn around" the scale so that the heavier side is on the left, then you can consider $6$ distinct scenarios: $$AA/aa\dots Aa$$ $$AA/aa\dots aA$$ $$AA/Aa\dots aa$$ $$AA/aA\dots aa$$ $$Aa/aa\dots AA$$ $$aA/aa\dots AA$$

    For the second weighting, replace the two balls on the left side with the two balls located aside. Now we have three possible scenarios. The left side will either get a bit heavier, get outweighted by the right side, or get a bit lighter. In each scenario, we have only $2$ cases left to consider, and to determine which one we are at, we simply need one more weighting.
    Done in $3$ weightings.

    If it is balanced, we can consider $8$ possible scenarios: $$Aa/Aa\dots Aa$$ $$Aa/Aa\dots aA$$ $$Aa/aA\dots Aa$$ $$Aa/aA\dots aA$$ $$aA/Aa\dots Aa$$ $$aA/Aa\dots aA$$ $$aA/aA\dots Aa$$ $$aA/aA\dots aA$$

    Then if you look at them as three pairs, you then in each pair take the left ball and move it into the next pair on the spot of its left ball, making a "cyclic exchange".
    Then making the second weighting afterwards to see the new eight scenarios of which there are: two balanced scenarios, three scenarios with the right side being heavier and three scenarios with the left side being heavier, as noted:

$$R: aa/Aa \dots AA$$ $$B: Aa/Aa \dots Aa$$ $$R: aa/AA \dots aA$$ $$R: Aa/AA \dots aa$$ $$L: aA/aa \dots AA$$ $$L: AA/aa \dots Aa$$ $$B: aA/aA \dots aA$$ $$L: AA/aA \dots aa$$

For the two balanced scenarios, to determine which one you got, it is easily noticeable that one more weighting is required.
For the right-side-heavy ones, replace the inner balls on the scale and you can consider three distinct changes and thus identify the scenario and all the balls: $$ (R\rightarrow L): aA/aa \dots AA$$ $$ (R\rightarrow B): aA/aA \dots aA$$ $$ (R\rightarrow R): AA/aA \dots aa$$


For the left-side-heavy ones, replace the right balls of each pair on the scale and you can also consider three distinct changes and thus identify the scenario and all of the balls: $$(L\rightarrow R): aa/aA \dots AA$$ $$(L\rightarrow B): Aa/aA \dots Aa$$ $$(L\rightarrow L): AA/aA \dots aa$$

Notice that we solved all cases in $3$ weightings.

Done in $3$ weightings.



  • $(3)$ Firstly place $3/3$ on the scale; It'll always be weighted on
    one side, and we can consider two scenarios if we look at the heavier side as the right side of the scale: $$AAA/aaa$$ $$(AAa)/(aaA)$$

    Now if we take a ball from one side, and replace it with a ball from the other side, we can consider four noticeable changes;

    The heavier side will either decrease in weight a bit, increase in weight a bit, become the lighter side, or there will be no noticeable changes.

    $1.$ If it decreases a bit in weight, we have only one possible scenario: $$[AAA/aaa]\rightarrow [(AAa)/(Aaa)]$$ That we had all balls sorted out in the first weighting, thus we are here done in just two weightings.

    $2.$ If it increases a bit in weight, we have only one possible scenario: $$[(AAa)/(aaA)]\rightarrow [AAA/aaa] $$ That we now have everything sorted out, again in just two weightings we can know for sure to identify each ball.

    $3.$ If it becomes the lighter side, we know that we replaced a heavy ball from the right side with the light ball from the left side, and that we have on each side one more light and one more heavy ball.
    We also know that we just observed the case where one side is heavier than the other by the $x-y$ which we will write as $(1/1)$ in one of the future scenarios because we will need this information there.
    Finally, with all this information we can consider four scenarios: $$|a|aA/|A|aA$$ $$|a|aA/|A|Aa$$ $$|a|Aa/|A|aA$$ $$|a|Aa/|A|Aa$$

    Now we remove the known balls, then replace the inner balls on the scale, then replace the left ball on the right side with the known heavy ball, then finally weight for the third time to get four distinct scenarios: $$ B: aA/|A|a$$ $$ L: AA/|A|a$$ $$ R(2/2): aa/|A|A$$ $$ R(1/1): Aa/|A|A$$

    Where $(2/2)$ notates the scale showing the difference $2x-2y$ and $(1/1)$ as I mention earlier, notates the difference $x-y$.

    Thus we can identify our scenario for sure, thus identifying all the remaining balls and their positions. Done in three weightings.

    $4.$ If there are no noticeable changes, we either replaced a light with a light, or a heavy with a heavy ball. We can then consider four scenarios: $$|a|AA/|a|Aa$$ $$|a|AA/|a|aA$$ $$|A|Aa/|A|aa$$ $$|A|aA/|A|aa$$

    Now we remove the known balls, then replace the inner balls on the scale, then replace the left ball on the right side with the known removed ball which is either light or heavy, then finally weight for the third time to get four new scenarios: $$L: AA/aa\dots$$ $$B: Aa/aA\dots$$ $$B: Aa/Aa\dots$$ $$R: aa/Aa\dots$$

    For the $R$ and $L$ scenario, we have one possible arrangement thus solving in three weightings, and for the $B$ scenarios, we need one more weighting to determine which arrangement we got so we can identify the balls.

    So, by this method we can solve in either $2,3$ or $4$ weightings which have in order $\frac{1}{5}, \frac{3}{5}$ and $\frac{1}{5}$ chances of occurring.

    Thus, done in $3$ weightings on average.

$8$ ball case

I've Found one method for $4$ weightings, by firstly weighting 1/1.

$10$ ball case

I've Found one method for $\approx4.86$ weightings on average.


* I wont bother explaining the the methods for $8$ and $10$ balls unless someone is working on this question and is interested or needs insight in my approach or on how I got these solutions since they are both similar to my methods for $2,4,6$ balls which have already been explained. *

Also, feel free to ask for clarifications on anything that doesn't seem clear.

$\endgroup$
  • 1
    $\begingroup$ Where it says "$30\%$" I think you mean $\frac13$. (By the way this is a very well-posed question.) $\endgroup$ – joriki Apr 28 '16 at 11:34
  • 1
    $\begingroup$ Also, you ask about the minimum number of weighings, but your further considerations show that you're actually interested in minimising the expected number of weighings. $\endgroup$ – joriki Apr 28 '16 at 12:11
  • 1
    $\begingroup$ @joriki Yes, by 30% I mean $\frac{1}{3}$. Well, I think it is interesting to find both "risky" (gives minimum number of weightings on average) and "safe" (always gives a minimal number of weightings) methods. $\endgroup$ – Vepir Apr 28 '16 at 18:19
  • $\begingroup$ This is the second time you bumped your question by a trivial edit. Please see this thread on meta regarding this practice. $\endgroup$ – joriki May 1 '16 at 8:41
  • 1
    $\begingroup$ @joriki Thanks for the note on that, I'll keep it on my mind from now on. $\endgroup$ – Vepir May 1 '16 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.