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:
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 even
; and describe
the other ball as odd
. I tacitly assume you have some mechanism of
labelling the balls without interfering with their relative weights –
e.g. by putting each ball into a cloth bag, of negligible weight (or at least
the weights of the bags are equal, to within the tolerance of our balance),
each with a distinct label – so that you can keep track of information
about each ball separately, as you weigh different subsets of them against one
another. 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. Note that power(i, 3) is an odd natural, for every natural i,
so that (power(i, 3) −1)/2 is natural and, for positive i, so is
(power(i, 3) −3)/2.
I shall begin by showing that, for any natural number n:
We can then, with a brief digression about the signed ternary number system, consider the messy business of what this tells us about sets of balls that are not so exactly related to any power of three.
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. Note that one easy special case of this is when we have power(n, 3) balls and know either that they are heavier or that they are lighter than an equal number of even balls.
In the case n = 0,the statement of the problem is the statement of the solution; we have power(0, 3) = 1 ball; it is odd and we know (given that it is odd) 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(i, 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.
Suppose now, for some natural n, 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, 3) 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, from among those of which one is known to be odd; we are left with (power(n+2, 3) −power(n+1, 3))/2 = power(n+1, 3) of these 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.
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.
Now let us turn to the – seemlingly harder – problem of solving the last section's problem when we have to specify, before the first weighing, everything we are going to do. We can no longer use what we learned from earlier weighings to guide our choice of what to weigh next. To achieve this, we must either come up with another approach to solving the problem or find a way to include enough known even balls in each weighing, of the above solution, to ensure that we are also doing the weighing we would have done had each earlier weighing gone differently.
Let us attempt the latter strategy. The solution above has us, first, put (power(n+1, 3) −1)/2 in each pan, leaving the same number unweighed; such a sub-division clearly gains us most information. Each subsequent weighing uses fewer balls, but only because it served no purpose to include balls we'd learned, from earlier weighings, to be even. We can pad each later weighing with enough balls to make up (power(n+1, 3) −1)/2 in each pan, with equally many left out, by adding in balls known, from earlier weighings, to be even. Because each weighing had equal numbers of balls on each side, and each padded weighing also has equal numbers on each side, this inescapably adds equal numbers of known even balls on either side, making no difference to the weighing's outcome.
If the first weighing does not balance, we throw one of the unweighed (hence known even) balls in with the weighed ones. That next weighing would, in this case, have power(n, 3) balls in each pan; so we need to throw (power(n+1, 3) −1)/2 -power(n, 3) = (power(n, 3) -1)/2 extra known even (i.e. previously unweighed) balls in to each pan.
Written by Eddy.