Results 1 to 11 of 11

Math Help - combination lock

  1. #1
    Newbie
    Joined
    Jul 2007
    Posts
    5

    combination lock

    You have a combination padlock with four dials on it. Each dial has the numbers 0 through 4 on them. The lock can have as many 0s as dials, and is set to 0000 by default. The lock does not allow you to use any number between 1 and 4 two or more times in the combination. The following combinations are valid: 0123 1234 0103 0010 4031. The following combinations are invalid: 0113 4014 0202 4444. How many possible combinations are there?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,683
    Thanks
    615
    Hello, johnphantom!

    You have a combination padlock with four dials on it.
    Each dial has the numbers 0 through 4 on them.
    The lock can have as many 0s as dials, and is set to 0000 by default.
    The lock does not allow you to use any number between 1 and 4
    . . two or more times in the combination.
    The following combinations are valid: 0123 1234 0103 0010 4031.
    The following combinations are invalid: 0113 4014 0202 4444.
    How many possible combinations are there?

    Four 0's

    There is 1 way: 0000


    Three 0's

    The three 0's can be in any of {4\choose3} \,=\,4 positions.
    The fourth number can be any of the other 4 numbers.
    Hence, there are: 4 \times 4 \,= 16 ways to have three 0's.


    Two 0's

    The two 0's can be in any of {4\choose2} \,=\,6 positions.
    The two remaining positions can be filled in: 4\cdot3\,=\,12 ways.
    Hence, there are: 6 \times 12 \,= 72 ways to have two 0's.


    One 0

    The one 0 can be in any of 4 positions.
    The three remaining position can be filled in: 4\cdot3\cdot2\,=\,24 ways.
    Hence, there are: 4 \times 24\,= 96 ways to have one 0.


    No 0's

    The four positions can be filled in: 4\cdot3\cdot2\cdot1\,= 24 ways.


    Therefore, there are: . 1 + 16 + 72 + 96 + 24 \;= 209 possible combinations.

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2007
    Posts
    5
    It seems the least complex formula I have recieved yet is:

    Sum (4 C n) * (4 P n)
    Do you agree?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    Did you ever wonder why it's called a combination lock when order matters.

    It should be called a permutation lock.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,846
    Thanks
    320
    Awards
    1
    Quote Originally Posted by galactus View Post
    Did you ever wonder why it's called a combination lock when order matters.

    It should be called a permutation lock.
    (groans in pain)

    -Dan
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jul 2007
    Posts
    5
    Here is an answer I recieved on yahoo.com:

    Yahoo! Answers - Do you have a formula for this word puzzle?


    Interestingly, it uses Pascal's Triangle to solve the problem:

    Ron Allen (person who answered the question to my satisfaction):

    let n be the max value for any wheel.
    for example n=2 would give you 0,1, or 2 for each wheel

    my simplification involves 2 things
    first it involves the progression of numbers (i forget what the specific name for it is - johnphantom comment: this is known as Pascal's Triangle, see All You Ever Wanted to Know About Pascal's Triangle and more) . The progression can be depicted as a triangle with the number 1 at the top
    the next row would have 2 numbers 1,1
    the next row would have 3 numbers 1,2,1
    the next row would have 4 numbers 1,3,3,1
    the next row would have 5 numbers 1,4,6,4,1
    and so on

    this progression gives you the multiplier for each term in the simplification and the row number that you use is equal to the number of wheels in the lock

    the terms in the simplification are as follows
    for 1 wheel the first and only term is n+1
    for 2 wheels the first term is n+1 the second is n^2
    for 3 wheels the first term is n+1 2nd is n^2 3rd is n(n-1)^2
    for 4 wheels 1st is n+1 2nd is n^2 3rd is n(n-1)^2 4th is n(n-1)(n-2)^2
    for 5 wheels the 5th term is n(n-1)(n-2)(n-3)^2
    and so on

    the terms are simply summed with their multipliers so in your example you get:
    (1)(n+1) + (3)(n^2) + (3)(n(n-1)^2) + (1)(n(n-1)(n-2)^2)
    so plugging in 4 for n you get 5+48+108+48=209

    if you had the numbers 0 tru 5 on each wheel you'd get
    6+75+240+180=501

    3 numbers and 3 wheels?
    (1)(n+1) + (2)(n^2) + (1)(n(n-1)^2)
    4+18+12=34

    the only limitation here is that n >= the number of wheels.

    Here are the formulas for five and six wheels/numbers:

    five: (1)(n+1) + (4)(n^2) + (6)(n(n-1)^2) + (4)(n(n-1)(n-2)^2) + (1)(n(n-1)(n-2)(n-3)^2)

    six: (1)(n+1) + (5)(n^2) + (10)(n(n-1)^2) + (10)(n(n-1)(n-2)^2) + (5)(n(n-1)(n-2)(n-3)^2) + (1)(n(n-1)(n-2)(n-3)(n-4)^2)

    Anyone else find this interesting?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    I think that Yahoo is just wrong.
    Soroban gave you the correct answer.
     \sum\limits_{k = 0}^4 {C(4,k)P(4,4 - k)}=209 .
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Jul 2007
    Posts
    5
    Problem is that Ron's formula comes up with the correct answer; it is just another way to express this:

    (1)(n+1) + (3)(n^2) + (3)(n(n-1)^2) + (1)(n(n-1)(n-2)^2) = 209

    I do believe for eight wheels/numbers this is correct:

    (1)(n+1) + (7)(n^2) + (21)(n(n-1)^2) + (35)(n(n-1)(n-2)^2) + (35)(n(n-1)(n-2)(n-3)^2) + (21)(n(n-1)(n-2)(n-3)(n-4)^2) + (7)(n(n-1)(n-2)(n-3)(n-4)(n-5)^2) + (1)(n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)^2) = 1441729
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    Quote Originally Posted by johnphantom View Post
    Here is an answer I recieved on yahoo.com:

    Yahoo! Answers - Do you have a formula for this word puzzle?


    Interestingly, it uses Pascal's Triangle to solve the problem:

    Ron Allen (person who answered the question to my satisfaction):

    let n be the max value for any wheel.
    for example n=2 would give you 0,1, or 2 for each wheel

    my simplification involves 2 things
    first it involves the progression of numbers (i forget what the specific name for it is - johnphantom comment: this is known as Pascal's Triangle, see All You Ever Wanted to Know About Pascal's Triangle and more) . The progression can be depicted as a triangle with the number 1 at the top
    the next row would have 2 numbers 1,1
    the next row would have 3 numbers 1,2,1
    the next row would have 4 numbers 1,3,3,1
    the next row would have 5 numbers 1,4,6,4,1
    and so on

    this progression gives you the multiplier for each term in the simplification and the row number that you use is equal to the number of wheels in the lock

    the terms in the simplification are as follows
    for 1 wheel the first and only term is n+1
    for 2 wheels the first term is n+1 the second is n^2
    for 3 wheels the first term is n+1 2nd is n^2 3rd is n(n-1)^2
    for 4 wheels 1st is n+1 2nd is n^2 3rd is n(n-1)^2 4th is n(n-1)(n-2)^2
    for 5 wheels the 5th term is n(n-1)(n-2)(n-3)^2
    and so on

    the terms are simply summed with their multipliers so in your example you get:
    (1)(n+1) + (3)(n^2) + (3)(n(n-1)^2) + (1)(n(n-1)(n-2)^2)
    so plugging in 4 for n you get 5+48+108+48=209

    if you had the numbers 0 tru 5 on each wheel you'd get
    6+75+240+180=501

    3 numbers and 3 wheels?
    (1)(n+1) + (2)(n^2) + (1)(n(n-1)^2)
    4+18+12=34

    the only limitation here is that n >= the number of wheels.

    Here are the formulas for five and six wheels/numbers:

    five: (1)(n+1) + (4)(n^2) + (6)(n(n-1)^2) + (4)(n(n-1)(n-2)^2) + (1)(n(n-1)(n-2)(n-3)^2)

    six: (1)(n+1) + (5)(n^2) + (10)(n(n-1)^2) + (10)(n(n-1)(n-2)^2) + (5)(n(n-1)(n-2)(n-3)^2) + (1)(n(n-1)(n-2)(n-3)(n-4)^2)

    Anyone else find this interesting?
    Quote Originally Posted by Plato View Post
    I think that Yahoo is just wrong.
    Soroban gave you the correct answer.
     \sum\limits_{k = 0}^4 {C(4,k)P(4,4 - k)}=209 .
    Quote Originally Posted by johnphantom View Post
    Problem is that Ron's formula comes up with the correct answer; it is just another way to express this:

    (1)(n+1) + (3)(n^2) + (3)(n(n-1)^2) + (1)(n(n-1)(n-2)^2) = 209

    I do believe for eight wheels/numbers this is correct:

    (1)(n+1) + (7)(n^2) + (21)(n(n-1)^2) + (35)(n(n-1)(n-2)^2) + (35)(n(n-1)(n-2)(n-3)^2) + (21)(n(n-1)(n-2)(n-3)(n-4)^2) + (7)(n(n-1)(n-2)(n-3)(n-4)(n-5)^2) + (1)(n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)^2) = 1441729
    It appears Soroban's and Ron's formulas form another one of the many identities associated with Pascal's Triangle:

     \sum_{k = 0}^n C(n,k)P(n,n - k) \equiv \sum_{k=0}^{n-1} C(n-1,k)P(n,n-k)(n-k+1).

    Can anyone prove this?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jul 2007
    Posts
    5
    No one chooses to prove JakeD's conjection. How bout I throw a curve. I can perform all of the permutations with one command, which is summed by pure connections in memory; as in no math.
    Last edited by johnphantom; August 12th 2007 at 12:47 AM.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Apr 2010
    Posts
    1
    It's called a combination lock because the different dials are distinguishable, and it's the combination of their settings which matters. If they were indistinguishable, then that combination would not define a permutation of digits, but here it does naturally because they're distinguishable. So in this case, using the word "permutation" would probably mean considering the order in which the dials are set to the respective settings, which is indeed extraneous.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Total number of combinations for combination lock
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: December 26th 2011, 10:11 AM
  2. 9-Digit Combination Lock Chances And Probability
    Posted in the Statistics Forum
    Replies: 9
    Last Post: June 25th 2011, 03:39 PM
  3. combination lock (question)
    Posted in the Statistics Forum
    Replies: 7
    Last Post: May 18th 2009, 04:08 PM
  4. Master Lock Combination
    Posted in the Statistics Forum
    Replies: 2
    Last Post: October 7th 2008, 06:22 PM
  5. Combination Lock
    Posted in the Statistics Forum
    Replies: 1
    Last Post: October 1st 2007, 03:11 PM

Search Tags


/mathhelpforum @mathhelpforum