Google’s Keypad

One of the many lovely things about Big MathsJam is that I’ve found My People - I’ve made several very dear friends there, introduced others to the circle, and get to stay in touch with other maths fans through the year. It’s golden.

Adam Atkinson is one of those dear friends, and one of the ways he stays in touch is to send me puzzles. This one, a question Alex Golec has used to interview people at Google, made me struggle for a bit, then grin in smug triumph - which is a very MathsJam reaction.

The problem

If you can’t be bothered clicking the link, the problem is to determine how many different phone numbers you can dial if you can only make $n$ knight’s moves on a standard keypad. Nothing artificial about that, no sir.

Golec’s post goes into some detail about how to solve it with code, which might be fine for Google, but it’s not the MathsJam way1

I did it a different way. Below the line be spoilers.


My first move was to draw a graph showing how the different numbers connect:

keypad graph

Number 5, it turns out, doesn’t allow a move anywhere else, so it’s not on the graph.

The nine digits can be grouped into four classes according to the kinds of neighbours they have: Corner digits (1, 3, 7 and 9), Triples (4 and 6), Middles (2 and 8) and Zero (well, 0).

I’m going to set up four functions here: $C(n)$, $T(n)$, $M(n)$ and $Z(n)$, each being how many numbers you can dial starting from a digit in each of the four classes.

If you start at a Corner, you can immediately move to a Triple or to a Middle, which means $C(n) = T(n-1) + M(n-1)$.

If you start at a Triple, you can move to either of two Corners, or to Zero: $T(n) = 2C(n-1) + Z(n-1)$.

Starting at a Middle, your next move is to either of two Corners: $M(n) = 2C(n-1)$.

And starting at Zero, your next move is to either Triple: $Z(n) = 2T(n-1)$.

We also have, by definition, $C(0) = T(0) = M(0) = Z(0) = 1$.

I spy a recurrence relation!

We have four linked recurrence relations - and what with this being Google and all, that looks like a linear algebra problem. We can set it up as a matrix:

$\left( \begin{array}{c} C(n) \\ T(n) \\ M(n) \\ Z(n) \end{array} \right) = \left( \begin{array}{cccc} 0 & 1 & 1 & 0 \\ 2 & 0 & 0 & 1 \\ 2 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \end{array} \right) \left( \begin{array}{c} C(n-1) \\ T(n-1) \\ M(n-1) \\ Z(n-1) \end{array} \right)$

If I say $\bb{X}(n) = \left( \begin{array}{c} C(n) \\ T(n) \\ M(n) \\ Z(n) \end{array} \right)$ and $\bb{M} = \left( \begin{array}{cccc} 0 & 1 & 1 & 0 \\ 2 & 0 & 0 & 1 \\ 2 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \end{array} \right)$, that can be written as:

$\bb{X}(n) = \bb{M} \cdot \bb{X}(n-1)$, with $\bb{X}(0) = \left( \begin{array}{c} 1 \\ 1 \\1 \\1 \end{array} \right)$.

But that means $\bb{X}(n) = \bb{M}^n \left( \begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \end{array} \right)$, which can be computed quickly for any value of $n$.

Then we just need to read off the answer!

Did I get the job2?

Colin

Colin is a Weymouth maths tutor, author of several Maths For Dummies books and A-level maths guides. He started Flying Colours Maths in 2008. He lives with an espresso pot and nothing to prove.

  1. It’s totally OK to solve things with code at MathsJam. It’s just harder to be smug about. []
  2. I don’t really want a job. []

Share

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Sign up for the Sum Comfort newsletter and get a free e-book of mathematical quotations.

No spam ever, obviously.

Where do you teach?

I teach in my home in Abbotsbury Road, Weymouth.

It's a 15-minute walk from Weymouth station, and it's on bus routes 3, 8 and X53. On-road parking is available nearby.

On twitter