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.

Have you ever seen this interface?

Pattern lock

Nowadays, it is used for locking smartphones.

If you haven't, here is a short video on it.


The rules for creating a pattern is as follows.

  • We must use four nodes or more to make a pattern at least.
  • Once a node is visited, then the node can't be visited anymore.
  • You can start at any node.
  • A pattern has to be connected.
  • Cycle is not allowed.

How many distinct patterns are possible?

share|improve this question
1  
I think that the best way is just case by case analysis while using symmetry. For example, there are 48 ways of starting at the center. (4 possibilities for the first step, then two possibilities for the next step, then the steps are fixed, but there are six possibilities for where to stop). –  Phira May 5 '11 at 11:57
4  
I guess the problem is that of counting self-avoiding walks in the 2x2 grid. See Wikipedia and especially Mathworld. –  ShreevatsaR May 5 '11 at 12:07
1  
Loops are allowed though, see youtube.com/watch?v=vV2efG9WCmk&feature=related for example –  Listing May 5 '11 at 13:00
1  
Diagonals are allowed too, so user9325's calculations are invalid. –  TonyK May 5 '11 at 13:45
2  
I don't see a simple way to attack it. I would just write a program to generate the possibilities (9! is only 362880 and the shorter ones are even less) and check each one for whether it meets the rules. –  Ross Millikan Apr 5 '12 at 17:31

6 Answers 6

up vote 7 down vote accepted

I believe the answer can be found in OEIS. You have to add the paths of length 4 through 9 on a 3x3 grid, so 80+104+128+112+112+40=576

I have validated the 80 4 number paths. If we number the grid $$\begin{array}{ccc}1&2&3\\4&5&6\\7&8&9 \end{array}$$

The paths starting 12 are 1236, 1254, 1258, 1256 and there were 8 choices of corner/direction, so 32 paths start at a corner. Starting at 2, there are 2145,2147,2369,2365,2541,2547,2587,2589,2563,2569 for 10 and there are 4 edge cells, so 40 start at an edge. Starting at 5, there are 8 paths-four choices of first direction and two choices of which way to turn

Added per user3123's comment that cycles are allowed: unfortunately in OEIS there are a huge number of series titled "Number of n-step walks on square lattice" and "Number of walks on square lattice", and there is no specific definition to tell one from another. For 4 steps, it adds 32 more paths-four squares to go around, four places to start in each square, and two directions to cycle. So the 4 step count goes up to 112. For longer paths, the increase will be larger. But there still will not be too many.

share|improve this answer
3  
Wow, just 576? If we try 576 patterns, we can unlock any smartphone which uses that way. Shocked. –  Benjamin May 5 '11 at 12:41
    
Cycles are allowed so there are more patterns. But yes if it would use the proposed pattern its right –  Listing May 5 '11 at 13:02
13  
It's even easier to unlock a smartphone which uses this form of code. For most people, this is the most commonly swiped pattern on their phone. The pattern will be clearly visible on the screen as an oily deposit from the user's fingers. –  Chris Taylor May 5 '11 at 13:05
    
Note that if "circles are allowed" only means that the last step could close a circle, this would do less than multiply the result by 4, so you might get 2000 possibilities. –  Phira May 5 '11 at 13:38
2  
@RossMillikan This doesn't seem right, diagonal lines are allowed! connecting from 1->5 and from 1->6 is allowed! –  Madara Uchiha Apr 5 '12 at 16:59

I don't have the answer as "how to mathematically demonstrate the number of combinations". Still, if that helps, I brute-forced it, and here are the results.

  • 1 dot: 9
  • 2 dots: 56
  • 3 dots: 320
  • 4 dots: 1624
  • 5 dots: 7152
  • 6 dots: 26016
  • 7 dots: 72912
  • 8 dots: 140704
  • 9 dots: 140704

Total for 4 to 9 digits :389,112 combinations

share|improve this answer
2  
How do you get $56$ possibilities for $2$ dots? I only get $4\cdot 3+4\cdot 5+8=40$. –  celtschk Jul 9 '13 at 6:44
    
I now tried for $3$ dots and only get $160$ possibilities. –  celtschk Jul 9 '13 at 6:51

Writing this as a program in python gives the following results:

path with 1 dot => 9 combinations

path with 2 dots => 40 combinations

path with 3 dots => 160 combinations

path with 4 dots => 656 combinations

path with 5 dots => 2776 combinations

path with 6 dots => 11776 combinations

path with 7 dots => 50488 combinations

path with 8 dots => 217408 combinations

path with 9 dots => 941368 combinations

share|improve this answer

Was bored at work and solved it total combinations are 389432 if using 3 or more

389112 is using 4 or more.

share|improve this answer

For what it is worth, I coded this problem and found 139,880 paths meeting the criteria. I don't know of any good way of validating this answer, but I can independently verify that my code gets the right answer for the number of paths with 3 points, which is 304. To see this, note that the valencies of the 9 points look like this: $$\begin{array}{ccc} 5 & 7 & 5 \\ 7 & 8 & 7 \\ 5 & 7 & 5 \end{array} $$ This is because a node at a corner can see the 5 non-corners, a node at the centre of a side can see the 7 other nodes that are not directly opposite and the node in the centre of the square can see all the 8 other nodes. Now count paths with 3 points by considering the middle point: if it has valency $n$, then it contributes $n(n-1)$ paths of length 3 ($n$ choices for the edge going in and $n - 1$ for the edge going out). So the number of paths with 3 points is:

$$4 \times 5 \times 4 + 4 \times 7 \times 6 + 8 \times 7 = 80 + 168 + 56 = 304 $$

share|improve this answer
    
An argument along the same lines applied to the middle edge in a path of 4 points confirm that my code is also getting the right answer of 1400 for that case. –  Rob Arthan Sep 21 at 16:55

Multiply the amount of nodes(9) by the number of rows and columns (9) and then multiply that by the amount of starts(9).

It would look like this: $9\times 9=81$, then, $81\times 9=729$, so it would be 729 possible answers that some one could use. Wait!, but you have to use 4 at a minimum so you multiply that by 4 like this: $729\times 4=2916$

$2,916$ possible answers!

share|improve this answer

protected by T. Bongers Apr 17 at 15:40

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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