Possible numeric codes

This is a question I saw and solved a long time ago, it involves some maths.

There is a keypad

1 2 3

4 5 6

7 8 9

A certain password starts with a 3. Each digit is adjacent (horizontally or vertically) on the keypad to either of the previous two digits of the password. The password length is 10. How many possibilities are there?

For example, 1247879685 is valid but 1234565985 is not (4 is not adjacent to 2 or 3).

Note:
Although a complicated combinatorics solution or a program would also work, I'm looking for one that any common person can understand.

• @Geobits Sorry, I meant either of the last 2 digits. Commented Feb 12, 2015 at 14:39
• Is 32155 allowed? Is 322 allowed? (My understanding is no, yes respectively but wanting to check I've understood right) Commented Feb 12, 2015 at 14:57
• @ChristopherFish You're right. Commented Feb 12, 2015 at 15:01
• Do you have reason to think there's a nice answer?
– xnor
Commented Feb 13, 2015 at 18:12
• @xnor I know a shorter method if a digit has to be adjacent to only the previous digit. I had originally thought the same approach would work, but it doesn't. So I have no idea whether a simple method exists or not. Commented Feb 14, 2015 at 10:41

1 Answer

I made a small program in lua. this is the code:

n = {
[0] = {},
[1] = {[2]=true,[4]=true},
[2] = {[1]=true,[3]=true,[5]=true},
[3] = {[2]=true,[6]=true},
[4] = {[1]=true,[5]=true,[7]=true},
[5] = {[2]=true,[4]=true,[6]=true,[8]=true},
[6] = {[3]=true,[5]=true,[9]=true},
[7] = {[4]=true,[8]=true},
[8] = {[7]=true,[5]=true,[9]=true},
[9] = {[6]=true,[8]=true}}

function x(a,b, level)
if level == 10 then
return 1;
end
local newnumbers = {}
for k in pairs(n[a]) do
newnumbers[k] = true
end
for k in pairs(n[b]) do
newnumbers[k] = true
end
local c = 0
for k in pairs(newnumbers) do
c = c + x(b,k,level+1)
end
return c;
end

print(x(0,3,1))


you can test it out at http://www.lua.org/cgi-bin/demo

The result is:

691,950

Not sure if I made any mistake

• Is @SamDickson wrong then? And do you know the simpler approach - no code, very little math? Commented Feb 12, 2015 at 17:12
• You tell me who is right. You should know. I could have made a mistake. And I don't know the simpler approach.
– Ivo
Commented Feb 12, 2015 at 17:15
• I just realised my approach was wrong. Sorry. Shall I delete the question or just let it be? Commented Feb 12, 2015 at 17:28
• But is the answer correct even, shouldn't a and b be removed from newnumbers ?
– HKOB
Commented Feb 12, 2015 at 19:52