1
$\begingroup$

How many strings of five ASCII characters contain the character @ (“at” sign) at least once? [Note: There are 128 different ASCII characters?

My wrong attempt: Since there needs to be at least 1 @ symbol in every string we can set the 1st letter to @, then we have 128 options for the next letter and 128 options for the next letter again etc. So we have 1*128^4 options.

Could someone explain why this doesn't work?

$\endgroup$
  • 1
    $\begingroup$ how many strings do not contain the at sign anywhere? $\endgroup$ – Will Jagy Nov 9 '15 at 20:48
1
$\begingroup$

Consider instead 2 signs A, B, and strings of length 2. And your string must contain A. With your reasoning this gives 2 different strings. But we can have AA, AB, BA. You forgot to count the last one!

Perhaps the easiest way is to consider all possible strings, and then subtract the number of strings that contain no @.

$\endgroup$
1
$\begingroup$

Your string is made of $5$ characters. Let $p = \frac{1}{128}$ be the probability that a single character is equal to @.

The probability to have $0 \leq k \leq 5$ character(s) equal to @ is:

$$P(k) = {5 \choose k}p^k(1-p)^{5-k}$$

The probability to have at least one character equals to @ is:

$$P(1)+P(2)+P(3)+P(4)+P(5) = 1-P(0) = \\= 1 - {5 \choose 0}p^0(1-p)^{5-0} =\\= 1 - (1-p)^{5} = 1 - \left(\frac{127}{128}\right)^5.$$

Now, having $128^5$ possible strings, then the number of strings containing at least one @ symbol is:

$$128^5 \cdot \left( 1 - \left(\frac{127}{128}\right)^5\right) = 128^5-127^5.$$

This argument holds since the probability (in this very simple case) is defined as the ratio between the number of favourable cases (the number of strings with at least one @) and the number of possible cases (all the strings).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.