Alice and Bob card game

Question

I came across this puzzle online in an online Princeton thingy (course?):

Alice writes down two integers between 0 and 100 on two cards. Bob gets to select one of the two cards and see its value. After looking at the value, Bob commits to one of the two cards. If he chooses a card with the largest value, he wins; otherwise he loses.

Devise a strategy for Bob so that he guarantees to win strictly more than half the time.

I thought about it, and the problem is that we can't presume Alice is choosing random numbers (otherwise the strategy of Bob simply choosing the other card if known value is less than 50 would be sufficient).

Any ideas on how to approach this?

Answer 1

Bob should start by looking at one of Alice's cards at random: call the one he chooses $A_1$ and the other $A_2$.

Bob can choose an integer $B$ in $[1,100]$ uniformly at random so that $P[B=b] = \frac{1}{100}$ and then accepts the card $A_1$ if $A_1 \ge B$ but swaps to $A_2$ if $A_1 \lt B$.

This will give a conditional probability of $\frac12$ of selecting the larger of Alice's cards when both Alice's cards are less than $B$ or both are greater than or equal to $B$, and a conditional probability of $1$ of selecting the larger of Alice's cards when one of Alice's cards is less than $B$ and the other greater than or equal to $B$.

So if the mean absolute difference between Alice's cards is $d$ then the probability of Bob choosing the larger of the two using this strategy is $\frac12+\frac{d}{200} \gt \frac12$.

Alice would be wise to ensure her two numbers only differ by $1$, in which case the probability of Bob choosing the larger of the two is $0.505$.

Answer 2

You draw a number randomly ,$Z$, say from a $N(0,1)$ distribution with density $f(z)$ with positive probability on $(-\infty,0) \cup (100,\infty)$. If the number is outside $[0,100]$, choose one of the cards uniformly at randomly. Otherwise, if your card is less than the number you generated, switch cards. Else, keep the card.

• The first case gives you $\frac{1}{2} P(Z \notin [0,100])$ probability of being right.
• The second case gives you $\sum_{i=0}^{99} \frac{100-i}{100} P(Z \in [i,i+1])$.
• The third case gives you that you win with probability $\sum_{i=0}^{99} \frac{i}{100} \int_i^{i+1} f(z) dz$.

Answer 3

Here is a strategy that works even if Alice's choice is a pair of real numbers, and the choice does not have to be bounded.

Fix a strictly decreasing function $p:\mathbb{R}_+\rightarrow (0,1)$. Draw the first card with uniform probability. Read its value $x$ and switch to the other card with probability $p(x)$.

Suppose the cards contain $x,y$, with $x<y$. If the first card contains $x$, then Bob succeeds with probability $p(x)$. If it contains $y$, the probability of success is $1-p(y)$. So, the probability of success is $$ \frac{1}{2}(p(x)+1-p(y))=\frac{1}{2}+ \frac{p(x)-p(y)}{2}>\frac{1}{2}. $$