0

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?

Greg Martin
  • 78,820
Andrey Valitov
  • 1
  • Welcome to MSE. Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or be closed. To prevent that, please [edit] the question. This will help you recognize and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. – José Carlos Santos Dec 09 '22 at 07:26
  • Is the player allowed to compare 2 cards and pick one of them per game ? After picking one card does the player continue the game of picking another card ? – Balaji sb Dec 09 '22 at 07:53
  • @balaji-sb, The player takes the next card, after which he has the right to compare with any previous one, without knowing the exact numbers on these cards (you can only find out the result of the comparison). He can either take the current card and end the game with the corresponding final score (described in the text of the question), or move on to the next card. You cannot go back and choose a final card. – Andrey Valitov Dec 09 '22 at 12:42
  • When a player picks a card, can he compare the currently picked card with all of his previous cards and know the results of all the comparison or he is allowed to do a single comparison by picking exactly one of his previous cards and compare it with current card and move on to next card without further comparison based on current card ? – Balaji sb Dec 10 '22 at 05:53
  • @balaji-sb, the player picks up a card and can compare it with any previous card any number of times. – Andrey Valitov Dec 10 '22 at 09:38

1 Answers1

1

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.

Balaji sb
  • 4,357
  • Sounds good and hope it works, but I don't understand how we can calculate probability of any term in E(i, n) formula? For example, ( card is 98|ℎ highest among card among picked random cards )? – Andrey Valitov Dec 26 '22 at 10:21
  • 1
    I will think about existence of any simple formula for $P(\text{ card is } 98 |....)$ but i suggest to first check if strategy is optimal. – Balaji sb Dec 26 '22 at 10:56