Optimal algorithm for finding the odd spheres

Say we have $N$ [$3 \le N \le 100,000$] spheres indexed as $1,2,3,\cdots N$,all of them have identical weight apart from one.We have to determine which sphere it is (index) by using only the pair of scales.

We could solve this problem by weighing repeatedly,but I am obviously interested weighing as minimum as possible so my question is what could be the optimal algorithm for this task?

Solutions Collecting From Web of "Optimal algorithm for finding the odd spheres"

This looks like a generalization of the classic $12$ ball problem.

You should be able to modify Jack Wert’s wonderful algorithm, (which was designed for the case when $N= \dfrac{3^m – 3}{2}$) to work for any $N$. I believe I had made an (incomplete) attempt when someone asked this on stackoverflow.

Note that the numbers $\dfrac{3^m – 3}{2}$ are special, in the sense that they are the turning points.

In the variant of the problem where you are also required to tell if the odd sphere is heavier or lighter, for $\dfrac{3^m -3}{2} \lt N \le \dfrac{3^{m+1}-1}{2}$, the optimal number of weighings can be shown to be $m+1$.

If you are only required to find the odd sphere and not necessarily figure out if it is heavier or lighter, the turning points are $\dfrac{3^m -3}{2} + 1$.

For a complete treatment, we have to consider all the combinations with
some variant parameters. The base problem: given $n$ balls, one being
“deviant” (not the same weight than the $n-1$ others), how to find the
deviant ball in at most $w$ weighs ? Or, similarly, what is the maximum
number $n$ of balls for which the deviant ball can always be identified
in at most $w$ weighs ?

The variant parameters are:

  • The balls may be “marked”. A ball which is “marked heavy” may be
    deviant by being heavier, but not lighter. We can consider a variant
    problem where all balls are individually marked heavy or light
    (independently of each other). The problem in which you know a
    that the deviant ball is heavier is a subcase of the “marked
    balls” problem (i.e. it is the “marked balls” problem where all balls
    are marked “heavy”).

  • You may be asked to identify the deviant ball and to give its
    deviance direction (i.e. you also need to find out whether the
    deviant ball is heavier or lighter).

  • Possibly, an extra “standard” ball is given, guaranteed to be

We’ll first see the “marked balls” problem because it is an essential
step of the full treatment.

Marked balls

First, some important notes:

  • With marked balls, identifying the deviant ball implies identifying
    the deviance, automatically.

  • If you have only one marked ball, then the problem is solved with no
    weigh at all: if there is only one suspect, then it is the culprit.

  • If you have two marked balls and they bear distinct marks (one is
    marked heavy, the other is marked light), then the problem is
    unsolvable — unless you have a standard ball available, in which
    case you just have to make a weigh between that standard ball and one
    of the potentially deviant balls.

  • Each weigh may yield only 3 different results, so with $w$ weighs you
    may reach at most $3^w$ distinct conclusions. Thus, the problem
    cannot be solved (reliably) if $n \gt 3^w$.

It so happens that the “marked balls” problem can be solved for all $n$
up to that $3^w$ limit (assuming the presence of a standard ball if
$n = 2$). This is demonstrated with the following recurrence:

  • With $w = 0$ (no weigh at all), you may indeed solve the problem with
    $n = 3^0 = 1$ marked ball.

  • With $w = 1$ and two marked balls with the same mark, just weigh one
    against the other; if they have distinct marks, use the extra
    standard ball, as explained above.

  • If $w = 1$ and three marked balls, then two of them (at least) have
    the same mark. Weigh one against the other; this yields the result.

  • If $w \gt 1$ and $3^{w-1} \lt n \leq 3^w$, then you can assemble two
    sets of balls of size $\lceil n/3 \rceil$, taking care to put the same
    number of “heavy” marks in both sets (which implies that you also put
    the same number of “light” marks in both sets). Then weigh one set
    against the other. If the balance tilts to the left, then the deviant
    ball is one of “heavy” balls from the left scale or one of the
    “light” balls from the right scale. If the weigh result is balanced,
    then the deviant ball is in the set of balls which you put in neither
    set. Either way, you end up with at most $3^{w-1}$ suspect balls,
    $w-1$ weighs, and at least one ball which is definitely non-deviant,
    i.e. a “standard ball”. Recurrence applies.

Unmarked balls

Consider $n$ unmarked balls. Your first weigh will result in either a
balanced result, or an unbalanced result. If the result is balanced,
then the problem is reduced to that of $w-1$ allowed weighs with all the
balls that did not take part into the first weigh; and the balls used
in the first weigh are now known to be all “standard balls”. If the
result is unbalanced, then all balls involved in the weigh are suspect
but can all be marked, so this brings us back to the problem of marked
balls (and the balls which were not used in the first weigh are now
known to be standard).

Let’s call $f(w)$ the maximum number of unmarked balls which can be
processed in $w$ weighs, assuming that an extra standard ball is
available. For now, we suppose that we want to identify both the ball
and its deviance.

$f(1) = 1$. Indeed, with only one weigh, you get only three conclusions,
so you cannot process two balls, because two balls mean four
possible conclusions (first ball is heavy, first ball is light, second
ball is heavy, second ball is light). With one ball, you just weigh it
against the extra standard ball.

If $w \gt 1$ and you have $n \gt f(w-1)$ balls, then isolate $f(w-1)$
balls, and split the remainder into two subsets of equal size (if there
is an odd number of remaining balls, add the standard ball). Do a weigh
between these two subsets. If a balanced result is obtained, then
recurrence applies (you have $f(w-1)$ unmarked balls and $w-1$ weighs).
If an unbalanced result is obtained, then all the balls involved in the
first weigh are now “marked” (except of course the extra standard ball,
if it was added). This leads us to the following relation:
$f(w) = f(w-1) + 3^{w-1}$.

Thus, $f(w) = (3^w – 1)/2$ (you can verify it fulfills the recurrence
relation and the starting point $f(1) = 1$).

What if you don’t have an extra standard ball to begin with ? Then
you will not be able to make the first weigh with $3^{w-1}$ balls, since
that’s an odd integer, and a weigh involves an even number of balls. So
you have to use only $3^{w-1}-1$ balls. However, after this first weigh,
you have one or several “standard balls”, so you are back to the previous
problem. Thus, unavailability of an extra standard ball means just
decrementing by one the maximum number of processable balls.

What if you are not interested in identifying the actual deviance
direction, but just in finding out which ball is deviant ? Then all of
the above still holds, except for the starting point. If you call $g(w)$
the maximum number of unmarked balls which you can process under these
conditions, then $g(1) = 2$: with two balls, just weigh one against the
extra standard ball; with three balls, you have to include two suspect
balls in the first weigh, but you will not known which is the culprit
since they are unmarked. It follows that $g(w) = f(w) + 1$ for all $w$.


If you are allowed $w$ weighs, then you can find the deviant ball and
its deviance among a maximum of $(3^w-3)/2$ balls. If you are not
interested in the deviance direction but only in identifying the deviant
ball, then you can process one extra ball. If a “standard” extra ball is
available, then you can process one extra ball. These two “one extra
ball” increments are cumulative; thus, with 3 weighs, you can process up
to 12, 13 or 14 balls, depending on whether you have an extra standard
ball, and whether you are interested in the deviance direction.

Extra conditions: if no “standard” extra ball is provided, then the
problem is unsolvable if:

  • there are one or two balls and you want the deviance direction;

  • there are exactly two balls and you are not interested in the
    deviance direction.

Apart from these two edge cases, all number of balls no greater than the
maximum can be processed (there is no “hole”).

If $N = 3^n$ is a power of three, then we can do it $n+1$ weighings:
First, assume that the odd ball is heavier than the others (this is just to simplify the exposition; we will come back to this). Now label all the balls from $0$ to $N-1$, in ternary notation. For each ternary digit position, weigh all the balls with $0$ in that position against all the balls with $2$ in that position, leaving out the remaining balls (with 1 in that position). The result tells you (assuming that the odd ball is heavier) the ternary digit of the odd ball in that position: $0$ if the $0$’s outweigh the $2$’s; $2$ if the $2$’s outweigh the $0$’s; and $1$ if they are equal.
So now you have the ternary expansion of the odd ball, assuming that it’s heavy. If that assumption is wrong, and the odd ball is light, then the number of the odd ball is obtained by flipping all the $0$’s to $2$ and vice versa. To find out which of these two candidates is the odd ball, just weigh one of them against a ball that is known not to be odd.

This doesn’t work if $N$ is not a power of three, because in general the number of balls with $0$ in a given position is not the same as the number of balls with $2$ in that position. So we can’t weigh them against each other. But we can fix this by the simple device of splitting the balls into two equal heaps, numbering one heap upwards from $0$ and the other heap downwards from $3^n-1$, where $3^n$ is the smallest power of three that is $\ge N$. (If the number of balls is odd, label the left-over ball with $11…11$.)

My guess is that this procedure is optimal when $N$ is a power of three, but otherwise we can sometimes do better; for instance, if $N=4$, we only need two weighings to identify the odd ball (but we won’t always know whether it is heavier or lighter).

Edit This solution shows how to solve the problem in $n$ weighings for any $N \le 3^n$ when we know whether the odd ball is heavier or lighter. Now we can put this together with Moron’s proposed solution (linked to in Moron’s answer) to get a complete solution in $n$ weighings when $N \le (3^n-3)/2$. (This solution also tells us whether the odd ball is heavier or lighter.)