Let's image that we have a table and 100 cards on it. One card has two sides: on the first hidden side there is a number, from 1 to 100, and on the other side there is nothing. All cards are arranged sequentially in random order. A player can take a card and ask a friend to compare the number from this card with the number from any other card. A friend can answer which one has the greater number written on it. The player never has the right to look at the number on the card. The player must choose one of the cards. The player can take a card only at the moment of taking, it is impossible to go back and compare with the future ones. The player chooses the final card on which the number N is written. If the number N is 100, then the player gets 20 for the whole game. If the number N is 98, then the player gets 50 for the whole game. If the number N is 96, then the player gets 100 for the whole game. For all other numbers, the player gets 0 points. The player also has the right not to choose any card, then the player gets 10 points for the game.
What algorithm can you suggest in which a player can get the highest average value of final points for a certain number of such games?
Here are my thoughts : Since we can compare any previous card with current card, we know that say for $n^{th}$ card current card is $i^{th}$ highest number among these $n$ cards. Let $E(i,n) = 20 P( \text{card is} 100 | i^{th} \text{ highest card among $n$ picked random cards} ) + 50 P( \text{ card is } 98 | i^{th} \text{ highest among card among $n$ picked random cards }) + 100 P( \text{ card is } 96 | i^{th} \text{ highest among card among $n$ picked random cards }).$
We stop the game and pick the $n^{th}$ card if $E(i,n) \geq \max(10, \max_{m \geq n+1} \sum_{1 \leq j \leq m} P( m^{th} \text{card is } j^{th} \text{ highest among $m$ random cards}) E(j,m).$
Try proving the optimality of above strategy. Let $S$ denote the variable which takes value $m$ if we decide to stop the game when $m^{th}$ card is picked.
Expected gain $= E_S[E(\text{ gain when $n^{th}$ card is picked and it's the $i^{th}$ highest card } | S] = P(S=n) E(i, n ) + \sum_{100 \geq m \geq n+1} P(S=m) E_j[E(j,m)] + 10 P( S >100).$
Our strategy is to pick the values of $P(S=m)$. So we pick $S$ to take the value which maximizes its coefficient in expected gain in the above expression.
Check if this is ok for you.