Problem: A sovereign wants their advisor to choose the largest number from among 100, and the advisor sees each number only once and has to decide on the spot if they want to choose that number or not. Each number is drawn uniformly from [0,1]. What should the advisor's strategy be?
My thinking was, if they see a number $x$ on the $r$th turn, then they choose that number if it's the highest they've seen so far, and $1-(1-x)^{100-r} < .5$, because if there's a greater than 50% chance there's something better, then they should continue looking at future numbers. However, the answer is that $x$ should be greater than the solution to the equation $$x^{100-r} = {100-r \choose 1}x^{100-r-1}(1-x) + \frac{1}{2}{100-r \choose 2}x^{100-r-2}(1-x)^{2} + ... + \frac{1}{100-r}{100-r \choose 100-r}(1-x)^{100-r} $$
Apparently, the RHS is computing the probability of choosing the correct option if we pass $x$, which is different than my approach (computing probability of seeing something larger than $x$), but I don't see how it can be correct. If there are $n$ numbers bigger than $x$, is it really the case that I have $\frac{1}{n}$ chance of choosing the correct number? Would I not have extra information once I reach a larger number (i.e., how many more numbers are left, etc.)? It seems too simplistic to assume it's uniform.
Any intuitive explanation of this would be great!
Thanks.