How many telephone numbers can be dialed if each digit is reached from the previous one by a move of a...

combinatorics/phone.dialing New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

How many telephone numbers can be dialed if each digit is reached from
the previous one by a move of a given chess piece (knight, rook, bishop,
king or queen) on the telephone keypad?

    1 2 3
    4 5 6
    7 8 9
      0

[ Editor: problem statement reconstructed from the postings.  The only
  surviving posting works the knight case; its final sum (the squares of
  the 4-digit counts) implies that 7-digit numbers were meant. ]

Show solution

In article <Mar.6.18.29.52.1989.6425@topaz.rutgers.edu>, I wrote:

> Using the adjacency matrix approach and doing the recursion directly,
> it took me 15 minutes to come up with the answers to A *by hand*.
> Did this problem take you more than 15 minutes?

I'll give more detail on the method I used.

First, exploit all possible symmetry in the problem.  Assume we've
chosen our chess piece and note that if f(m,n) equals the number
of possible n-digit telephone numbers that start with "m" then
f(1,n) = f(3,n), f(4,n) = f(6,n), f(7,n) = f(9,n).  Furthermore,
f(1,n) = f(7,n) + a*f(0,n), f(2,n) = f(8,n) + b*f(0,n), where
a = 0 if "0" cannot be reached from "1", 1 otherwise; b is similarly
defined.  Hence we need only compute f(1,n), f(2,n), f(4,n), f(5,n),
and f(0,n) to get f(m,n) for all m.  Now note that f(m,1) = 1 for all
m, and because of my previous remarks, we need only compute 3
iterations to get the desired answer.

Sample for knight:

a,b = 0

For n>=1,

f(1,n+1) = f(6,n) + f(8,n) = f(2,n) + f(4,n)
f(2,n+1) = f(7,n) + f(9,n) = 2*f(1,n)
f(4,n+1) = f(0,n) + f(3,n) + f(9,n) = f(0,n) + 2*f(1,n)
f(5,n+1) = 0
f(0,n+1) = f(4,n) + f(6,n) = 2*f(4,n)

f(1,1) = 1, f(1,2) = 2, f(1,3) = 5, f(1,4) = 10
f(2,1) = 1, f(2,2) = 2, f(2,3) = 4, f(2,4) = 10
f(4,1) = 1, f(4,2) = 3, f(4,3) = 6, f(4,4) = 16
f(0,1) = 1, f(0,2) = 2, f(0,3) = 6, f(0,4) = 12

hence the number we seek is 6*10^2 + 2*16^2 + 12^2 = 1256.

This works out nice since a,b=0 (the rook is the same).  A little
more work is required for bishop, king, queen, but we never have to
keep track of more than 6 values.

-- Chris Long

[ Editor: the counts for the other pieces are not in the collected
  postings. ]