**The game**

Lucy has $2n$ distinct white colored balls numbered $1$ through $2n$. Lucy picks $n$ different balls in any way Lucy likes, and paint them red. Lucy then giftwrap all the balls so that it is impossible to tell its color without opening its wrapping. Lucy does this before offering any of the balls to Alice.

Alice would like to get one of the red balls. Alice doesn't know which balls are painted red. Lucy will offer Alice the balls one by one, starting from ball $1$, until ball $2n$. Upon being offered each ball, Alice may either take the ball or pass it. If Alice takes the ball, Alice open the wrapping. If it is red, Alice takes it and the game ends -- otherwise, Alice will continue to be offered the remaining balls (unless all balls has been offered). If Alice pass the ball, the ball remains wrapped and thus Alice does not know the color of the ball, and Alice will continue to be offered the remaining balls. Note that it is possible for Alice not to get any red ball -- for example, if Alice choose not to take any ball.

Alice's goal is to

- Obtain a red ball with probability at least $1 - 1/n$ (that is, it is okay for her not to get a red ball as long as this probability does not exceed $1/n$), and
- Minimize the expected number of balls Alice take.

Lucy's goal is the complete opposite of Alice, that is:

- If it is possible for her to make Alice unable to obtain a red ball with probability at least $1 - 1 / n$, she will do so.
- Otherwise, maximize the number of balls Alice take in average (that is, the expected number of balls Alice take).

**Question**

What is the optimal strategy for Alice? What is the expected number of balls that Alice would take in the optimal case?

**Example**

When $n = 2$, Alice's goal is to obtain a ball with probability at least $1/2$. Here's an example strategy, which is provably optimal:

Decide which one of the four balls to open at random, and open that and only that ball. Clearly the probability that the opened ball is red is $1/2$, and the expected number of balls opened is $1$.

**My work**

Let $X$ be the expected number of balls Alice would take if both players play optimally.

*Upper bound on X*

I can proof a $O(\log n)$ upper bound on $X$ by letting Alice select $\log_2 n$ balls at random to open. The probability of Alice not finding any red ball is at most $2^{-\log_2 n} = 1/n$. Lucy would then paint the last $n$ balls red, and we have $X = O(\log n)$.

*Lower bound on X*

**Edit**: As domotorp pointed in chat, the proof in the pdf below for my lower bound is wrong because I wrongly use the assumption that E(x) and E(y) were independent. I don't see any immediate fix to the proof, so I will try to work on this again.

I proven a $\Omega(\log \log n)$ lower bound on $X$ in this pdf. I used a different terminology in the pdf: instead of having $2n$ balls, $n$ colored red, we have $2n$ bins, $n$ of which has ball inside.

**Motivation**

In the distributed systems settings, a rather common approach to guarantee that an algorithm is fault tolerant is by utilizing a bound on the number of possible failures. One of my supervisor's paper's algorithm works by utilizing a cheap algorithm that runs very fast if the number of failures is very small. To accommodate for larger number of failures, he decides to run this multiple times -- if with high probability (at least $1 - 1/n$) one of these runs have very few errors, then this algorithm will be much faster than the previously known one. At the moment, the paper utilize the $O(\log n)$ upperbound, but we wondered whether this bound is optimal.

A very nice implication is that if a strategy with expectation lower than $O(\log n)$ is found for this game, then the algorithm's complexity in the paper will decrease correspondingly. However, I strongly believe that it is more probably to prove $\Omega(\log n)$ rather than $o(\log n)$.

10more comments