Solving the Oddball Problem with N balls

In the last post we solved the odd ball problem for 12 balls. Today I want to present a solution for N balls. I do not know of another general solution, but when N can expressed as (3^n-3)/2, there are very nice solutions here, here and here.

First, label the N balls 1 through N. Then mark each ball with a + and a – sign. These signs stand for the various hypotheses. For example the + on ball 1 stands for the fact that ball 1 could be the odd ball and it could be heavier than the rest. As we go through our weighings we erase these marks . Obviously when a ball has no marks left it isn't the oddball. We call all eliminated balls, good balls. A ball that isn't good is a candidate ball.

Our goal will be to eliminate as many marks as we can in each weighing. The marks we erase after a weighing depend on the outcome of the weighing, i.e. L,R or E (following the conventions of the previous post). Recall that in a weighing we put some balls on the left pan, an equal number of balls on the right pan and the rest of the candidate balls "on the side".

How Marks are Erased: If the outcome is E, then balls we just weighed are all eliminated and the balls on the side are the only candidate balls. If the outcome is L then erase any – signs on the balls on the left pan and erase any + signs on the balls of the right pan. The balls "on the side" are all eliminated as well as any being weighed that have no marks left. Similarly, if the outcome is R then erase any + signs on the L pan etc.

Again, the trick to solving this problem is to focus on marks rather than balls. Let m[k] be the number of remaining marks at the beginning of the kth weighing. For example, m[1]=2N. Since there are only three possible outcomes in a weighing you can't hope to eliminate more 2/3 of the marks after a weighing. The way to do this is to ensure that regardless of whether the outcome of a weighing is L,R or E you will be left with very close to 1/3 of the marks you had before the weighing, i.e. m[k+1] is about m[k]/3. For example, to ensure that this happens when the outcome is E, you want about m[k]/3 of the marks to be in balls that are "on the side".

Of course m[k] may not be divisible by 3. But notice that if you've got K things you can always divide them into three piles so that two piles have the same number of things and the third one is off by at most one thing. For example, if you have 6 things, all the piles have 2 things; 7 things give piles of 2,2,3 and 8 things give piles 3,3,2. We'll call this dealing into 3 piles
and to avoid confusion later refer to this d3p(K)=(p,p,q) where 2p+q=K and abs(p-q)<= 1.

Another potential complication is that in the weighing process you may come to a situation where some balls have 2 marks on them and others have just 1 mark. That's something we will avoid. In the beginning all candidate balls will have two marks on them. But the first time a weighing has the outcome L or R, each candidate ball will have exactly one mark on it. (To see this reexamine the way we marks are erased.) This condition will persist until we find the odd ball. So our method boils down to provide how to do each weighing, W[k] when each candidate ball has 2 marks (we call these AllEven weighings) and when each candidate ball has one mark (we call these PostEven weighings). The nice thing about this way of describing the method is that we don't have to specify a complicated tree of what to do which would make explaining things virtually impossible!

Both kinds of weighings take as a variable, k, the number the number of weighings. Also, the first weighing is always AllEven, so start the process by calling AllEven(1).

We denote O(W(k)) to be the outcome of weighing W(k) and it can take a value from L,R or E.

AllEven(k) All the candidate balls are marked with a + and a -

1. If m[k]>2 then let d3p( m[k]) =(p,p,q). p can be either odd or even, but the q must always be even since m[k] is even.
   
   1. W(k) :
      
      1. If p is even put p/2 balls on each pan and the left over q/2 is on the side.
         
      2. If p is odd put p balls on the left pan, p good balls on the right pan and q/2 balls on the side (you always have p good balls to spare for this)
         
   2. If O(W(k))=E then increment k and go back 1
      
   3. If O(W(k)) = L/R then increment k and call PostEven(k)
      
2. If m[k]=2 then W(k): Weigh the candidate ball against a good ball and then terminate.
   

PostEven(k): All the candidate balls are marked either + or – but not both.

1. If m[k]>3 then
   
   1. If there are even number of balls marked + put an equal number of them in each pan. Otherwise put 1 + ball on the side and split the remaining + balls over the pans. Repeat for the balls marked -. Now there are equal number of + balls in the L and R pans, and an equal number of – balls in the L and R pans. There are 0,1 or 2 balls on the side. Suppose there are b balls on each of the pans and s balls on the side.
      
   2. While (b-s> 1.) [i.e. keep repeating this step until b-s<=1]
      
      1. Remove a ball from the L pan and a ball of the same sign from the R pan and put both balls on the side.
         
   3. W(k): Weigh the balls as they are in the pans. (Note: if dp3( m[k])= (p,p,q) then there are p balls in each pan.)
      
   4. Increment k and Go back to 1
      
2. If m[k]<= 3 then it easy to terminate in one more weighing.
   

As an example, pick N=12. We start off by calling AllEven. Clearly h[1]=24. At the end of W(1), h[2]=8. If O(W(1))=E then we stay in AllEvens and W(2) will have 3 of the remaining candidate balls vs 3 good balls. W(3) is easy. If O(1)=L/R then we go to PostEven(2) etc. W(3) yields the oddball.

If N=(3^k -3)/2. Then h[1]= 3^k -3, h[2]=3^{k-1}-1,h[3]=3^{k-2}-1,….,h[k]=2 and therefore the oddball will identified in k weighings.

Also, if N= 3^k. Then h[1]=2*3^k, h[2]= 2*3^{k-1},…,h[k+1]=2, and therefore the oddball will identified in k+1 weighings.

For arbitrary N, notice that regardless of whether the kth weighing is AllEven or PostEven,: m[k+1]<=celing(m[k]/3). Note that ceiling(x) is the largest integer greater than equal to x.Thus each weighing eliminates the maximum number of hypotheses possible.

So to get to the bottom line: define h[k+1]= celing(h[k]/3), h[1]=2N. Then the min # of weighings required to identify the odd ball is the smallest K for which h[K]<=3.