Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was wondering how many different possible combinations are there for unlocking an Android phone. In order to do this, you have to choose a path from a graph:

Android unlocking screen

The graph is not regular: the nodes at the corners are linked to 5 nodes only, the nodes at the sides are linked to 7 nodes and the central node is connected to every other.

The unlocking paths can have any length between 3 and 9. Is there a simple way to count the possibilities?

share|improve this question
1  
Actually, the graph is complete (and regular); you can go from any node to any other, because you don't have to move between them in a straight line. (Tested w/ Android 2.3.6.) –  Kevin Reid Dec 20 '11 at 0:59
add comment

3 Answers

up vote 6 down vote accepted

If $A$ is the adjacency matrix of the graph, then the $ij$ entry of $A^n$ is the number of paths from vertex $i$ to vertex $j$ of length $n$ (why?). $A^n$ can be computed quickly by diagonalizing.

share|improve this answer
    
Would you mind explaining why? I'm not studying graph theory nor well versed in the subject (this problem came up while discussing Android, not graph theory). –  Fernando Martin Dec 21 '11 at 23:48
    
This can be proven inductively. If $p(i,j,n)$ is the number of paths of length $n$ from $i$ to $j$, then $p(i,j,n)=\sum_{\mbox{k a neighbor of j}}p(i,k,n-1)$. –  Perce Dec 23 '11 at 21:47
2  
In your solution it's possible to walk throug a vertex more than one times, but n Android you can't. How modify your solution for excluding incorrect paths? –  Corvus Feb 6 '13 at 17:05
add comment

Actually in this case the adjacency matrix and its powers can be trivially computed. For a full graph, in fact, we have $A^m=n^{m-1}J$ where $n$ is the number of nodes in the graph and $J$ is the matrix of all ones. Therefore the number $f(n)$ of possible paths of length $3, 4, \dots, n$ is exactly $$f(n)=\sum_{k=3}^n\sum_{ij=1}^n (A^k)_{ij}=n^4\sum_{k=0}^{n-3}n^k=\frac{n^4(1-n^{n-2})}{1-n}$$ The number you are looking for is $f(9)$.

share|improve this answer
add comment

Let's define $v(n)$ as the number of $n$-step paths to a particular corner, $e(n)$ to a particular side and $f(n)$ to the centre node. Then you have

$$v(n)=4e(n-1)+f(n-1)$$ $$e(n)= 4v(n-1)+2e(n-1)+f(n-1)$$ $$f(n)= 4v(n-1)+4e(n-1)$$

starting with $v(0)=e(0)=f(0)=1$. Your desired result is $$\sum_{n=3}^{n=9} 4v(n)+4e(n)+f(n)$$ which I think may be 179,966,424.

There may be shortcuts: it is also $f(3)+f(10)+2\sum_{n=4}^{n=9} f(n)$; for large $n$, the number of paths of length $n$ is about $8.860423 \times 6.36388667^n$, i.e. close to a geometric progression.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.