levy@princeton.UUCP (08/22/83)
Suppose someone has ten (real) numbers, written on slips of paper. This person will draw the slips one by one, and read the numbers aloud. It is your task to spot the highest number *as soon as it is read*, i.e. if you let it go, you lose. Of course you don't know a priori what the numbers are, so if you claim that one of the first numbers is the highest, you really don't have much information to go by, and if you wait until near the end, chances are you're going to miss the highest number. The question is: what is the best strategy to guess the highest number? What is the probability that it will work? What happens if instead of ten numbers you take a hundred, or one thousand, etc.? The answer to all three questions is very surprising. If you know it already, ou if you found it in three seconds, *don't post it*! Answer by mail. -Silvio Levy
levy@princeton.UUCP (08/23/83)
OK, all you guys who said you'd choose the first number. This gives you *exactly* 10% chance of being right, and I can assure you you can do better than that. In particular your strategy gets worse and worse when you have more numbers, whereas the optimal one does not. Think again! For those who say the question is unanswerable in the absence of more info, here's why not: The problem does not depend on the actual values of the numbers, only on their ordering. So we might as well assume they are 1 through 10, *as long as the strategy does not make use of this fact*. In other words, a strategy is a decision procedure (say deterministic) which after the i-th number has been drawer tells you whether to declare it's the biggest or not, *based only on the ordering of the first *i* numbers, and not on their values*. There are clearly only finitely many such strategies, so one (or more) must be optimal. Now of course if you have more information your chances are better! If you are competing agains someone who can only count up to 100, and s/he draws that number in the first attempt, you win with 100% certainty... -Silvio Levy