levy@princeton.UUCP (08/26/83)
Well, the best submission so far (with a proof of why it works) is Jon Sieber's:
Let the first N/2 numbers go by, then choose the first number which is bigger
than all the first N/2. This gives you at least a 25% chance, because...
You are bound to be right if the biggest number is in the second half, and
the second biggest is in the first half.
However, that's not the whole story...
If neither the second or the biggest number are in the first half, but still
the biggest number comes before anything else that is bigger than everything
in the first half, you still win...
So this is a pretty good strategy... But it can be improved (along the same
lines). Feel free to post your solution now. My solution will come in a
few days (when I have worked it out).
-- Silvio levy