5
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ A simple lower bound: each weighting has at most $2n+1$ possible outcomes, hence you need at least $\left(\log\binom{2n}{n}\right)/\log(2n+1)\sim2n/\log_2n$ weightings. $\endgroup$ – Emil Jeřábek supports Monica May 6 '16 at 16:43
  • 8
    $\begingroup$ You can improve this bound asymptotically by a factor of two using Shannon entropy. We can assume (for the purposes of lower bounds) that the heavy/light distribution is uniform, so the Shannon entropy is $\log_2 \binom{2n}{n} \sim 2n$. Each measurement actually has an entropy of at most $\sim \frac{1}{2} \log_2 n$ due to concentration of measure (the answer is concentrated in a region of width about $\sqrt{n}$). This gives an asymptotic lower bound of $4n/\log_2 n$. $\endgroup$ – Terry Tao May 6 '16 at 17:57
  • 1
    $\begingroup$ What is the outcome of the weighting, a numerical value or a decision, which of two sets of the balls is heavier? In the classical version of the puzzle it is just a comparison of weights. If in your version the outcome is a precise weight, then the complexity might also depend on the properties of the weights, i.e. whether the heavier ones weigh an integral, rational or irrational multiple of the lighter ones. $\endgroup$ – Manfred Weis May 7 '16 at 14:29
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ That is great! So overall this solves the $2n$ cases in either $n+1$ or $n$ weightings. So far in my original question I've posted some "manual methods" for specific cases which seem to need exactly $n$ weightings or exactly the average of $n$ weightings up to the case of $10$ balls which I've found to do in either $4$ or $5$ weightings I believe, which averages out at $\approx 4.86$ weightings thus is even less than $n$, on average. But I think I need to double check and revise all my methods so far, and hopefully come up with something to follow the pattern of exactly $n$ weightings or less. $\endgroup$ – Vepir May 7 '16 at 6:59
  • 1
    $\begingroup$ I would be interested in the answer to a modified question in which each weighing operation (on a pan balance, say) returns just either heavier, lighter or equal of the candidate sets--not their weight difference. $\endgroup$ – David G. Stork May 7 '16 at 17:11
7
$\begingroup$

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}

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.