Competitive Higher/Lower – Part 1

At my local pub’s weekly trivia night, one of the rounds involves a game of competitive higher/lower. The quiz master has a particular number in mind and two players take turns to guess the number, being told higher or lower until someone guesses correctly and wins.

Most players tend to pick a number somewhere in the middle of the available range, leading to a reasonably quick resolution of the game one way or another. Last week my friend employed a different tactic, always opting to pick the smallest number in the available range, while the other player picked numbers somewhere in the middle of the range. My friend lost.

This week I got to play and employed the same tactic, as we’d convinced ourselves through some vague handwaving that it was the optimal tactic. I lost.

This tactic makes the game take twice as long as it normally would, and since only two people in the pub get to play the game it is generally met with groans of exasperation from the unamused room of punters.

Two losses from two attempts (and a good dose of mocking from the quiz master) didn’t seem like a good advertisement for the tactic, but it was also a very small sample size. I wanted to know if our tactic was any good, and if so, how good. So I did some maths which I’d like to share with you here.

The game at the pub typically involves guessing, to the exact cent, the value of a bag of goodies. An initial range is given, say between 3500 cents ($35) and 3600 cents ($36). To make things easier to talk about, let’s define a range [a, b] as all the integers between a and b (inclusive). Also, let’s call the spread of a range the cardinality of the range, or the number of numbers in the range. So the spread of [a, b] would be b - a + 1.

With these definitions in mind, let’s consider some basic situations in the game. If the available range has a spread of 1, then you have one choice – the correct answer – and (unless you make a terribly embarrassing mistake) you have a 100% chance of winning. If there is a spread of 2, you have a 50/50 chance of picking the right answer, and if you get it wrong the other person is left with a spread of 1, meaning they’ll win. So, a spread of 2 gives a 50% chance of winning.

Now, if there’s a spread of 3 then things get interesting. If you pick the middle number, you have a 1/3 chance of winning. But you have a 2/3 chance of losing, and if you lose your opponent faces a spread of 1 either way, meaning they win. So picking the middle option in a spread of 3 gives you a 33.3% chance of winning.

If, on the other hand, you pick a number not in the middle, you still have a 1/3 chance of winning on that move, but if you get it wrong then your opponent is faced with a spread of 2, meaning they only have a 50% chance of winning. So your total odds are (1/3) + (2/3)*(1/2) = 2/3. Picking the edge number gives you a 66.6% chance of winning!

We see that in this very simple case, picking an edge number is clearly a better option than picking the middle number. Does this generalise to larger spreads, or is it only relevant for a spread of 3? Well, lets see if we can come up with a formula for our chances for any spread.

To do this we’ll have to be a little more rigorous. First, let’s define the tactics of two players. Player 1 always picks the lowest number in the available range. Player 2 always picks the middle number of the range (for an odd spread, there is a single “middle” number for them to pick. For an even spread there are two options, so let’s say they pick the smaller of the two equally “middle” values).

We want to calculate a function f(n) which gives the probability of Player 1 winning if they go first in a game which starts with a spread of n. The first few cases are easy:

f(1) = 1 (if there’s only one choice, you’d better win!)
f(2) = \frac{1}{2} (as we proved above.)
f(3) = \frac{2}{3} (also shown above.)

Now, let’s see if we can come up with a recurrence relation which uses these base cases. Let’s start in the case where n is even. Player 1 picks their number, the smallest in the range. It’s either correct, and they win \left(\frac{1}{n}\right), or it’s incorrect \left(\frac{n-1}{n}\right) and Player 2 gets a turn with a spread of n-1. If Player 2 guesses correctly, \left(\frac{1}{n-1}\right), then Player 1 loses. If Player 2 guesses incorrectly \left( \frac{n-2}{n-1}\right) then Player 1 will get another crack at a spread of \frac{n-2}{2}. Putting this all together gives

$latex
f(n) = \frac{1}{n} + \frac{n-1}{n} \frac{n-2}{n-1}f\left(\frac{n-2}{2}\right)\newline
\,\,\, = \frac{1}{n}\left(1 + (n-2)f\left(\frac{n-2}{2}\right)\right).
$

In the case where n is odd, there is still a \frac{1}{n} chance of Player 1 winning on that turn and an \frac{n-2}{n} chance of Player 2 getting a chance and missing, but now if Player 2 gets it wrong things are a little tricky. Player 2 faced an even spread, so picked one of two equally good “middle” values, but if he’s wrong then there are two different spreads that Player 1 might face on their next turn. Out of the n-2 possibly correct values which Player 2 didn’t pick, \frac{n-1}{2} will be on one side of the number he did pick (leaving Player 1 with a spread of \frac{n-1}{2}) and \frac{n-1}{2} - 1 will be on the other side (leaving Player 1 with a spread of \frac{n-1}{2} - 1).

So, we put all this together and get (in the odd case)

$latex
f(n) = \frac{1}{n} + \frac{n-2}{n} \frac{1}{n-2} \left(\frac{n-1}{2}f\left(\frac{n-1}{2}\right) + \left(\frac{n-1}{2} – 1\right)f\left(\frac{n-1}{2} – 1\right) \right)\newline
= \frac{1}{n}\left(1 + \frac{n-1}{2}f\left(\frac{n-1}{2}\right) + \left(\frac{n-1}{2} – 1\right)f\left(\frac{n-1}{2} – 1\right) \right).
$

Plugging in n=3 we get

$latex
f(3) = \frac{1}{3}\left(1 + f(1) + 0 \right)\newline
= \frac{2}{3},
$

which is consistent with our original argument.

So now lets apply this to the pub trivia scenario, where we begin with a range of 99. Expanding out the terms we need to calculate and then back substituting gives

$latex
f(99) = \frac{1}{99}(1 + 49f(49) + 48f(48))\newline
f(49) = \frac{1}{49}(1 + 24f(24) + 23f(23)\newline
f(48) = \frac{1}{48}(1 + 46f(23))\newline
f(24) = \frac{1}{24}(1 + 22f(11))\newline
f(23) = \frac{1}{23}(1 + 11f(11) + 10f(10))\newline
f(11) = \frac{1}{11}(1 + 5f(5) + 4f(4))\newline
f(10) = \frac{1}{10}(1 + 8f(4))\newline
f(5) = \frac{1}{5}(1 + 2f(2) + 1f(1))\newline
f(4) = \frac{1}{4}(1 + 2f(1))\newline
= \frac{3}{4}\newline
f(5) = \frac{3}{5}\newline
f(10) = \frac{7}{10}\newline
f(11) = \frac{7}{11}\newline
f(23) = \frac{15}{23}\newline
f(24) = \frac{15}{24}\newline
f(48) = \frac{31}{48}\newline
f(49) = \frac{31}{49}\newline
f(99) = \frac{63}{99}.
$

So in the pub trivia situation Player 1 would beat Player 2 on 63 out of every 99 games.

This is reasonably solid improvement, and demonstrates that using this tactic could definitely help you to win more prizes at pub trivia. The obvious disadvantage of course is that everyone in the pub will think you’re a bit of a dick :-)