Page 419 - Discrete Mathematics and Its Applications

398 6 / Counting

48. How many bit strings of length seven either begin with 59. Suppose that at some future time every telephone in the
two 0s or end with three 1s? world is assigned a number that contains a country code
1 to 3 digits long, that is, of the form X, XX,or XXX,
49. How many bit strings of length 10 either begin with three
0s or end with two 0s? followed by a 10-digit telephone number of the form
NXX-NXX-XXXX (as described in Example 8). How
∗ 50. How many bit strings of length 10 contain either five con- many different telephone numbers would be available
secutive 0s or five consecutive 1s? worldwide under this numbering plan?
∗∗ 51. How many bit strings of length eight contain either three 60. A key in the Vigenère cryptosystem is a string of English
consecutive 0s or four consecutive 1s? letters, where the case of the letters does not matter. How
many different keys for this cryptosystem are there with
52. Every student in a discrete mathematics class is either a three, four, five, or six letters?
computer science or a mathematics major or is a joint
major in these two subjects. How many students are in 61. A wired equivalent privacy (WEP) key for a wireless fi-
the class if there are 38 computer science majors (includ- delity (WiFi) network is a string of either 10, 26, or 58
ing joint majors), 23 mathematics majors (including joint hexadecimal digits. How many different WEP keys are
majors), and 7 joint majors? there?
62. Suppose that p and q are prime numbers and that n = pq.
53. How many positive integers not exceeding 100 are divis-
ible either by 4 or by 6? Use the principle of inclusion–exclusion to find the num-
ber of positive integers not exceeding n that are relatively
54. How many different initials can someone have if a person prime to n.
has at least two, but no more than five, different initials?
63. Use the principle of inclusion–exclusion to find the num-
Assume that each initial is one of the 26 uppercase letters
ber of positive integers less than 1,000,000 that are not
of the English language.
divisible by either 4 or by 6.
55. Suppose that a password for a computer system must have 64. Use a tree diagram to find the number of bit strings of
at least 8, but no more than 12, characters, where each length four with no three consecutive 0s.
character in the password is a lowercase English letter, 65. How many ways are there to arrange the letters a, b, c,
an uppercase English letter, a digit, or one of the six spe- and d such that a is not followed immediately by b?
cial characters ∗,>,<, !, +, and =.
66. Use a tree diagram to find the number of ways that the
a) How many different passwords are available for this World Series can occur, where the first team that wins
computer system?
four games out of seven wins the series.
b) How many of these passwords contain at least one oc-
67. Use a tree diagram to determine the number of subsets
currence of at least one of the six special characters?
of {3, 7, 9, 11, 24} with the property that the sum of the
c) Using your answer to part (a), determine how long it elements in the subset is less than 28.
takes a hacker to try every possible password, assum- 68. a) Suppose that a store sells six varieties of soft drinks:
ing that it takes one nanosecond for a hacker to check cola, ginger ale, orange, root beer, lemonade, and
each possible password.
cream soda. Use a tree diagram to determine the num-
56. The name of a variable in the C programming language is ber of different types of bottles the store must stock to
a string that can contain uppercase letters, lowercase let- have all varieties available in all size bottles if all vari-
ters, digits, or underscores. Further, the first character in eties are available in 12-ounce bottles, all but lemon-
the string must be a letter, either uppercase or lowercase, ade are available in 20-ounce bottles, only cola and
or an underscore. If the name of a variable is determined ginger ale are available in 32-ounce bottles, and all but
by its first eight characters, how many different variables lemonade and cream soda are available in 64-ounce
can be named in C? (Note that the name of a variable may bottles?
contain fewer than eight characters.) b) Answer the question in part (a) using counting rules.
57. The name of a variable in the JAVA programming lan- 69. a) Suppose that a popular style of running shoe is avail-
guage is a string of between 1 and 65,535 characters, able for both men and women. The woman’s shoe
inclusive, where each character can be an uppercase or a comes in sizes 6, 7, 8, and 9, and the man’s shoe
lowercase letter, a dollar sign, an underscore, or a digit, comes in sizes 8, 9, 10, 11, and 12. The man’s shoe
except that the first character must not be a digit. Deter- comes in white and black, while the woman’s shoe
mine the number of different variable names in JAVA. comes in white, red, and black. Use a tree diagram to
58. The International Telecommunications Union (ITU) determine the number of different shoes that a store
specifies that a telephone number must consist of a coun- has to stock to have at least one pair of this type of
trycodewithbetween1and3digits,exceptthatthecode0 running shoe for all available sizes and colors for both
is not available for use as a country code, followed by men and women.
a number with at most 15 digits. How many available b) Answer the question in part (a) using counting rules.
possible telephone numbers are there that satisfy these ∗ 70. Use the product rule to show that there are 2 2 n different
restrictions? truth tables for propositions in n variables.