You are at the grocery store buying a bag of oranges. The oranges are pre-bagged and all bags are sold at the same price.

All bags have the same number of oranges, but they do not weigh the same. You would not like to be cheated, or in other words, to not buy a bag below the median weight.

You begin by grabbing a bag with each hand to compare them. Once you decide on the heavier one you discard the one that feels lighter, keeping the one that feels heavier in your other hand, and pick up another bag with your free hand to make another comparison and continue the process.

Given that you are right about which bag is heavier 90% of the time (for simplicity assume your chances of misjudging the heavier of two bags are independent of their weight difference). How many bags will you have to pick up to be 85% certain that you are not being cheated?.

The number of bags to choose from is very large and there are no bags whose weight is equal to the median weight.

I think that the probability of not being cheated can be written as a recursive function.

Let F(n) be the probability of not being cheated after n comparisons.

F(0), of course, is .5, as the first bag is just as likely to be below or above the median.

Now, F(n) is related to F(n-1) in the following way:

F(n)=F(n-1)/2 + .9/2

The reasoning behind this equation is that the new bag is either on the same side or the opposite side of the median.  If it's on the same side, then the bag will stay on the same side of the median.  If it's on the opposite side, there is .9 probability of getting the bag above the median, no matter which bag that happens to be.

This recursive function can be rewritten as follows:

F(n)=.9 - .4(.5^n)

This sequence looks like this:
.7, .8, .85, .875, .8875, ...

So 85% is reached after the third weighing (4 bags are picked up).

Edited on June 5, 2005, 7:31 pm

Posted by Tristan on 2005-06-05 19:30:30