mathematics - N balls and a scale

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

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.