# Permutation and Combination Puzzle - Spy Keypad

1 2 3
4 5 6
7 8 9


J. Bond has to break into the headquarters of an evil organization and steal important documents. The documents are in a safe that can only be opened by entering the correct code into the keypad, which is a 3 × 3 grid as shown on the right. Bond has been told that every two consecutive digits in the code will always be adjacent keys on the keypad. For example, the digit 1 will only be followed by a 2 or 4, the digit 5 will only be followed by a 2, 4, 6 or 8, and so on. So 3252 and 12369 are valid codes, but 1234 is not (3 is not adjacent to 4 on the keypad) and 55 is not (5 is not adjacent to 5 on the keypad).

Bond also knows the ﬁrst digit of the code and the length of the code. From this, he would like to compute the number of possible codes he has to try. For instance, if the ﬁrst digit is 4 and the length of the code is 3, then there are 8 possible codes, namely {412, 414, 452, 454, 456, 458, 474, 478}. In each of the following cases, given the ﬁrst digit of the code and the number of digits in the code, help Bond compute the total number of possible secret codes.

(a) First digit 2, number of digits 8.
(b) First digit 5, number of digits 10.
(c) First digit 9, number of digits 13.


This was a real tough one that I simply cannot get through. Help please?

• Who is J. Bond and why must I help him? – Tunk-Fey May 24 '14 at 5:16
• Only Sherlock Holmes can help you. – evil999man May 24 '14 at 5:21
• @Tunk-Fey He is Bond. James Bond. – evil999man May 24 '14 at 5:22
• Is this from the Indian Informatics Exam? Seems very familiar? – sayantankhan May 24 '14 at 6:32
• @Awesome Ahh!? $007$. – Tunk-Fey May 24 '14 at 7:04

For (a),

We start on 2. Either we then choose 1 or 3, resulting in two choices for the next digit, all of which are "equivalent" to 2. Otherwise we then choose 5, resulting in four choices for the next digit, all of which are "equivalent" to 2.

Using usual counting techniques, we have only one choice for the first digit, two choices for the second digit leading to two choices for the third OR one choice for the second digit leading to four choices for the third, and then since we're back to a digit equivalent to 2, we have the same scenario, except for the final digit in which we just have the three choices adjacent to our "2" (we know longer care about the consequences of which one we choose). Hence the number of possibilities is:

$1\times (2\times 2 + 1 \times 4) \times (2\times 2 + 1 \times 4) \times (2\times 2 + 1 \times 4) \times 3=1536$

Try using similar thinking to find the other answers.

First of all, note that there are $3$ classes of numbers: corner ($1,3,7,9$), edge ($2,4,6,8$) and centre ($5$). Now clearly a corner number can be followed by any $1$ of $2$ edge numbers. An edge number can be followed by any $1$ of $2$ corner numbers or a centre number. And a centre number can only be followed by $1$ of $4$ edge numbers. Using these relations, define $3$ functions $C(n)$,$E(n)$ and $Cen(n)$ where $C(n)$ represents the total possible number of strings of length $n$ starting with a corner number. Likewise for the other 2 functions. Now we have $$C(n)=2\cdot E(n-1)$$ $$E(n)=2\cdot C(n-1)+Cen(n-1)$$ $$Cen(n)=4 \cdot E(n-1)$$ Also you can determine the initial values for the $3$ functions $$C(1)=E(1)=Cen(1)=1$$ Using these and the recurrence relations you're good to go.

If in doubt, try it out. There is a potentially lengthy but workable tabular kind of solution illustrated by the first problem - starting with $2$, the possibilities for a one number code can be represented as:

$\begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}$

Two digits gives

$\begin{array}{ccc} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{array}$

Three digits gives

$\begin{array}{ccc} 0 & 3 & 0 \\ 2 & 0 & 2 \\ 0 & 1 & 0 \end{array}$

Four digits

$\begin{array}{ccc} 5 & 0 & 5 \\ 0 & 8 & 0 \\ 3 & 0 & 3 \end{array}$

Five digits

$\begin{array}{ccc} 0 & 18 & 0 \\ 16 & 0 & 16 \\ 0 & 14 & 0 \end{array}$

Six digits

$\begin{array}{ccc} 34 & 0 & 34 \\ 0 & 64 & 0 \\ 30 & 0 & 30 \end{array}$

etc - there are some obvious patterns here which could be proved by induction if there were more problems of the same kind to solve - and similar things will appear on investigation of the other two cases.

• So the totals are $1,3,8,24,64, 192 \dots$ and you will be able to identify the different formulae for odd and even numbers - and see why it works like that. The other problems then become very much easier, because you know what you are looking for. – Mark Bennet May 24 '14 at 9:16