levy@princeton.UUCP (08/31/83)
Several people came up with the right solution to this puzzle, namely letting go M numbers out of the N and then picking the first one which is bigger than the first M (for M=[N/e]). Since they also provided a proof that this value of M is optimal, I will not repeat it. Unfortunately, I do not know of any proof that this strategy is indeed optimal in the universe of all possible (deterministic, number-independent) strategies. If anybody knows of one, please post it. Ed Shepard suggests a slightly different strategy, but I did not understand its wording. As far as I can understand it, it consists in letting go by the first M *positive* numbers and then picking the first number bigger than those However this gives a probability of less than .39 for M=1, N=10, even assuming that positive and negative numbers are equiprobable (which is not warranted by the wording of the problem). I should say that "choose ten real numbers at random" doesn't make much sense because there is no uniform distribution of probabilities over the whole real line; what I mean is "choose then real numbers according to some distribution of probabilities, but don't tell the guy what the distribution is". I still think a strategy that works almost 40% of the time for this problem is almost miraculous. --Silvio Levy
ark@rabbit.UUCP (08/31/83)
This problem appeared many years ago in Gardner's column in Scientific American. I thought that the solution he gave was to let the first sqrt(N) numbers go by and then pick the first that was bigger than any of them. This was claimed to be optimum.