# Monty Hall's Revenge

At first glance, it appears that no matter which bag you pick, your chances are the same: 1/100. However, once you have opened some bags, you know something. Since you obviously won't pick the second bag if it is less than the first, or the third if it is less than either of the first two (etc.), since you know you can't win, you now have information you can use to improve your odds. So, this best strategy is to open some number of bags, and then pick the next bag that has more money than all the previous ones.

How many should you pass on? By calculating the probabilities for each number of bags passed, you can find the highest probability (around 37%) for passing on 37 bags. This number can also be found by noting that it is the highest number of bags that can be passed on such that the odds of the most money being in one of the first x bags is still greater than the odds that the most money will be found in the last 100-x bags *and be picked*. This amounts to finding the smallest x with:

x/n > x/n * (1/(x+1) + ... + 1/(n-1)), where n=100 in this case.

This solution is a simplification of the puzzle; it is actually not so obvious that this is the best strategy. Also, when dealing with discrete values of money, we have additional information. For example, in the case of 2 bags, knowing how much money is in the first bag actually allows us to choose the richer bag with >50% probability. However, these considerations do not appear to affect the solution to a great extent.