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
priori 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
non-deviant.
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$.
Conclusion
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:
Apart from these two edge cases, all number of balls no greater than the
maximum can be processed (there is no "hole").