Separating Heavier from the Lighter Balls

Question

This Question was originally posted Here, 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.

Answer 1

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.

Answer 2

The answer is indeed asymptotic to $4n/\log(n)$, but I don't know of an elementary or easy construction for this upper bound. I believe simple probabilistic-method type constructions do not work.

This is also phrased as a "coin-weighing" problem. One point to keep in mind is that we can think of each weighing of $k$ balls as simply learning how many of the $k$ are light versus heavy. Thus you can rephrase your problem as follows: There is a special unknown subset $S$ of $\{1,\dots,2n\}$, where $|S| = n$, and we wish to determine $S$. At each step, we can query any $T \subseteq \{1,\dots,2n\}$ and learn $|S \cap T|$.

I find these references in the tutorial/lecture by Galvin[1], where he attributes the upper bound to (independently) [2,3] and the lower bound to (independently) [4,5]. Note that in his formulation there are only $n$ coins rather than $2n$ (hence the bound is $2n/\log n$), and it is not promised how many are heavy or light (so in particular the upper bound holds for the case where half are promised to be heavy).

This is also addressed in this MO question[6], but I'm not sure where a factor $2$ has gone missing in that answer.

---

[1] http://arxiv.org/abs/1406.7872

[2] D. Cantor and W. Mills, Determination of a subset from certain combinatorial properties, Can. J. Math. 18 (1966), 42–48

[3] B. Lindstr¨om, On a combinatorial problem in number theory, Can. Math. Bull. 8 (1965), 477-490.

[4] P. Erd˝os and A. R´enyi, On two problems of information theory, Publ. Hung. Acad. Sci. 8 (1963), 241–254.

[5] L. Moser, The second moment method in combinatorial analysis, in “Combinatorial Structures and Their Applications”, 283–384, Gordon and Breach, New York, 1970.

[6] Guessing a subset of {1,...,N}