20-CS-110-001 Introduction to Computer Science Fall 2010

Numbers Puzzle

    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

       
    solution