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 first 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
first 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 first 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?
Best Answer
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$
so the answer is 36.
Try using similar thinking to find the other answers.