The game
We have $10$ cards faced down each numbered $1-10.$ For $1\$$ You may select any $2$ cards and I will tell you which is the the minimum card and its value. At any point you may stop the game and select a card and I will pay you that cards value in $\$$.
Example run
You picked $2$ cards for $\$1$ I told you the minimum was $9$ you then selected the other card and I gave you $\$10$
My attempts
We care only about the highest card we know the value of and the cards unknown to us. In which case we can either guess our highest value or randomly select one of the unknown.
We should also only ever compare with the highest card avaliable to us, even if its value is unknown . For example we compare cards A and B and are told A is the minimum value with 6 then we should only use B to compare future cards.
Smaller case studies
Consider we have only $2$ cards. Then we should randomly guess $1$ card for an expected value of $1.5$. Asking to be told the minimum (and have certainty of the $2$) costs us $\$1$ which is pointless as $1.5 > 2-1$
Consider now we have $3$ cards. We can randomly guess and be given and expected value of $2$. Or we can ask to compare 2 cards.$\frac{1}{3}$ of the time we know the exact position of the $3$ when we are told the minimum value is $2$ all other outcomes lead to an EV strictly less than $3$ hence we should not bother comparing any cards and just guess right away.
Consider now we have $4$ cards. We again can guess for an EV of $\$2.5$. Half the time we find the $1$ and are in a shifted version of the 3 card scenario in which case the EV is $3$. A third of the time our minimum card is $2$ in which case we should guess the card we compared with for an EV of $3.5$ (we have either a 3 or 4 with equal probability ( No other stratergy can have expected value 4.5 so no point seeing another card. ) And a sixth of the time we can grab the $4$ by being told the minimum card we saw was a $3$
This yields: $\frac{1}{2} 3 + \frac{1}{3} 3.5 + \frac{1}{6} 4 = \frac{20}{6} = 3 + \frac{1}{3} < 2.5 + 1 $ So we should just instantly guess!
I dont think this method will be very easy to scale up to n = 10. Can someone find a better way of doing this 🙂
Best Answer
(a sketch, too detailed for the comments)
Suppose you had $N$ cards.
For each $k\in \{1,2,\cdots, N\}$ we consider the strategy $\mathscr S_k$ to be "take the maximum of $k$ selected cards". We note that we can achieve this strategy by paying $k-1$ dollars, and sticking with the current max. $\mathscr S_1$ is, of course, just blind guessing. Letting $E_k$ denote the expected max of the $k$ selected cards, the value of $\mathscr S_k$ is $S_k=E_k-(k-1)$.
Now consider the special case $N=10$. Of course $S_1=5.5$ but we can do better. One round of information gets us to $E_2= 7.\overline 3$ so $S_2=6.\overline 3$ which is better than $S_1$.
Can we do even better? Well, let's consider $\mathscr S_3$. To get the distribution of the max $M$ it is easiest to compute the probability $P(M≤i)$ for $i\in \{3,4,5,6,7,8,9,10\}$. Then, of course, $P(M=i)=P(M≤i)-P(M≤i-1)$. Routine calculations yield $$\{P(M=i)\}_{i=3}^{10}=\{.008333,.025,.05,.08333,.125,.175,.2333,.3\}$$
from which we deduce that $E_3=8.25$ which implies that $S_3=6.25$ which is less than $S_2$.
This leads me to believe that $\mathscr S_2$ is optimal.
To stress: this is not complete. I believe, but have not shown, that the strategies increase to a max and then decrease thereafter. In this particular case, of course, all you need to do is to consider the other $\mathscr S_k$, which would be straight forward, if a bit tedious.
Note: complicating matters considerably, you are able to improve on $\mathscr S_3$ by only paying the second round selectively. For instance, if the first choice gets you a min of $9$, then you should obviously just take the $10$ and stop. Similarly, if the first choice gets you a min of $8$ (or maybe even less) it might well be better to stop. That sort of optional exercise can best be handled by backwards induction. though that's a bit messy even in the case $N=10$.