|20-CS-110-001||Introduction to Computer Science||Fall 2010|
|Put positive distinct numbers on n pieces of paper, upside down on a
table. Game: pick up a paper and turn it over; stop at some point.
If you stop at the maximum number, you win otherwise you lose. What
strategy gives you about 1/2 probability of winning?
Case of 2 numbers only: pick 1st one, Pr(max number is 1st) = 1/2