Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How many patterns are there with 9 dots?

  1. Dec 29, 2011 #1
    Recently smart phones using Android have provided a new feature that you can draw a pattern to unlock the screen, so here is the question, how many patterns you can create with 9 dots? By pattern we mean a connected path between 9 dots that you don't go through the same dot more than once. Is my definition of pattern clear?
    I guess that would be a nice question to be studied in combinatorics. How many such patterns can you have with n2 dots in general? (Assuming that the dots are numbered and can be distinguished).
     
  2. jcsd
  3. Dec 29, 2011 #2
    That problem sounds interesting. Can you tell more about the requirements.

    1. Does the path have to contain all dots? If yes it seems to me you are looking for the number of Hamiltonian paths.

    2. Is this the 9 dot lock you are talking about?
    http://www.stef.be/dev/javascript/patternlock/
     
  4. Dec 29, 2011 #3
    well, the requirement is that you can not choose one dot for more than once.

    No, not necessarily. I'm trying to make the problem as simple as possible, actually it requires that you choose at least 4 dots but I think if we ignore that requirement it'll be a bit easier. so you can choose any number of dots you want ranging from 4 to 9 or just any number of dots you want.

    looks close. It doesn't let me draw a pattern on it though but yea, the appearance looks the same.
     
  5. Dec 29, 2011 #4
    Ok, I've started with easy cases.

    A few definitions:
    The side of the square consists of n dots.
    A path consists of p dots.


    Code (Text):

    p          # of combinations    
    --------------------------
    1          n*n
    2          2(n-1)(2n-1)
     
    This means:
    If the path consists of 1 dot there are n*n different codes.
    If the path consists of 2 dots there are 2(n-1)(2n-1) different codes.

    -------------------------

    In general we are searching for a function [itex]f_p(n)[/itex] where p is the length of the code and the square has n dots as its side.
    p ranges from 1 to n.

    So here, [itex]f_1(n) = n^2[/itex] and [itex]f_2(n) = 2(n-1)(2n-1)[/itex]
     
  6. Dec 30, 2011 #5
    My answer for [itex]f_2(n)[/itex] is wrong by a factor of 2. It should be [itex]f_2(n)=4(n-1)(2n-1)[/itex]. That is if you count e.g. the paths (5,8) and (8,5) as two different paths. This makes sense if you interpret the paths as code for your smartphone.

    With 5 and 8 I mean dots in the following scheme:
    Code (Text):

    0 1 2
    3 4 5
    6 7 8
     
    As an example I printed the possible codes for a 9 dot lock. The codes consist of 2 dots.

    Code (Text):

    >>> ================================ RESTART ================================
    >>>
    [0, 1]
    [0, 3]
    [0, 4]
    number of paths starting with dot 0 is:   3
    [1, 0]
    [1, 2]
    [1, 3]
    [1, 4]
    [1, 5]
    number of paths starting with dot 1 is:   5
    [2, 1]
    [2, 4]
    [2, 5]
    number of paths starting with dot 2 is:   3
    [3, 0]
    [3, 1]
    [3, 4]
    [3, 7]
    [3, 6]
    number of paths starting with dot 3 is:   5
    [4, 0]
    [4, 1]
    [4, 2]
    [4, 3]
    [4, 5]
    [4, 6]
    [4, 7]
    [4, 8]
    number of paths starting with dot 4 is:   8
    [5, 2]
    [5, 1]
    [5, 4]
    [5, 7]
    [5, 8]
    number of paths starting with dot 5 is:   5
    [6, 3]
    [6, 4]
    [6, 7]
    number of paths starting with dot 6 is:   3
    [7, 6]
    [7, 3]
    [7, 4]
    [7, 5]
    [7, 8]
    number of paths starting with dot 7 is:   5
    [8, 7]
    [8, 4]
    [8, 5]
    number of paths starting with dot 8 is:   3
    solution (totals paths):  40
     
    I also tried to calculate [itex]f_3(n)[/itex], i.e. the number of possible paths consisting of 3 dots. Here is my result:

    For [itex]n \geq 3[/itex] I get: [itex]f_3(n)=8(11 - 18n + 7n^2)[/itex].
    This formula does not apply for n=2 since less path configurations are possible (e.g. you don't have the horizontal path (0,1,2) in a n*n =2*2 dot-square).

    For a n*n=3*3 dot-square the formula gives: [itex]f_3(3)=160[/itex]
    I also wrote a Python program to check this result:

    Code (Text):

    >>> ================================ RESTART ================================
    >>>
    [0, 1, 2]
    [0, 1, 3]
    [0, 1, 4]
    [0, 1, 5]
    [0, 3, 1]
    [0, 3, 4]
    [0, 3, 7]
    [0, 3, 6]
    [0, 4, 1]
    [0, 4, 2]
    [0, 4, 3]
    [0, 4, 5]
    [0, 4, 6]
    [0, 4, 7]
    [0, 4, 8]
    number of paths starting with dot 0 is:   15
    [1, 0, 3]
    [1, 0, 4]
    [1, 2, 4]
    [1, 2, 5]
    [1, 3, 0]
    [1, 3, 4]
    [1, 3, 7]
    [1, 3, 6]
    [1, 4, 0]
    [1, 4, 2]
    [1, 4, 3]
    [1, 4, 5]
    [1, 4, 6]
    [1, 4, 7]
    [1, 4, 8]
    [1, 5, 2]
    [1, 5, 4]
    [1, 5, 7]
    [1, 5, 8]
    number of paths starting with dot 1 is:   19
    [2, 1, 0]
    [2, 1, 3]
    [2, 1, 4]
    [2, 1, 5]
    [2, 4, 0]
    [2, 4, 1]
    [2, 4, 3]
    [2, 4, 5]
    [2, 4, 6]
    [2, 4, 7]
    [2, 4, 8]
    [2, 5, 1]
    [2, 5, 4]
    [2, 5, 7]
    [2, 5, 8]
    number of paths starting with dot 2 is:   15
    [3, 0, 1]
    [3, 0, 4]
    [3, 1, 0]
    [3, 1, 2]
    [3, 1, 4]
    [3, 1, 5]
    [3, 4, 0]
    [3, 4, 1]
    [3, 4, 2]
    [3, 4, 5]
    [3, 4, 6]
    [3, 4, 7]
    [3, 4, 8]
    [3, 7, 6]
    [3, 7, 4]
    [3, 7, 5]
    [3, 7, 8]
    [3, 6, 4]
    [3, 6, 7]
    number of paths starting with dot 3 is:   19
    [4, 0, 1]
    [4, 0, 3]
    [4, 1, 0]
    [4, 1, 2]
    [4, 1, 3]
    [4, 1, 5]
    [4, 2, 1]
    [4, 2, 5]
    [4, 3, 0]
    [4, 3, 1]
    [4, 3, 7]
    [4, 3, 6]
    [4, 5, 2]
    [4, 5, 1]
    [4, 5, 7]
    [4, 5, 8]
    [4, 6, 3]
    [4, 6, 7]
    [4, 7, 6]
    [4, 7, 3]
    [4, 7, 5]
    [4, 7, 8]
    [4, 8, 7]
    [4, 8, 5]
    number of paths starting with dot 4 is:   24
    [5, 2, 1]
    [5, 2, 4]
    [5, 1, 0]
    [5, 1, 2]
    [5, 1, 3]
    [5, 1, 4]
    [5, 4, 0]
    [5, 4, 1]
    [5, 4, 2]
    [5, 4, 3]
    [5, 4, 6]
    [5, 4, 7]
    [5, 4, 8]
    [5, 7, 6]
    [5, 7, 3]
    [5, 7, 4]
    [5, 7, 8]
    [5, 8, 7]
    [5, 8, 4]
    number of paths starting with dot 5 is:   19
    [6, 3, 0]
    [6, 3, 1]
    [6, 3, 4]
    [6, 3, 7]
    [6, 4, 0]
    [6, 4, 1]
    [6, 4, 2]
    [6, 4, 3]
    [6, 4, 5]
    [6, 4, 7]
    [6, 4, 8]
    [6, 7, 3]
    [6, 7, 4]
    [6, 7, 5]
    [6, 7, 8]
    number of paths starting with dot 6 is:   15
    [7, 6, 3]
    [7, 6, 4]
    [7, 3, 0]
    [7, 3, 1]
    [7, 3, 4]
    [7, 3, 6]
    [7, 4, 0]
    [7, 4, 1]
    [7, 4, 2]
    [7, 4, 3]
    [7, 4, 5]
    [7, 4, 6]
    [7, 4, 8]
    [7, 5, 2]
    [7, 5, 1]
    [7, 5, 4]
    [7, 5, 8]
    [7, 8, 4]
    [7, 8, 5]
    number of paths starting with dot 7 is:   19
    [8, 7, 6]
    [8, 7, 3]
    [8, 7, 4]
    [8, 7, 5]
    [8, 4, 0]
    [8, 4, 1]
    [8, 4, 2]
    [8, 4, 3]
    [8, 4, 5]
    [8, 4, 6]
    [8, 4, 7]
    [8, 5, 2]
    [8, 5, 1]
    [8, 5, 4]
    [8, 5, 7]
    number of paths starting with dot 8 is:   15
    solution (totals paths):  160
    >>>
     
    So, for a 9 dot lock the probability of guessing the correct code is 1/160.
     
    Last edited: Dec 30, 2011
  7. Dec 31, 2011 #6
    ** I don't know what the feature looks like on a smart phone to begin with.

    This question assumes that the 9 distinct dots are in a "square form/shape"
    in a square lattice, so that, for instance, 0 --> 4 --> 8 is the same as
    pattern as 0 --> 8.


    But if no three points (or more) were to be collinear, then these two examples
    would be different paths/patterns.
     
  8. Dec 31, 2011 #7
    The square looks like this:
    Code (Text):

    0 1 2
    3 4 5
    6 7 8
     
    I wrote a Python-program and got the following results:

    Code (Text):

    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
     
    Note: I counted paths such as (0 1 4) and (4 1 0) as two different paths
    If you don't differ between those two you have only half the combinations, see below:

    Code (Text):

    path with 1 dot    =>    9    combinations
    path with 2 dots   =>    20    combinations
    path with 3 dots   =>    80    combinations
    path with 4 dots   =>    328    combinations
    path with 5 dots   =>    1388    combinations
    path with 6 dots   =>    5888    combinations
    path with 7 dots   =>    25244    combinations
    path with 8 dots   =>    108704    combinations
    path with 9 dots   =>    470684    combinations
     

    ----

    The results above are for the 9-dot-square. In general we are searching for a function [itex]f_p(n)[/itex] where
    - p is the number of dots in the path
    - a side of a square consists of n dots

    For n=3 we get the 9-dot-square.


    So far I have found:

    [itex]f_1(n) = n^2[/itex]
    This is the number of paths consisting of 1 dot.
    A path of length 1 is just a dot, and since there are [itex]n^2[/itex] dots we have [itex]n^2[/itex] possible paths. Example for n=3:
    The number of paths (with 1 dot) in the 9-dot-square is:
    [itex]f_1(3) = 3^2 = 9[/itex]

    ---

    [itex]f_2(n) = 4(n-1)(2n-1) [/itex]
    This is the number of paths consisting of 2 dots. Such a path corresponds to an edge, so I've just counted the edges. Example for n=3:
    [itex]f_2(3) = 4(3-1)(6-1) = 40[/itex]
    Note that there are only 20 edges but I counted them twice (see above).

    ---

    [itex]f_3(n) = 8(11 - 18n + 7n^2)[/itex]
    This is the number of paths consisting of 3 dots. Here, I counted the different patterns that can be built from a 3-dot-path. Example for n=3:
    [itex]f_3(3) = 8(11 -18\cdot 3 + 7\cdot 3^2)= 160[/itex]
     
  9. Jan 1, 2012 #8
    That's good. to be honest I'm creating a new language to formalize everything in an axiomatic flavor. I'll soon share my definitions with you. My main idea is that the number of paths depend on the position of the dot. We got 3 types of dots as far as I've seen.
    I'm trying to find a formula like fp(n) as you said.
    Can you share the source code of your Python program with me? I've come up with the same results for the cases where the length of the path is 0,1,2 (when we choose 3 dots the path is 2, if we connect k dots the length is k-1 in my definition. so if we choose a single dot the path is zero). but to move forward I should write a program, I can't continue counting with writing down the possibilities on paper.
     
    Last edited: Jan 1, 2012
  10. Jan 6, 2012 #9
    I have attached the Python program. Usage:
    Run the file 9dot_main.py in the Python-Shell, e.g. by pressing F5 in idle. In the Python-Shell you can type for example:

    Code (Text):

    superFun(5,3)
     
    This calculates the number of codes consisting of 5 dots for a 3x3 dot square.
     

    Attached Files:

    Last edited: Jan 6, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: How many patterns are there with 9 dots?
  1. In how many (Replies: 1)

Loading...