How many patterns?

Question

You probably have seen #patterns# in android devices witch working like passwords.

some patterns

My question is how many patterns can we draw in a 3*3 net and then how many in a m*n?

assumptions:

-a pattern can be just a dot

-the direction is important and makes diffrent patterns

-you can't connect any two dots directly!

if you wanna break into someone's phone, you could just look at the fingermarks on the screen :) — Jam, Jul 08 '14 at 13:17

score 1 · Answer 1 · answered Jul 09 '14 at 09:59

1

Let us mark all the points as shown. C - Corner, M - Middle, T- Center.

Each C can reach 2 M OR 1 T, Each M can reach 2 M, 2 C OR 1 T, T can reach 4 C OR 4 M. enter image description here

Step 1: 1 step password is allowed, so there are 9 ways.

Step 2: Out of the 9 ways of step 1, there are 4 Cs, 4 Ms and 1 T. Each of the 4 Cs can reach 2 Ms or 1 T, each of the 4 Ms can reach 2 Ms, 2 Cs or 1 T, 1 T can reach 4 Cs or 4 Ms. So there are $12+20+8=40$ ways to complete step 2.

enter image description here

Step 3: Collect all the Cs and Ms together. Now the choice of Ms for Ms will be reduced by 1, since we can't go back to from where we came. So $18+32+16=66$ ways to complete step 3. enter image description here

Same way

$\underline{\text{Step 4}:} 62 $ways$\hspace{50 pt}$ $\underline{\text{Step 5}:} 62 $ways$\hspace{50 pt}$ $\underline{\text{Step 6}:} 62 $ways$\hspace{50 pt}$

$\underline{\text{Step 7}:} 62 $ways$\hspace{50 pt}$ $\underline{\text{Step 8}:} 62 $ways$\hspace{50 pt}$ $\underline{\text{Step 9}:} 62 $ways$\hspace{50 pt}$

So TOTAL number of combinations=No of ways of step 1+No of ways of step (1*2)+No of ways of step (1*2*3) +...+ No of ways of step (1*2*3*...*9)

NOTE: I was not aware about what is mentioned in the previous answer and comments that we can reach any point from any point.

answered Jul 09 '14 at 09:59

Vikram

5,580

Wow! Just Brilliant..+1 – MonK Jul 09 '14 at 10:02
@Vikram, your solution seems to contain paths with loops, say ABA or ABCA (for any A, B, C points which are accessible form one anther). Is this kind of path 'what is on mobiles', as OP requested? – CiaPan Jul 09 '14 at 10:10
@CiaPan, to avoid that form step 3 onward I have reduced 1 from the total options available. – Vikram Jul 09 '14 at 10:14
@Vikram Ah, yes, thanks. – CiaPan Jul 09 '14 at 10:20
@Vikram I think there is a little bug: each C can reach 4 M and each M can reach 4 C – Mahdi Jul 09 '14 at 13:04
@SayedMahdi, yes, u r right, that will change the total number. – Vikram Jul 09 '14 at 13:26

score 0 · Answer 2 · answered Jul 09 '14 at 06:44

0

If you have an $m \times n$ grid of dots and each stroke can go from any dot to any other dot, the number of patterns of $k$ strokes is $mn (mn-1)^k$.

answered Jul 09 '14 at 06:44

Robert Israel

448,999

you can't connect any two dots directly! – Mahdi Jul 09 '14 at 07:00
@SayedMahdi Are you sure one 'can't connect any two dots directly'? AFAIK you can go from any corner to another corner and not touch any mid-dot... Even if your fingers are not slim enough to pass between dots without touching them, you can use two fingers: put one finger on dot A, next the other finger on dot B, then lift the first finger from A - a device recognizes A-to-B pass, even though it was rather a jump instead of a stroke. I used this trick for a skew line in a pattern similar to the one in the last row, second column of your image. – CiaPan Jul 09 '14 at 07:20
@CiaPan I don't know but if what you said is true this counting is so easy let's see what if we can't connect any two dots directly! – Mahdi Jul 09 '14 at 07:43
@CiaPan, I tried it, you can not jump a dot. If you select top one point and bottom one point, device counts the middle point. – Vikram Jul 09 '14 at 10:41

How many patterns?

2 Answers2

Linked