Weighing the odd ball out

There is a puzzle of form: you are given some apparently identical balls, told that all but one of them weigh the same and the other does not, given a balance and asked to find the odd ball out, and determine whether it is ligtht or heavy, in as few uses of the balance as possible. It has a quite general solution; I shall elaborate it here.

Since I am both a physicist and a pedant, let me state the problem more exactly:

• you are given a balance – implicitly with two pans, in which one may place things; when one does so, the balance shall settle into one of three states; one of which indicates that the contents of the two pans have equal weight; the other two of which indicate that the contents of one pan are heavier than the contents of the other pan;
• you are given several objects, all apparently alike
• you are told that all but one of these objects have weights so similar that, if equal numbers of them are placed in the pans of your balance, it shall declare their weights equal;
• you are told that the other one's weight differs from that of the others by enough that, if it is swapped for one of the others in such a balanced weighing, the balance shall indicate a difference in weight between its two pans;

but those neither of a pedantic disposition nor particularly concerned about the subtleties of observation should notice no material difference between this and the earlier informal statement of the problem. I shall refer to the objects as balls; I shall desscribe the balls whose weights are (for all practical purposes) equal as evan; and describe the other ball as odd. Define (: power :{naturals}) by: for any number n, power(0, n) = 1 and, for each natural i, power(1+i, n) = n.power(i, n); we shall only need this for n = 3.

I shall begin by showing that, for any natural number n:

• if we have isolated a set of power(n, 3) balls that includes the odd ball, and we know whether each is, if odd, light or heavy, then we need at most n more weighings to isolate the odd ball (thereby solving the problem);
• if we have isolated a set of (power(n+2, 3) −1)/2 balls that includes the odd ball; and have enough balls, that we know to be even, at our disposal; then we need at most n+2 weighings to isolate the odd ball and determine whether it is light or heavy;
• if we have a set of (power(n+2, 3) −3)/2 balls that includes the odd ball, then we need at most n+2 weighings to isolate the ball and determine whether it is odd or even.

We can then consider the messy business of what this tells us about sets of balls that are not so exactly related to any power of three.

Finding the odd ball, given its bias

Suppose, for some natural n, we have a set of power(n, 3) balls, one of which is odd, all others being even; and, for each ball, we know which of heavy or light it is, if it is in fact odd. I shall now show that we need at most n weighings to determine which is the odd ball.

In the case n = 0,the statement of the problem is the statement of the solution; we have power(0, 3) = 1 ball and we know whether it is lighter or heavier. Suppose, then, that we have some natural i for which we are satisfied that the above claim holds true; consider the case n = i+1.

Divide the possibly-light balls into three subsets as nearly equal as possible; one or two of these may have one extra ball. Likewise divide the possibly-heavy balls into three subsets as nearly equal as possible. Since the total number of balls, power(n, 3) = 3.power(i, 3), is a multiple of three, either each type divides equally or one type has one subset with an extra ball and the other has two subsets with an extra ball. In the latter case, combine the former's sub-set with an extra ball with the latter's subset without, and each of the former's sub-sets without an extra ball with one of the latter's sub-sets with an extra ball; and weigh the last two combined sets against one another. In the equal case, just combine each subset of one type with a subset of the other type; and weigh two of them against one another. Either way, the numbers of possibly-heavy balls in the two weighed sub-sets are the same; as are their numbers of possibly-light balls; and each weighed sub-set has power(i, 3) balls in it.

If the weighed sets balance, the odd ball is in the remaining combined set, of size power(i, 3). Otherwise, the odd ball is either one of the possibly-heavy balls in the heavy pan or one of the possibly-light balls in the light pan; and we have arranged that the number of possibly-heavy balls in either pan, plus the number of possibly-light balls in the other pan, comes to power(n, 3). We still know, for each ball, whether it is light or heavy, if odd; thus, we have reduced the problem, in one weighing, to the same problem we started with, but with i in place of n. We may thus induce that we need at most i further weighings to solve the problem, for a total of i+1 = n, as promissed.

Finding the odd ball and its bias, given enough even balls

Suppose, now, that we have (power(n+2, 3) - 1)/2 balls, one of which is known to be odd, all others being even, and at least power(n) balls that are known to be even. I shall now show that we need at most n+2 weighings to identify the odd ball and determine wether it is light or heavy. Set aside (power(n+1, 3) -1)/2 balls; we are left with (power(n+2, 3) - power(n+1, 3))/2 = power(n+1, 3) balls. Separate power(n, 3) of these and combine them with power(n, 3) balls known to be even; weigh these against the remaining 2.power(n, 3) balls.

If this balances, then we know the power(n+1, 3) balls are all even and the odd balls is one of the (power(n+1, 3) -1)/2 that we set aside. If n = 0, this is just one ball – which must then be the odd ball – and we have, at our disposal, at least power(n, 3) = 1 even ball to weigh it against, so as to discover whether it is lighter or heavier; thus we have our answer in n+2 = 2 weighings as promised. Otherwise, n is 1+i for some natural i, n+1 = i+2 and we can inductively apply what we are now establishing to conclude that we can identify the odd ball in at most i+2 further weighings which, together with the one we just did, makes i+3 = n+2 weighings, as promised.

Otherwise, we have some {P, Q} = {lighter, heavier} for which our 2.power(n, 3) balls of uncertain weight are P relative to our power(n, 3) known even balls and the power(n, 3) uncertain balls with which we combined them. Divide the P balls into two equal sub-sets and weigh them against one another. If they differ, then we know the odd ball is in the P one of them, and is itself P; we thus know whether it is light or heavy, and have isolated it among power(n, 3) balls, so we need n further weighings to establish which it is; taken with the two weighings needed to get here, this makes the promised n+2 weighings. Otherwise, the balance is even and all the balls in it are even; and we know that the power(n, 3) uncertain balls – that we earlier combined with an equal number of even balls – are Q; so we know that the odd ball is Q and we have isolated it in a set of size power(n, 3); we can isolate it in n more steps, for a total of n+2, as promised, again.

Finding the odd ball out

Now suppose, for some natural n, we are simply given (power(n+2, 3) -3)/2 balls and know only that one of them is odd, all others being even. Divide them into three equal subsets, each of size (power(n+1, 3) -1)/2; select two of these and weigh them against one another. If they balance, the third sub-set contains the odd ball; it is of size (power(n+1, 3) -1)/2 and we have at least power(n+1, 3) -1 even balls; for n = 0 this says we have the odd ball isolated and have more than one ball we know to be even, so we can weigh the odd ball against an even one and be done in 2 = n+2 steps; otherwise, n > 0 so n = i+1 and we have the odd ball among (power(i+2, 3) -1)/2 balls, and have power(i+2, 3) -1 > power(i, 3) balls we know to be even, so can use the last section's result to solve the problem in only i+2 = n+1 further steps, for a total of n+2.

Alternatively, the two subsets of size (power(n+1, 3) -1)/2 that we tested didn't balance; so we have power(n+1, 3) -1 balls, one of which is odd; for each, we now know whether, if it is the odd one, it is light or heavy. We also have (power(n+1) -1)/2 ≥ 1 balls that we know to be even. Add one ball that we know to be even to the power(n+1, 3) -1 among which the odd one lies; then we have power(n+1, 3) balls, for each of which we know whether, if odd, it is light or heavy. We thus know that we can solve the problem in at most n+1 further steps, for a total of n+2, as promissed.