N balls and a scale

Question

The question of twelve balls and a scale is probably the best-known example of the "find the ball of a different weight" problem. But does it generalize? Is there a general way to find a weighing algorithm for $N$ balls on a scale where $N \ne 12$?

This is the variant where the direction of deviation is not known (one ball is slightly lighter or slightly heavier than the others) and the solution must both pinpoint the odd ball and indicate whether it is lighter or heavier.

Assume that for $K$ weighings, there will be no more than $(3^K - 3)/ 2$ balls to weigh, as that has been proven to be optimum.

Answer 1

Yes, there is an algorithm.

Oh, you wanted to know what the algorithm is? Here is one, which presents an algorithm but not all the reasoning behind it. For that, and a proof, and the variant where the odd ball must be identified but not the direction of its deviance, read Thomas Pornin's excellent presentation on the same question on Math Stack Exchange (which I used heavily while writing my answer here).

The core idea is that this problem works in threes. Each weighing involves three sets of balls: the left pane, the right pane, and the balls not being weighed. Each weighing has three possible results: lighter, balanced or heavier.

I'll start with the simpler variant where you know that the odd ball out is heavier than the rest (but not as heavy as two normal balls). The general idea is to weigh one third of the balls against another third, determine which set contains the odd ball, and repeat. But there's a big wrinkle: at the beginning, you don't know whether the odd ball is heavier or lighter, so unless the result of the weighing is “equal”, you're left with two possibilities. To compensate for that, we'll put slightly less than 1/3 of the balls on each pane.

Determine the number $w$ such that $(3^{w-1} - 3)/2 \lt N \le (3^w - 3)/2$, i.e. $w = \lceil \log_3(2N+3) \rceil$. This will be the number of required weighings.

In the first stage, weigh $(3^{w-1}-1)/2$ balls against the same number of balls.

• If the outcome is “heavier” or “lighter”, all the left-over balls are standard; apply the second stage to all the balls that were weighed, and put a marking on each of these balls to indicate whether it was on the lighter or heavier side (this will be used to tell whether the odd ball is lighter or heavier).
• If the outcome is “balanced”, then the odd ball is among the left-over balls, and all the weighed balls are standard; apply the third stage to the left-over balls.

In the second stage, we have a pool of standard balls. Set $(3^w-1)/2$ balls apart, and weigh half of the remainder against the other half, using a standard ball to complete the set if the size is odd.

• If the outcome is “balanced”, repeat the second stage with the left-over balls.
• If the outcome is “lighter” or “heavier”, then move on to the third stage (same principle as in the first stage).

In the third stage, all the balls involved have a mark which indicates whether they are part of the heavy group or of the light group. Put $\lceil N/3 \rceil$ balls on each side of the scale, taking care to put the same number of light balls on both sides (and also the same number of heavy balls).

• If the outcome is “balanced”, the odd ball is one that wasn't weighed. Repeat the third stage with the left-over balls.
• If the outcome is “lighter” or “heavier”, then the odd ball is either among the light balls on the lighter side or among the heavy balls on the heavier side. Repeat the third stage with the potential odd balls.

The process stops when there are at most two potential odd balls:

• If there is a single potential odd ball, it's the one.
• If there are two balls marked heavy, weigh one of them against a known-standard ball. (There will be one, courtesy of stage 2, except if you started with two balls, in which case the problem cannot be solved.)
• If there are two balls with different markings, weigh them against each other.

In all cases, the last weighing reveals the odd ball, and its marking indicates whether it is lighter or heavier.

Answer 2

As before in the original twelve-balls problem, we can do this with a fixed weighing schedule in pretty much the exact same way. It just takes a little more fiddling with possibilities to make sure you're putting an even number of balls on the scale for each weighing.

For example, with only 11 balls, the schedule might look like this:

1  2  3  4  5  6  7  8  9  10 11
R        R  L  L     L  L  R  R
   R  L     L     R  R  L  L  R
      R  L     L  R  L  R  L  R

Notice we're now using the LLL/RRR pair that we didn't use in the 12-balls case, and this case doesn't look nearly as symmetric as the cases before it because we had to fiddle around a bit. We couldn't do the problem just by removing one of the cases in the original weighing schedule, since that would result in at least one of the weighings having only seven balls placed on it, which cannot be divided evenly among the two pans.

---

For 3 balls (the maximum you can do with two weighings), it looks like this:

1  2  3
L     R
   R  L

For 39 balls and four weighings, it might look like this:

1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 
R           L  L  L           L  L  L           R  R  R     R  R  L     R  L  L     R  L  R     R  L  R  L  R  R  L  
   L        L        R  L     R        L  L     R  R     R  L  L     R  L  R     L  R     R  L  L  R  R  L  R  L  R
      R        L     R     R     R     R     R  R     R  R  L     R  L  R     R  R  L  L     L  L  L  L  L  L  L  L  
         L        L     L  R        R     R  L     R  R  R     L  R  L     L  L  L     R  L  R  L  L  R  R  L  R  R  

I'll leave it as an exercise to the reader to do the general cases from 4 to 10, and 13 to 38 balls.

Answer 3

I don't think there is a crisp way to describe it, but basically you round up to the next $K$ and find some balls to leave out of the strategy for $(3^K-3)/2$ The type of problem you can have is for $N=8$. If you weigh four vs four, they will not balance. The next step calls for you to use one of the known good coins, but you don't have any of those. If you had weighed three vs three to start (and they didn't balance) you have two known goods available. So start by weighing about $1/3$ of the coins against the same number and keep going.

Answer 4

You basically need N chances for No. of Balls Ranging from ((N-1)*3)+1 to N*3. i.e

1. Upto 3 Balls -> 1 Scale
2. 3 - 9 Balls -> 2 Scale
3. 10 - 15 Balls-> 3 Scale
4. 16 - 21 Balls-> 4 Scale And so on.