This Question was originally posted [Here](https://math.stackexchange.com/questions/1762437/separating-heavier-from-the-lighter-balls), where I'm more interested in the methods for manual solutions yielding $n$ or less moves on average.


I wanted to post it here as well, to see what the people of mathoverflow think about it. 




---


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. 


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



> 
> You have an even number of balls, $2n$ identical balls.   
>  Half of
>  them, $n$ amount of balls, are "Heavy Balls" and the other half are
>  "Light Balls".
> 
> 
> 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?
> 
> 
> 


For my progress on the specific cases of $n$ so far, check the original question linked [Here](https://math.stackexchange.com/questions/1762437/separating-heavier-from-the-lighter-balls).



Separating Heavier from the Lighter Balls
In the comments, Emil Jeřábek and Terry Tao have given an asymptotic lower bound of $4n / \log\_2 n$. 


For the upper bound, $2n$ is trivial, obtained by weighing each ball individually. Here is a solution which only requires $n+1$ weighings. 


Let $h$ be the weight of a heavy ball and $\ell$ be the weight of a light ball. We consider the version where we do not even know $h$ and $\ell$ beforehand. Let $B$ be the set of balls. Group the balls into $n$ pairs $(x\_1,y\_1), \dots, (x\_n, y\_n)$. For each $i$, we weigh $y\_i$ versus $B \setminus \{x\_i,y\_i\}$. The four possible weight differences are 


* $nh+(n-3)\ell$
* $(n-1)h+(n-2)\ell$
* $(n-2)h+(n-1)\ell$
* $(n-3)h+\ell$


which correspond to the possibilities $(\ell,\ell), (h, \ell), (\ell, h), (h,h)$ respectively. 


There are cases to consider depending on how many weight differences we observe. 


If we observe $4$ weight differences, then we know the type of each $(x\_i, y\_i)$, so $n$ weighings suffice.


If we observe exactly $1$ weight difference, then all pairs are of type $(h, \ell)$ or all pairs are of type $(\ell,h)$. We can determine which type by weighing $x\_1$ versus $y\_1$. 


If we observe exactly $2$ weight differences, then since there are the same number of heavy balls as light balls, we must have $(x\_i,y\_i) \in \{(\ell, \ell), (h,h)\}$ for all $i$ or $(x\_i,y\_i) \in \{(\ell,h), (h, \ell)\}$ for all $i$. We can determine which by weighing $x\_1$ versus $y\_1$. 


If we observe exactly $3$ weight differences, then $(x\_i,y\_i) \in \{(\ell,\ell), (h,h), (h, \ell)\}$ for all $i$ or $(x\_i,y\_i) \in \{(\ell,\ell), (h,h), (\ell, h)\}$ for all $i$. Note that in both subcases, the types $(h,h)$ and $(\ell,\ell)$ both appear. Moreover, we know which pairs correspond to $(h,h)$ and $(\ell, \ell)$ since they correspond to the smallest and largest of the $3$ observed weight differences, respectively. It now suffices to weigh $x\_j$ versus $y\_j$ where $(x\_j,y\_j)$ is a pair corresponding to the middle weight difference. 


