Weight and Diets

This post is somewhat off point, but it has to do with why it is that some people don't ever seem to put on weight and others are in a constant battle to stay slim.

A NYT times article based on a new book by Gina Kolata suggests that we all have internal mechanisms that try to keep our body weight within a narrow range, and that this range is not the same across people. The way these mechanisms work is to slow down or speed up our metabolic rate depending on how much we eat. People who are naturally thin will rapidly lose weight if they put on pounds and vice a versa. Studies have shown that an individual's natural weight zone is genetically determined.

This doesn't really lead to an argument for abdicating responsibility for one's obesity --- but it does say that it's really much harder for some people to do anything about it. If we truly understood this it would affect the way we judge a person who seems more than a little bit on the heavier side. More importantly it would change the way many people judge themselves.

It is always a bit uncomfortable to talk about the fact that we all arrive with natural advantages and disadvantages but these days I see much more of it the popular science press. (The findings I just talked about are actually not recent but are only now finding their way into the NYT.)

For example, consider the more-or-less established view that men of south asian origin are much more likely than average to get heart attacks regardless of diet and where they live. Stories like this one abound. It suggests that any South Asian male who has waist bigger than 35 inches is almost certainly doomed.

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.

Toy Puzzle Solution

In my last post I posed the odd ball problem. In this post I'll solve it for 12 balls. This solution is almost identical to what is found in the excellent book by Mackay. In the next post, I'll show how to generalize the solution to more balls.

For 12 balls we start out with 24 possible hypotheses since each ball can be either heavy or light.

First, since all the balls look alike let's just number them 1 to 12 to tell them apart. Let's denote the hypothesis that ball 1 is heavier than the rest by 1+ and that it is lighter by 1-. Similarly denote 2+,2-, 3+,3- etc. Of course, only one of these 24 hypotheses can be correct. Our job is to find out which one in 3 weighings.

Let's call the three weighings W1, W2 and W3. Also, if we weigh balls 1,2,3 (in the left pan) against 4,5,6 (in the right pan), then we'll denote that weighing as 1,2,3#4,5,6. In general we can use this notation to describe any weighing. There are three possible outcomes of any weighing: the left pan is heavy, the right pan is heavy or the two pans are even. Let's just denote these outcomes as L, R and E respectively. We say O(W1)=L to denote that the outcome of weighing one is that left pan is heavier.

Now to the solution! Most people will struggle with various combinations of balls until they have either given up or stumbled on an answer. That's no fun! We are going to pick our weighings based on a very simple strategy:

Try to pick each weighing in such a way that it is equally likely for the outcome to be L, R or E.

Why this strategy? That's for the next post, but think about this way for now: You don't learn from expected outcomes but from unexpected ones. Anyway, this strategy will give us the solution to the oddball problem in three weighings:

The only weighing that results in equally likely outcomes is when you weigh four balls against four other balls. So we chooseW1= 1,2,3,4#5,6,7,8 . Clearly if O(W1)= E then the oddball is one of 9,10,11,12 and the probability of that is 4/12=1/3. That leaves 2/3 which is divided equally between the outcomes L and R. So this weighing matches our strategy since the probability of each outcome is 1/3. Now depending on what happens in W1:

1. O(W1)=E: Then the oddball is one of 9,10,11,12, i.e. there are only 8 remaining hypotheses (see how we eliminated 2/3 of the hypotheses?).
   
   Now for W2 we have to shoot for the same thing, i.e. make the outcomes L,R,and E as close to being equally likely as we can. Since the number of hypotheses is not a multiple of 3 we won't be able to get the outcomes to exactly equal but we can come close. There are several ways to do this --here's one:

W2: 9,10,11#1,2,3. Notice that we already know that 1,2,3 are not oddballs. So the probability of outcomes L,R and E are 3/8,3/8 and 1/4 respectively.

If O(W2) =E then the oddball is ball 12. All we have to do in weighing 3 is to just weigh ball 12 against any other ball, e.g. W3=12#1. If the outcome is L, then 12 is heavy and if the outcome is R then ball 12 is light.
If O(W2)= L then we know that the oddball is heavy and the remaining hypotheses are just 9+,10+,11+. Now the third weighing is easy. For example,W3= 9#10 will work. If L then 9 is the oddball, if R then 10 is oddball and if E then 11 is the oddball.
If O(W2) =R then this case is almost identical to the previous case except that the oddball is lighter.

2. O(W1)=L: We are left with the hypotheses: 1+,2+,3+4+,5-,6-,7-,8-. Now for the second weighing we want the outcomes to be as equally likely as possible. How about::
   W2=1,2,5#3,4,6? The probabilities of the outcomes L, R and E are 3/8,3/8 and 1/4 respectively which is as close to being equiprobable as you can get. Now if O(W2)=E then 7- or 8- are true. W(3)=7#8 will do the job. And if O(W2)= L we are left with 1+,2+ and 6-. Then W(3)= 12 for the third weighing identifies the oddball.
3. O(W1)=R: This case is very similar to case 2 and can be completed the same way.

The cool thing about this solution is that it all comes from a very simple strategy. But why does it work? Next time I'll talk about this and the solution to the oddball problem with N balls.