Following the same strategy as Dr Xorile, I wrote a quick programming solution to this problem. The goal is to define a function $p_{n,k}$, the probability of winning with $n$ numbers left, if you choose the $k$-th number.
p[n_, k_] := p[n, k] = 1/n + (k - 1)/n (1 - p[k - 1]) + (n - k)/n (1 - p[n - k])
p[0] = 0;
p[1] = 1;
p[n_] := p[n] = Max[Table[p[n, k], {k, n}]]
I define the auxiliary function $p_n$ as the probability of winning with $n$ numbers if you choose ideally. I also assume that each number is equally likely to be correct. (This is not true in real life: for example, people rarely choose multiples of ten because they don't seem "random.")
With this function we can break $p_{n,k}$ into three mutually exclusive events:
- You guess the correct number. This happens with probability $1/n$ (and in this case you win with probability $1$.
- You guess high. This happens with probability $(k-1)/n$. Your opponent goes next, and since there are $k-1$ numbers left he has a probability to win of $p_{k-1}$; your probability of winning in this scenario is therefore $1-p_{k-1}$.
- You guess low. The reasoning is the same as above, except there are $n-k$ numbers remaining so the probability of this event is $(n-k)/n$ and your probability of winning is $1-p_{n-k}$.
Therefore the total probability is just:
$$
p_{n,k} = \frac 1 n + \frac{k-1} n (1-p_{k-1}) + \frac{n-k} n (1-p_{n-k})
$$
We can also write the winning probability for the ideal strategy:
$$
p_n = \max_{k\in[1,n]}p_{k,n}
$$
The base case is $p_1=1$ (If there is only one number left, you win). The case $p_0=0$ in the code is not strictly necessary, as that case only contributes with probability $0$.
Running this program, I found that there are three different cases:
- $n$ is even: $p_{n,k}=1/2$
- $n$ is odd, $k$ is even: $p_{n,k}=(n-1)/2n$
- $n$ is odd, $k$ is odd: $p_{n,k}=(n+1)/2n$
If this is true, it follows that $p_n=1/2$ for even $n$ and $(n+1)/2n$ for odd $n$.
We can prove this by induction:
- If $n$ is even, then either:
- $k$ is odd; $k-1$ is even and $n-k$ is odd, so:
$$ \begin{align} p_{n,k} &= \frac 1 n + \frac{k-1} n \frac 1 2 + \frac{n-k} n \frac{n-k-1}{2(n-k)} \\ &= \frac 2{2n} + \frac{k-1}{2n} + \frac{n-k+1}{2n} \\ &= \frac{2+k-1+n-k-1}{2n} \\ &= \frac n {2n} = \frac 1 2 \end{align} $$
- $k$ is even; $k-1$ is odd and $n-k$ is even, so:
$$ \begin{align} p_{n,k} &= \frac 1 n + \frac{k-1} n \frac{k-1-1}{2(k-1)} + \frac{n-k} n \frac 1 2 \\ &= \frac 2{2n} + \frac{k-2}{2n} + \frac{n-k}{2n} \\ &= \frac{2+k-2+n-k}{2n} \\ &= \frac n {2n} = \frac 1 2 \end{align} $$
- If $n$ is odd and $k$ is even, $k-1$ and $n-k$ are both odd, so:
$$ \begin{align} p_{n,k} &= \frac 1 n + \frac{k-1} n \frac{k-1-1}{2(k-1)} + \frac{n-k} n \frac{n-k-1}{2(n-k)} \\ &= \frac 2{2n} + \frac{k-2}{2n} + \frac{n-k+1}{2n} \\ &= \frac{2+k-2+n-k-1}{2n} \\ &= \frac{n-1}{2n} \end{align} $$
- If $n$ is odd and $k$ is odd, $k-1$ and $n-k$ are both even, so:
$$ \begin{align} p_{n,k} &= \frac 1 n + \frac{k-1} n \frac 1 2 + \frac{n-k} n \frac 1 2 \\ &= \frac 2{2n} + \frac{k-1}{2n} + \frac{n-k}{2n} \\ &= \frac{2+k-1+n-k}{2n} \\ &= \frac{n+1}{2n} \end{align} $$
Q.E.D.
Note that the middle number is not always the best choice: if $n\equiv 3\mod 4$, then $k=(n+1)/2$ will be even, and your probability of winning will be decreased by $1/n$ compared to the perfect strategy. The first strategy that Dr Xorile proposes (choosing one of the endpoints) is a perfect strategy. A perfect strategy that still roughly halves the possibilities on each turn could be:
- Given that you know the number is between $a$ and $b$, inclusive, compute the number of numbers remaining, $n=b-a+1$.
- If $n$ is even, choose either of $(b+a\pm 1)/2$.
- Otherwise, if $n+1$ is divisible by four, choose either of $(b+a)/2\pm 1$.
- Otherwise choose $(b+a)/2$.
Note again the assumptions we made: that your opponent also follows a perfect strategy (although not necessarily an identical strategy), and that the answer is evenly distributed among the possible guesses.
