1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Counting problem: 5-character ASCII strings containing at least one @

  1. May 6, 2014 #1
    1. The problem statement, all variables and given/known data

    How many strings of five ASCII characters contain the character @ ("at" sign) at least once? [Note: there are 128 different ASCII characters.]

    2. Relevant equations

    The rule of product and inclusion-exclusion principle are relevant.

    3. The attempt at a solution

    The correct solution is as follows:

    The number of 5-character ASCII strings is 128^5. The number of 5-character ASCII strings not including at least one @ is 127^5. By the inclusion-exclusion principle, the number of 5-character ASCII strings including at least one @ is equal to 128^5 - 127^5.

    I have no problem with that. What bothers me is that I can't find out where I go wrong with the following "solution", which yields a different answer.

    Incorrect solution:

    At least one of the five characters is an @. There are 5 ways to place this character, because the string has a length of 5. The remaining characters may or may not be an @ symbol. Each of the four remaining characters can be chosen in 128 different ways.

    By the rule of product, there are 5 * 128 * 128 * 128 * 128 = 5*128^4 such strings.

    Query:

    128^5 - 127^5 is a much larger number than 5*128^4. Which assumption in my incorrect solution is unjustified?
     
  2. jcsd
  3. May 6, 2014 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    No, 5*128^4 is larger than 128^5-127^5. It's because you are overcounting strings that contain more than one @.
     
  4. May 6, 2014 #3
    In the incorrect solution your over counting.

    Example:
    Suppose we fix the first element with @.
    then our string is of the form @0000. where the 0 can be any other ASCII character. But note we have @@000 as being one such character. But if we fix the second character so we have the set of strings of the form 0@000. Clearly if we let the first character be @, then we again have a string of the form @@000.
     
    Last edited: May 6, 2014
  5. May 6, 2014 #4
    Sorry, I somehow got that inequality backwards when translating it to a forum post.

    That makes perfect sense. The devil is in the detail, particularly where combinations are involved. Thank you both!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Counting problem: 5-character ASCII strings containing at least one @
  1. Counting problem. (Replies: 8)

  2. Counting strings (Replies: 1)

  3. Counting problem (Replies: 3)

  4. Counting problem (Replies: 3)

  5. Counting math problem (Replies: 6)

Loading...