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

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)

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

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

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 :-)

Pentagons with Rational Trigonometry

The other day I wanted to work out the properties of a pentagon, for reasons which I might go into in a future post. In particular I wanted to know the horizontal and vertical dimensions of a pentagon with unit length “spokes”.

A started scratching out diagrams and end up with a mess of lines and stupid values like sin\left(\frac{\pi}{5}\right). It all quickly because a mess and gave me no precise numbers. Everything was in terms of trig functions and pi. Don’t get me wrong, pi’s a great number to work with if you’ve got circles, but I’m just dealing with straight lines here, I shouldn’t need transcendental numbers!

So, I reverted back to good old rational trigonometry. Rational trigonometry uses the concept of spread to measure the angle between lines, and quadrance to measure the extent between points. If the angle between two lines is \theta then the spread, s, is equal to \sin^2\theta. The quadrance between two points is just the distance squared. It turns out that using these measures makes calculations much simpler than in traditional trigonometry.

The diagram below shows a regular pentagon with unit length (and thus unit quadrance) spokes. We shall use rational trigonometry to compute exact values for all the labels shown.

The first (and most complex) step is to compute s_1 and s_2. We note that s_1 is one fifth of a full revolution and s_2 is one fifth of a half revolution. Both a half and a full revolution represent a spread of zero. Therefore s_1 and s_2 are both solutions of the 5th order spread polynomial,

S_5(s) = s(16s^2 - 20s + 5)^2 = 0.

We use the quadratic equation to find the two non-zero solutions to this equation and find

 s_1 = \frac{5 + \sqrt{5}}{8}\\  s_2 = \frac{5 - \sqrt{5}}{8}.

A corollary of the triple spread law when applied to right angled triangles gives

s_3 = 1 - s_2 = \frac{3 + \sqrt{5}}{8}.

By the spread law we can now directly find

 Q_2 = s_2 = \frac{5 - \sqrt{5}}{8}\\  Q_3 = s_3 = \frac{3 + \sqrt{5}}{8}\\  Q_4 = s_1 = \frac{5 + \sqrt{5}}{8}\\  Q_5 = 1 - s_1 = \frac{3 - \sqrt{5}}{8}.

Applying the triple quad formula to a bisected line we get

Q_1 = 4Q_2 = \frac{5 - \sqrt{5}}{2}.

Pythagoras’ theorem now gives us

Q_6 = Q_1 - Q_4 = \frac{15 - 5\sqrt{5}}{8} = 5Q_5.

Once again applying the spread law we get

 Q_7 = \frac{s_3}{s_1} = \frac{5 + \sqrt{5}}{10} = \frac{4}{5}Q_4\\  Q_8 = \frac{1 - s_1}{s_1} = \frac{5 - 2\sqrt{5}}{5}.

So, there we have it, all the interesting dimensions of a pentagon without once having to resort to transcendental numbers or functions.

If you want to know more about rational geometry I strongly suggest watching this series of short lectures by Norman Wildberger.