# strings

• January 17th 2009, 09:25 AM
qwerty321
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
• January 17th 2009, 10:21 AM
Plato
Quote:

Originally Posted by 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 ?

Here is a big hint: $5(12)=60$.
• January 17th 2009, 10:38 AM
awkward
Quote:

Originally Posted by qwerty321
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|$.
• January 17th 2009, 11:22 AM
qwerty321
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?
• January 17th 2009, 11:27 AM
qwerty321
i mean 61 not 60
• January 17th 2009, 11:34 AM
Plato
Quote:

Originally Posted by qwerty321
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?
• January 17th 2009, 11:46 AM
qwerty321
it is 61
• January 17th 2009, 11:49 AM
qwerty321
Quote:

Originally Posted by Plato
${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]
• January 17th 2009, 11:52 AM
qwerty321
and why did you multiply by 2^7 and 2^6..order doesn't matter here no?
• January 17th 2009, 11:57 AM
Plato
Quote:

Originally Posted by qwerty321
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
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.
• January 17th 2009, 12:35 PM
Soroban
Hello, qwerty321!

Quote:

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 . . .