13
$\begingroup$

Can you please help settle a debate about the best strategy for this game?

At pub trivia when there is a tie for first or second the host uses a guess the right number between 1 and 99. Each person gets an alternate guess and she says higher or lower to narrow the range. The debate is about when you get down to a range of 5-10 numbers. I always like to leave at least a 2 number gap if possible so that if I get it wrong, my opponent still has a 50/50 choice.

eg Let's say the possible numbers left are 21, 22, 23, 24, & 25. I would choose 23. Once the host says higher or lower (if I'm not right), the opponent still has to guess the right answer, and if they guess wrong, I will get it right.

So what is the probability of each guesser (1st or 2nd guesser) winning from this point, and which is the best first choice for guesser 1? Should I choose the middle, the edge or the in between?

$\endgroup$
  • $\begingroup$ a) is the number chosen randomly between 1..99? i.e. not a distribution? b) Are the other player guesses random, or follow some distribution? Generally b) does not hold. $\endgroup$ – smci Oct 17 '15 at 1:19
  • $\begingroup$ Is 1-99 inclusive of 1 and/or 99? $\endgroup$ – Matthew0898 Oct 23 '15 at 15:48
15
$\begingroup$

If you have a range of 1 number, you are guaranteed to get it right.

If you have a range of 2 numbers, you have a 1/2 chance of getting it on your guess. If you don't your opponent has a range of 1 number, so they are guaranteed to get it.

If you have a range of 3 numbers, you can choose the middle or an edge. The middle leaves two ranges of 1, while the edge leaves a range of 2. The better strategy must be to choose the edge, and your chance of winning is 2/3.

If you have a range of 4 numbers, you can choose a middle number or an edge.

  • If you choose an edge and you're wrong, you leave a range of 3 numbers. We know that in this situation, the opponent has a 2/3 chance of winning.

  • If you choose a middle number and you're wrong, there is a range of 2 on one side, and a single number. In two cases, the actual number is in the range of 2 (leaving a 1/2 chance for the opponent). In the other case, it is the single number, and your opponent gets it. Overall, the chance that the opponent wins is (2/3)(1/2)+(1/3)(1)=2/3.

Therefore, either way, you have a 1/4+(3/4)(1/3)=1/2 chance of winning.


Now we can consider the range of five numbers.

  • If you choose an edge, you leave a range of 4, which we know is a 1/2 chance for the opponent.

  • If you choose the middle, you leave two ranges of 2, which we know is also a 1/2 chance.

  • If you choose one of the other numbers (22 or 24), you leave a range of 3 and a range of 1. This gives your opponent a chance of more than 1/2.

In conclusion, you can choose 21, 23, or 25 to get a 1/5+(4/5)(1/2)=3/5 chance of winning, but 22 and 24 are bad.

$\endgroup$
  • $\begingroup$ I think you're right, but your explanation of 4 numbers doesn't really parse to me (and I well understand the problem). You might want to reword that. $\endgroup$ – Joe Oct 16 '15 at 20:06
  • $\begingroup$ If I'm the host, I would be unlikely to select completely at random, and the bad numbers (leaves on higher-lower tree) will be favored in generation. $\endgroup$ – Joshua Oct 17 '15 at 20:26
7
$\begingroup$

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:

  1. $n$ is even: $p_{n,k}=1/2$
  2. $n$ is odd, $k$ is even: $p_{n,k}=(n-1)/2n$
  3. $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:

  1. 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} $$
  2. 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} $$
  3. 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.

$\endgroup$
  • $\begingroup$ Of note: in choosing the starting range of 1-99, the host has given a (small) advantage to the team that guesses first, provided they follow correct strategy. Using 1-100 (or any other even count range) would make it fair. $\endgroup$ – glibdud Oct 16 '15 at 16:06
6
$\begingroup$

It turns out that it's always a good strategy to choose one end of the range that is presented to you. But let's face it, that's going to be irritating for everyone waiting. Luckily it also turns out that it's almost always just as good of an idea to pick around the middle.

Here are the stats:

 Size of range: 1 choose number 1 to win 1
 Size of range: 2 choose number 1 to win 1/2
 Size of range: 3 choose number 1 to win 2/3
 Size of range: 4 choose number 2 to win 1/2
 Size of range: 5 choose number 3 to win 3/5
 Size of range: 6 choose number 3 to win 1/2
 Size of range: 7 choose number 3 to win 4/7
 Size of range: 8 choose number 4 to win 1/2
 Size of range: 9 choose number 5 to win 5/9
 Size of range: 10 choose number 5 to win 1/2
 Size of range: 11 choose number 5 to win 6/11
 Size of range: 12 choose number 6 to win 1/2
 Size of range: 13 choose number 7 to win 7/13
 Size of range: 14 choose number 7 to win 1/2
 Size of range: 15 choose number 7 to win 8/15
 Size of range: 16 choose number 8 to win 1/2
 Size of range: 17 choose number 9 to win 9/17
 Size of range: 18 choose number 9 to win 1/2
 Size of range: 19 choose number 9 to win 10/19
 Size of range: 20 choose number 10 to win 1/2
 Size of range: 21 choose number 11 to win 11/21
 Size of range: 22 choose number 11 to win 1/2
 Size of range: 23 choose number 11 to win 12/23
 Size of range: 24 choose number 12 to win 1/2
 Size of range: 25 choose number 13 to win 13/25
 Size of range: 26 choose number 13 to win 1/2
 Size of range: 27 choose number 13 to win 14/27
 Size of range: 28 choose number 14 to win 1/2
 Size of range: 29 choose number 15 to win 15/29
 Size of range: 30 choose number 15 to win 1/2
 Size of range: 31 choose number 15 to win 16/31
 Size of range: 32 choose number 16 to win 1/2
 Size of range: 33 choose number 17 to win 17/33
 Size of range: 34 choose number 17 to win 1/2
 Size of range: 35 choose number 17 to win 18/35
 Size of range: 36 choose number 18 to win 1/2
 Size of range: 37 choose number 19 to win 19/37
 Size of range: 38 choose number 19 to win 1/2
 Size of range: 39 choose number 19 to win 20/39
 Size of range: 40 choose number 20 to win 1/2
 Size of range: 41 choose number 21 to win 21/41
 Size of range: 42 choose number 21 to win 1/2
 Size of range: 43 choose number 21 to win 22/43
 Size of range: 44 choose number 22 to win 1/2
 Size of range: 45 choose number 23 to win 23/45
 Size of range: 46 choose number 23 to win 1/2
 Size of range: 47 choose number 23 to win 24/47
 Size of range: 48 choose number 24 to win 1/2
 Size of range: 49 choose number 25 to win 25/49
 Size of range: 50 choose number 25 to win 1/2
 Size of range: 51 choose number 25 to win 26/51
 Size of range: 52 choose number 26 to win 1/2
 Size of range: 53 choose number 27 to win 27/53
 Size of range: 54 choose number 27 to win 1/2
 Size of range: 55 choose number 27 to win 28/55
 Size of range: 56 choose number 28 to win 1/2
 Size of range: 57 choose number 29 to win 29/57
 Size of range: 58 choose number 29 to win 1/2
 Size of range: 59 choose number 29 to win 30/59
 Size of range: 60 choose number 30 to win 1/2
 Size of range: 61 choose number 31 to win 31/61
 Size of range: 62 choose number 31 to win 1/2
 Size of range: 63 choose number 31 to win 32/63
 Size of range: 64 choose number 32 to win 1/2
 Size of range: 65 choose number 33 to win 33/65
 Size of range: 66 choose number 33 to win 1/2
 Size of range: 67 choose number 33 to win 34/67
 Size of range: 68 choose number 34 to win 1/2
 Size of range: 69 choose number 35 to win 35/69
 Size of range: 70 choose number 35 to win 1/2
 Size of range: 71 choose number 35 to win 36/71
 Size of range: 72 choose number 36 to win 1/2
 Size of range: 73 choose number 37 to win 37/73
 Size of range: 74 choose number 37 to win 1/2
 Size of range: 75 choose number 37 to win 38/75
 Size of range: 76 choose number 38 to win 1/2
 Size of range: 77 choose number 39 to win 39/77
 Size of range: 78 choose number 39 to win 1/2
 Size of range: 79 choose number 39 to win 40/79
 Size of range: 80 choose number 40 to win 1/2
 Size of range: 81 choose number 41 to win 41/81
 Size of range: 82 choose number 41 to win 1/2
 Size of range: 83 choose number 41 to win 42/83
 Size of range: 84 choose number 42 to win 1/2
 Size of range: 85 choose number 43 to win 43/85
 Size of range: 86 choose number 43 to win 1/2
 Size of range: 87 choose number 43 to win 44/87
 Size of range: 88 choose number 44 to win 1/2
 Size of range: 89 choose number 45 to win 45/89
 Size of range: 90 choose number 45 to win 1/2
 Size of range: 91 choose number 45 to win 46/91
 Size of range: 92 choose number 46 to win 1/2
 Size of range: 93 choose number 47 to win 47/93
 Size of range: 94 choose number 47 to win 1/2
 Size of range: 95 choose number 47 to win 48/95
 Size of range: 96 choose number 48 to win 1/2
 Size of range: 97 choose number 49 to win 49/97
 Size of range: 98 choose number 49 to win 1/2
 Size of range: 99 choose number 49 to win 50/99
 Size of range: 100 choose number 50 to win 1/2

These odds of winning are exactly the same as the odds of winning if you simply pick one of the edges.

$\endgroup$
  • $\begingroup$ If I pick from the edges and my opponent picks from the middle I have far better than 0.5 chance to win. Against your strategy always choosing the highest number wins 7/11 times if I choose and there are 11 numbers. If your strategy chooses first it only has 5/11 chance of victory against the strategy of always choose highest. $\endgroup$ – Taemyr Oct 16 '15 at 6:09
  • $\begingroup$ @Taemyr: can you check your calculation again? The suggested results here seem to match the general rule from 2012rcampion's and from my answer. For range 11, I found that 5 or 7 would be an optimal answer (remaining 4-6 split or 6-4 split is even on both sides), and 2012rcampion found that as 11+1 is divisible by 4, we should take either 5 or 7. These both match with the suggestion from Dr Xorile that 5 could be selected as being close to the centre but still giving an optimal win probability. $\endgroup$ – Fillet Oct 16 '15 at 10:56
5
$\begingroup$

If you are guessing with an odd range (e.g. 5), always make sure that after you choose there are two even numbers ranges left for your opponent. There will be in total 4 numbers left, but you can split them oddly (1-3) or evenly (0-4 or 2-2). Make sure you choose the even split.

For an even range, both players have 50% chance of winning with optimal play.

Proof:

There is a guaranteed 50% strategy for player 2: choose the neighbour of the number taken by player 1 to leave two even ranges. For example, with 1-10, if player 1 takes nr. 3, you take nr. 4 (with same probability of winning directly), leaving ranges 1-2 and 5-10, both which are even, and you can repeat the tactic to always have 50% chance.

There is also a guaranteed 50% strategy for player 1: if you always take the penultimate number in the range N, either this number is correct (you win), the final number in the range is correct (you lose with same probability), or the game continues with an even range, with the other player to move, at which point you can use the player 2 strategy to ensure a 50% chance.

By guessing a number that forces your opponent into one of two even ranges you get one free guess, and after that, given optimal play, it's a coin toss (apologies for the mixed metaphor).

For your case with a range of 5, you can choose:

  • 21 : 0-4 split (good: even/even)
  • 22: 1-3 split (bad: odd/odd)
  • 23: 2-2 split (good)
  • 24: 3-1 split (bad)
  • 25: 4-0 split (good)

So if the range is N and an an odd number, and you leave your opponent two even ranges, then your probability of winning overall is

$$P = 1/N + (1-1/N) * 1/2$$ $$P = 1/2 + 1/(2N)$$

So for the range of 5, that gives $P= 1/2 + 1/10 = 3/5$, as found by Emrakul and f''.

$\endgroup$
4
$\begingroup$

This is a game about minimizing the amount of information your opponent has. In order to think about this, let's first make the assumption that the number you guess will be wrong (because if it's right, so ends the experiment).

The announcer will tell your opponent whether your guess was too high or too low. This will eliminate whichever number you guessed, plus everything higher/lower than it - in other words, at least one number must vanish.

As an example, if you pick 23, then your opponent knows the number is either 24/25 or 21/22. If you pick 21, though, then your opponent knows the number is one of 22/23/24/25. Strictly speaking, if your opponent guesses randomly, then they have a worse chance of guessing correctly by a factor of two when you pick 21 as compared to when you pick 23.

So the correct strategy is this: pick a number on the outer bound of the available range. If your range is from 21 to 25, pick either 21 or 25. That will give your opponent the least information to work from on their turn.

Even if your opponent plays ideally, at this point, you still get one more guess than them, because you pick three numbers and your opponent picks two. This means, even if your opponent plays ideally, you have a 60% (3/5) chance of coming out as the winner.

$\endgroup$
  • $\begingroup$ I think it is more complicated than minimizing the amount of information that your opponent has. If you give information in turn 1, then it may help the opponent in turn 2, but there is a chance that this extra information can help you again in turn 3. For the choice of 23 this gives you the advantage in the end, and 23 is just as good a choice as 21 and 25 (see answer from f'') $\endgroup$ – Fillet Oct 16 '15 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.