3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Are you sure we can't assume Alice is choosing random numbers? The question doesn't really say that Alice wins or loses depending on Bob's performance, so she may not be actively trying to get Bob to fail. $\endgroup$ Commented May 22, 2014 at 5:19
  • 1
    $\begingroup$ Is Alice strategic? What is her payoff in this game? $\endgroup$
    – Herr K.
    Commented May 22, 2014 at 5:19
  • $\begingroup$ @KevinC Yes, Alice is strategic, and we are to presume that she's playing optimally to get Bob to lose. $\endgroup$
    – Chris
    Commented May 22, 2014 at 5:28
  • $\begingroup$ So this is a zero-sum game then. What happens if Alice writes the same number on both cards? $\endgroup$
    – Herr K.
    Commented May 22, 2014 at 6:35

3 Answers 3

3
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Awesome; thanks! $\endgroup$
    – Chris
    Commented May 22, 2014 at 18:23
1
$\begingroup$

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$.
$\endgroup$
5
  • 1
    $\begingroup$ I'm unclear as to why we'd use the standard normal distribution here. How is it related to the scenario between Bob and Alice and what does it mean to 'draw a number' from the distribution? $\endgroup$ Commented May 22, 2014 at 5:28
  • $\begingroup$ Its not particularly important which distribution we use, so long as it has positive probability outside $[0,\infty]$ and is continuous (so it doesn't take a particular value of a card with probability $1$). Gaussians just make the probabilities easy to compute. $\endgroup$
    – Batman
    Commented May 22, 2014 at 5:36
  • $\begingroup$ Don't you have to consider Alice's response to such a strategy? At any rate, why would the winning probability here be greater than half? $\endgroup$
    – Herr K.
    Commented May 22, 2014 at 6:05
  • $\begingroup$ Your method words, but $Z$ does not need to be continuous or go outside the range, and your choice of distribution is not particularly optimal (what is the probability if Alice always chooses $99$ and $100$ with your $N(0,1)$ suggestion?). All that is required is that the probability of Bob keeping a particular observed value is a strictly increasing function of that value. $\endgroup$
    – Henry
    Commented May 22, 2014 at 6:51
  • 1
    $\begingroup$ Hm, right. I just liked the continuous assumption so i wouldn't have to worry about an equality case. but the idea between our answers is generally the same. $\endgroup$
    – Batman
    Commented May 22, 2014 at 14:14
0
$\begingroup$

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}. $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .