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