7

I noticed that several of my old credit cards have verification codes which have an interesting property which I'll call "numpathable".

A numpad is a graph that looks like this:

7 - 8 - 9
|   |   |
4 - 5 - 6
|   |   |
1 - 2 - 3

A number $n$ is a numpad path (or numpath, if you like) if its digits can be produced by moving along the edges of this graph, with at most one edge in between consecutive digits in $n$.

For example, $4556$ is a numpad path, as are $1$, $12$, and $123$ and $12321$. $987456321$ is the largest number that's a numpad path without repeating any digits.

However $4553$ isn't a numpad path, because you must traverse more than one edge between $5$ and $3$. $1234$ is also not a numpad path for the same reason. Similarly, any number containing $0$ isn't a numpad path since $0$ doesn't appear on this graph.

Q: What is the probability $P(d)$ that a random $d$-digit number ($d > 0$) is a numpad path? (Clearly, all 1 digit-numbers except 0 are numpad paths, so $P(1) = 0.9$.)

Edit: I previously called these "numpad tours", but a commenter pointed out that tours typically touch every node in a graph, so I've renamed it to numpad paths.

John Feminella
  • 544
  • 1
    Simplifications to the problem: 1) Ignore numbers that have any zeros as digits. You can multiply by $1-(9/10)^d$ later. 2) The problem then reduces to finding the number of paths of length $=d$ in your graph (if you do not allow the same digit to appear in adjacent positions). If you allow consecutive repetitions of a digit, then you need to count paths of length $\le d$ weighted by the different ways you can repeat digits to get to a $d$-digit number. – angryavian Aug 22 '20 at 21:15
  • 1
    I would do it recursively. You'll have to distinguish between strings according to the nature of the last digit. Some digits have $2-$ neighbors, some have $3$ and five has $4$, and that dictates how many options you have for the next move. – lulu Aug 22 '20 at 21:18
  • Just as a side note, the word tour here may be misleading. A knight's tour, for instance, will touch every square, and I would expect a numpad tour to touch every key. I'm sorry for this essentially useless comment because it's an interesting question! – Sort of Damocles Aug 22 '20 at 21:33
  • 1
    This is a very interesting question. +1 from me. – K.defaoite Aug 22 '20 at 22:51
  • @dbx You're right, that's confusing. I renamed these to numpad paths in accordance with the more conventional terminology. – John Feminella Aug 22 '20 at 23:22

1 Answers1

6

Recursion approach.
Let $f(n,k)$ be the number of numpad tours of length $n$, ending with digit $k$. Let $$\mathbf{f}_n:=(f(n,1),f(n,2),f(n,3),f(n,4),f(n,5),f(n,6),f(n,7),f(n,8),f(n,9))^T$$ Thus $\mathbf{f}_{n+1}=A\mathbf{f}_n$ where $$A=\begin{pmatrix} 1&1&0&1&0&0&0&0&0\\ 1&1&1&0&1&0&0&0&0\\ 0&1&1&0&0&1&0&0&0\\ 1&0&0&1&1&0&1&0&0\\ 0&1&0&1&1&1&0&1&0\\ 0&0&1&0&1&1&0&0&1\\ 0&0&0&1&0&0&1&1&0\\ 0&0&0&0&1&0&1&1&1\\ 0&0&0&0&0&1&0&1&1 \end{pmatrix}$$ The desired value is then $\frac{1}{10^{d-1}\cdot 9}(1,1,1,1,1,1,1,1,1)A^{d-1}(1,1,1,1,1,1,1,1,1)^T$.

Then we perform Jordan decomposition of $A=SJS^{-1}$ (WA, see here) to get $A^n=SJ^nS^{-1}$ (where $n=d-1$) and finally compute (see here) the fraction numerator of $$\frac14(2 + (17 - 12\sqrt{2})(1 - 2\sqrt{2})^n + (1 + 2\sqrt{2})^n(17 + 12\sqrt{2})).$$

Alexey Burdin
  • 5,214
  • Great answer, and thank you for also providing working code that let me experiment a bit. I was surprised this had a closed-form solution, but it's very clear now that it should. – John Feminella Aug 22 '20 at 23:19