Results 1 to 4 of 4

Math Help - 2 More Difficult Questions, Any Help Is Appreciated

  1. #1
    Newbie
    Joined
    Apr 2008
    Posts
    3

    2 More Difficult Questions, Any Help Is Appreciated

    the first question is:

    let a1, a2, a3, a4, a5 , be any distinct positive integers. Show that there exists at least one subset of three of these integers whose sum is divisible by 3.

    the second quesiton is:

    The simplex lock is a popular push-button combination lock found in aparment buildings, offices schools, etc... The metallic lock has five buttons that can be pushed individually or simultaneously with other buttons, and the order and number of pushes make up a unique code. Codes for the lock follow the protocol listed below
    (i) A code has a sequence of zero or more pushes, each involving atleast on button.
    (ii) Each button may be used at most once.
    (iii) Each push may include any number of previously unpushed buttons.
    (iv) When two or more buttons are pushed at the same time, order does not matter.
    Suppose you have a five-buton simplex lock. How many possible codes exist?

    plzzzzzz help on these crazy combinatorics questions


    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,708
    Thanks
    1638
    Awards
    1
    I am not sure about adding three odds or three evens.
    7+13+21=41 & 8+14+18=40 neither sum is divisible by 3.

    Suppose {a,b,c,d,e} are the five positive integers.
    Assign each to its equivalence class modulo 3.
    If one of the classes contains three of the numbers then that sum is divisible by three.
    If no class contains more than two then no class is empty.
    So for example: a=3j in [0], b=3k+1 in [1] and c=3n+2 in [2].
    Well a+b+c=3(j+k+n)+3.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by ChiragDesai01 View Post
    [snip]

    The simplex lock is a popular push-button combination lock found in aparment buildings, offices schools, etc... The metallic lock has five buttons that can be pushed individually or simultaneously with other buttons, and the order and number of pushes make up a unique code. Codes for the lock follow the protocol listed below
    (i) A code has a sequence of zero or more pushes, each involving atleast on button.
    (ii) Each button may be used at most once.
    (iii) Each push may include any number of previously unpushed buttons.
    (iv) When two or more buttons are pushed at the same time, order does not matter.
    Suppose you have a five-buton simplex lock. How many possible codes exist?

    plzzzzzz help on these crazy combinatorics questions
    More generally, let N(n) be the number of possible codes for a n-button simplex lock.

    Suppose you are choosing a code. Your first set of buttons can consist of 1 to n buttons. Let's say you decide to push i buttons. You can choose the set of i buttons in \binom{n}{i} ways. You can stop right there or go on to pick another set of buttons. If you decide to continue, there are N(n-i) codes left to (possibly) choose. So

    N(n) = \sum_{i=1}^n \left( \binom{n}{i} + \binom{n}{i} N(n-i) \right) = \sum_{i=1}^n \left(  1 + N(n-i) \right)  \binom{n}{i}

    Combined with N(0) = 0, this is sufficient to compute N(5). I calculate N(n) = 1, 5, 25, 149, 1081 for n = 1, 2, 3, 4, 5. Better check the calculations, I am notoriously unable to compute anything.

    jw
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by awkward View Post
    More generally, let N(n) be the number of possible codes for a n-button simplex lock.

    Suppose you are choosing a code. Your first set of buttons can consist of 1 to n buttons. Let's say you decide to push i buttons. You can choose the set of i buttons in \binom{n}{i} ways. You can stop right there or go on to pick another set of buttons. If you decide to continue, there are N(n-i) codes left to (possibly) choose. So

    N(n) = \sum_{i=1}^n \left( \binom{n}{i} + \binom{n}{i} N(n-i) \right) = \sum_{i=1}^n \left(  1 + N(n-i) \right)  \binom{n}{i}

    Combined with N(0) = 0, this is sufficient to compute N(5). I calculate N(n) = 1, 5, 25, 149, 1081 for n = 1, 2, 3, 4, 5. Better check the calculations, I am notoriously unable to compute anything.

    jw
    In the above I have ignored the possibility of the "empty combination", which the phrase "zero or more pushes" in the problem statement seems to indicate is a possibility. So if you think we should be including the empty combination in the count, the final answer is 1081 + 1 = 1082.

    jw
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. difficult statistics questions
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 21st 2010, 08:54 AM
  2. Replies: 6
    Last Post: November 20th 2009, 04:27 PM
  3. Challenging Stats Questions - Help appreciated
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: May 4th 2009, 10:50 PM
  4. A few pre calc questions! help appreciated
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: December 13th 2008, 09:49 PM
  5. Difficult differentiation of e questions.
    Posted in the Calculus Forum
    Replies: 3
    Last Post: July 20th 2008, 01:18 AM

Search Tags


/mathhelpforum @mathhelpforum