Picking k numbers from 1 - 100

139 Views Asked by At

Assume A and B play a game with C.

C will pick a random number from $1$ to $100$, and A and B both pick $k$ different integers between $1$ and $100$ inclusive.

Say A picks $a_1, a_2, \ldots, a_k$, B picks $b_1, b_2, \ldots, b_k$, and C picks $c$.

Player A is said to win the game if $$\min(|c-a_1|, |c-a_2|, |c-a_3|) > \min(|c-b_1|, |c-b_2|, |c-b_3|)$$ (the example shown above is when $k=3$)

What's A best picks such that the winning chances for them are higher?

For $k = 1$ and $k = 2$, the answers are trivial, being $50$ or $51$, and $33/34$ and $66/67$ each.

For $k = 3$, are the answers $25, 50$, and $75$? And for $k = n$, are the answers between intervals of $\frac{100}{n+1}$?

If A and B both pick the same list of numbers, it's a tie.

1

There are 1 best solutions below

0
On

Lets choose from the interval $[0,1]$ instead from the numbers $1,\ldots,n$. You claim that choosing $\frac 1 3, \frac 2 3$ is optimal for $k=2$. But that is not true. Bob chooses $\frac 1 3-\varepsilon, \frac 2 3+\varepsilon$ and its chances to win are $\frac 2 3-2\varepsilon$.

For Alice it is better to choose $\frac 1 4, \frac 3 4$. If Bob chooses both numbers from $(\frac 1 4, \frac 3 4)$ he will win with probability of smaller than $\frac 1 2$, e.g with probability $\frac 1 2-2\varepsilon$ for choosing $\frac 1 4+\varepsilon, \frac 3 4 -\varepsilon$. If Bob chooses $\frac 1 4-\varepsilon, \frac 3 4 +\varepsilon$ the probability is $\frac 1 2-2\varepsilon$ , too. If one number is from $(\frac 1 4, \frac 3 4)$ and the other either $\frac 1 4-\varepsilon$ or $\frac 3 4 +\varepsilon$ then the probability is $\frac 1 2-\varepsilon$, too. All in all, the best numbers for Bob are $\frac 1 4$ and $\frac 3 4$, too.

These arguments can be extended to $k>2$ Alice should divide $[0,1]$ into $k$ subintervals of equal length and then choose the center of each subinterval. This means Alice should choose $$\begin{eqnarray}a_1&=&\frac 1 {2k}\\ a_2&=&\frac 3 {2k}\\ &\vdots&\\ a_k&=&\frac {2k-1} {2k} \end{eqnarray}$$