Results 1 to 11 of 11

Math Help - strings

  1. #1
    Member
    Joined
    Dec 2008
    Posts
    86

    strings

    Hello i need help with this problem:

    1-How many strings of length 10 over the alphabet
    {a, b, c} have exactly

    3
    aís or exactly 4 bís ?

    2-There are 12 signs in the zodiac. How many people are needed to
    guarantee that at least six of these people have the same sign ?

    I think i should use th epigeon hole principle in the second on no?
    thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by qwerty321 View Post
    2-There are 12 signs in the zodiac. How many people are needed to
    guarantee that at least six of these people have the same sign ?
    Here is a big hint: 5(12)=60.
    Last edited by Plato; January 17th 2009 at 10:41 AM.
    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 qwerty321 View Post
    Hello i need help with this problem:

    1-How many strings of length 10 over the alphabet
    {a, b, c} have exactly

    3
    a’s or exactly 4 b’s ?

    [snip]
    Hi qwerty321,

    Here is a hint on 1; some care is necessary to avoid over-counting.

    Let A = the set of strings with exactly 3 a's, and let B = the set of strings with exactly 4 b's. Then note that

    |A \cup B| = |A| + |B| - |A \cap B|.
    Last edited by awkward; January 17th 2009 at 11:42 AM. Reason: Getting the problem statement right
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Dec 2008
    Posts
    86
    ok for the two i got it it is 60(pigeon hole)

    for the one, i think it is:

    P(10,3)+P(10,4)+P(10,5) no?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Dec 2008
    Posts
    86
    i mean 61 not 60
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by qwerty321 View Post
    ok for the two i got it it is 60(pigeon hole)
    for the one, i think it is:
    P(10,3)+P(10,4)+P(10,5) no!
    {10 \choose 3}\left(2^7\right)+{10 \choose 4}\left(2^6\right)- {10 \choose 3}{7 \choose 4}

    For #1, if you had only 60, then you could have five in each of 12 holes.
    So how many do you need?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Dec 2008
    Posts
    86
    it is 61
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Dec 2008
    Posts
    86
    Quote Originally Posted by Plato View Post
    {10 \choose 3}\left(2^7\right)+{10 \choose 4}\left(2^6\right)- {10 \choose 3}{7 \choose 4}

    For #1, if you had only 60, then you could have five in each of 12 holes.
    So how many do you need?
    I did not understant the part {10 \choose 3}{7 \choose 4}[/tex]
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Dec 2008
    Posts
    86
    and why did you multiply by 2^7 and 2^6..order doesn't matter here no?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by qwerty321 View Post
    I did not understant the part {10 \choose 3}{7 \choose 4}
    That is the numbers of strings with exactly 3 a's and 4 b's.

    Quote Originally Posted by qwerty321 View Post
    and why did you multiply by 2^7 and 2^6..order doesn't matter here no?
    In the first case we place 3 a's, leaving us with 7 places to put either a B or a C.
    That can be done in 2^7 ways.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,660
    Thanks
    600
    Hello, qwerty321!

    2) There are 12 signs in the zodiac. .How many people are needed
    to guarantee that at least six of these people have the same sign ?

    Think of the "worst case scenario."

    We could have five people who are Aries, five who are Leos, five who are Virgos, etc.

    Hence, there could be at most 60 people and no six of them have the same sign.


    Therefore, the 61^{st} person . . .

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How many eight-bit strings contain exactly three 0's
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 4th 2010, 08:06 AM
  2. bit strings and substring
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: September 7th 2009, 01:16 PM
  3. Bit strings
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2009, 11:07 AM
  4. Elastic strings
    Posted in the Advanced Applied Math Forum
    Replies: 2
    Last Post: March 7th 2009, 08:57 AM
  5. Function for bit strings
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 2nd 2009, 12:16 PM

Search Tags


/mathhelpforum @mathhelpforum