1. Problem: There are 18 mathematics majors and 325 computer science majors. a) How many ways to pick two representatives so that one is a mathematics major and the other is a computer science major? b) How many ways to pick one representative who is either a mathematics or computer science major? 2. Problem: An office building has 27 floors and 37 offices per floor. How many offices are in the building? 3. Problem: A multiple-choice test has 10 questions with 4 possible answers each. a) How many ways can a student answer all questions? b) How many ways if the student can leave answers blank? 4. Problem: A shirt comes in 12 colors, male/female versions, and 3 sizes each. How many different types? 5. Problem: Six airlines fly NY to Denver, seven fly Denver to SF. How many pairs of airlines for a trip NY to SF via Denver? 6. Problem: Four major auto routes Boston to Detroit, six Detroit to LA. How many routes Boston to LA via Detroit? 7. Problem: How many different three-letter initials can people have? 8. Problem: How many three-letter initials with no repeated letters? 9. Problem: How many three-letter initials begin with A? 10. Problem: How many bit strings of length 8? 11. Problem: How many bit strings length 10 begin and end with 1? 12. Problem: How many bit strings length 6 or less, excluding empty string? 13. Problem: How many bit strings length $n$ (positive integer) consist entirely of 1s, excluding empty string? 14. Problem: How many bit strings length $n$ start and end with 1s? 15. Problem: How many strings of lowercase letters length 4 or less, excluding empty string? 16. Problem: How many strings of 4 lowercase letters contain letter x? 17. Problem: How many strings of 5 ASCII characters contain @ at least once? (128 ASCII chars) 18. Problem: How many 5-element DNA sequences a) end with A? b) start with T and end with G? c) contain only A and T? d) do not contain C? 19. Problem: How many 6-element RNA sequences a) do not contain U? b) end with GU? c) start with C? d) contain only A or U? 20. Problem: Positive integers between 5 and 31 a) divisible by 3? Which? b) divisible by 4? Which? c) divisible by 3 and 4? Which? 21. Problem: Positive integers between 50 and 100 a) divisible by 7? Which? b) divisible by 11? Which? c) divisible by both 7 and 11? Which? 22. Problem: Positive integers less than 1000 a) divisible by 7? b) divisible by 7 but not 11? c) divisible by both 7 and 11? d) divisible by 7 or 11? e) divisible by exactly one of 7 and 11? f) divisible by neither 7 nor 11? g) have distinct digits? h) have distinct digits and are even? 23. Problem: Positive integers 100 to 999 inclusive a) divisible by 7? b) odd? c) same three digits? d) not divisible by 4? e) divisible by 3 or 4? f) not divisible by 3 or 4? g) divisible by 3 but not 4? h) divisible by 3 and 4? 24. Problem: Positive integers 1000 to 9999 inclusive a) divisible by 9? b) even? c) distinct digits? d) not divisible by 3? e) divisible by 5 or 7? f) not divisible by 5 or 7? g) divisible by 5 but not 7? h) divisible by 5 and 7? 25. Problem: Strings of 3 decimal digits a) no digit repeated thrice? b) begin with odd digit? c) exactly two digits are 4s? 26. Problem: Strings of 4 decimal digits a) no digit repeated twice? b) end with even digit? c) exactly three digits are 9s? 27. Problem: Committee with one representative from each of 50 states, each rep is governor or one of two senators. How many ways to form? 28. Problem: License plates with either 3 digits then 3 uppercase letters or 3 uppercase letters then 3 digits. How many? 29. Problem: License plates with either 2 uppercase letters then 4 digits or 2 digits then 4 uppercase letters. How many? 30. Problem: License plates with either 3 uppercase letters then 3 digits or 4 uppercase letters then 2 digits. How many? 31. Problem: License plates with either 2 or 3 uppercase letters followed by 2 or 3 digits. How many? 32. Problem: Strings of 8 uppercase letters a) letters can repeat? b) no repeats? c) start with X, repeats allowed? d) start with X, no repeats? e) start and end with X, repeats allowed? f) start with BO, repeats allowed? g) start and end with BO, repeats allowed? h) start or end with BO, repeats allowed? 33. Problem: Strings of 8 English letters a) no vowels, repeats allowed? b) no vowels, no repeats? c) start with vowel, repeats allowed? d) start with vowel, no repeats? e) at least one vowel, repeats allowed? f) exactly one vowel, repeats allowed? g) start with X and at least one vowel, repeats allowed? h) start and end with X and at least one vowel, repeats allowed? 34. Problem: Number of functions from set with 10 elements to sets with a) 2 b) 3 c) 4 d) 5 elements? 35. Problem: Number of one-to-one functions from set with 5 elements to sets with a) 4 b) 5 c) 6 d) 7 elements? 36. Problem: Number of functions from set {1,2,...,n} to {0,1}? 37. Problem: Number of functions from {1,...,n} to {0,1} a) one-to-one? b) assign 0 to both 1 and n? c) assign 1 to exactly one integer less than n? 38. Problem: Number of partial functions from set with 5 elements to sets with a) 1 b) 2 c) 5 d) 9 elements? 39. Problem: Number of partial functions from set with m elements to set with n elements? 40. Problem: Number of subsets of set with 100 elements having more than one element? 41. Problem: Number of bit strings length n that are palindromes? 42. Problem: 4-element DNA sequences a) no T? b) contain ACG? c) contain all four bases? d) contain exactly three of four bases? 43. Problem: 4-element RNA sequences a) contain U? b) no CUG? c) no all four bases? d) exactly two of four bases? 44. Problem: 22 work days, total 4642 communications sent. How many employees? 45. Problem: 434 freshmen, 883 sophomores, 43 juniors in course. Sections needed if each has 34 students? 46. Problem: Ways to seat 4 of 10 people around circular table, seatings same if neighbors same? 47. Problem: Ways to seat 6 people around circular table, seatings same if neighbors same ignoring order? 48. Problem: Arrange 6 people in row from 10 including bride and groom a) bride must be in picture? b) both bride and groom? c) exactly one of bride and groom? 49. Problem: Arrange 6 people including bride and groom a) bride next to groom? b) bride not next to groom? c) bride left of groom? 50. Problem: Bit strings length 7 either begin with two 0s or end with three 1s? 51. Problem: Bit strings length 10 either begin with three 0s or end with two 0s? 52. Problem: Bit strings length 10 contain either five consecutive 0s or five consecutive 1s? 53. Problem: Bit strings length 8 contain either three consecutive 0s or four consecutive 1s? 54. Problem: Discrete math class with 38 CS majors (including joint), 23 math majors (including joint), 7 joint majors. How many students? 55. Problem: Positive integers not exceeding 100 divisible by 4 or 6? 56. Problem: Different initials if person has at least 2 but no more than 5 initials, each initial one of 26 uppercase letters? 57. Problem: Passwords length 8 to 12, characters lowercase, uppercase, digit, or 6 special chars. a) How many passwords? b) How many contain at least one special char? c) Time to try all passwords at 1 nanosecond each? 58. Problem: Variable names in C with first 8 characters, first char letter or underscore, others letters, digits, underscore. How many different variables? 59. Problem: Variable names in JAVA 1 to 65535 chars, chars uppercase, lowercase, dollar sign, underscore, digit, first char not digit. How many? 60. Problem: Telephone numbers with country code 1 to 3 digits (not 0), number up to 15 digits. How many possible numbers? 61. Problem: Telephone numbers worldwide with country code 1 to 3 digits, followed by 10-digit number NXX-NXX-XXXX. How many? 62. Problem: Vigenere cryptosystem keys with 3,4,5,6 letters, case insensitive. How many? 63. Problem: WEP keys with 10, 26, or 58 hexadecimal digits. How many? 64. Problem: If p and q are primes and n = pq, use inclusion-exclusion to find number of positive integers not exceeding n relatively prime to n. 65. Problem: Use inclusion-exclusion to find number of positive integers less than 1,000,000 not divisible by 4 or 6. 66. Problem: Use tree diagram to find number of bit strings length 4 with no three consecutive 0s. 67. Problem: Number of arrangements of letters a,b,c,d such that a is not immediately followed by b? 68. Problem: Use tree diagram to find number of ways World Series can occur where first to 4 wins out of 7 wins series? 69. Problem: Use tree diagram to find number of subsets of {3,7,9,11,24} with sum less than 28? 70. Problem: Store sells 6 soft drink varieties with different bottle sizes and availability. a) Use tree diagram to find number of bottle types needed. b) Use counting rules. 71. Problem: Running shoe available for men and women with different sizes and colors. a) Use tree diagram to find number of different shoes to stock. b) Use counting rules. 72. Problem: Number of matches in single-elimination tournament with n players? 73. Problem: Minimum and maximum matches in double-elimination tournament with n players? 74. Problem: Use product rule to show there are $2^{2n}$ different truth tables for propositions in n variables. 75. Problem: Use induction to prove sum rule for m tasks from sum rule for two tasks. 76. Problem: Use induction to prove product rule for m tasks from product rule for two tasks. 77. Problem: Number of diagonals in convex polygon with n sides? 78. Problem: Internet datagram header and total length fields. a) Max total length in octets? b) Max header length in 32-bit blocks and octets? c) Max data area length? d) Number of different data area strings if header length 20 octets and max total length? --- Due to the extensive number of problems, here is a detailed solution for the first problem only as an example. **Problem 1:** There are 18 mathematics majors and 325 computer science majors. a) In how many ways can two representatives be picked so that one is a mathematics major and the other is a computer science major? b) In how many ways can one representative be picked who is either a mathematics major or a computer science major? **Step 1:** Understand the problem. We want to find the number of ways to select representatives under given conditions. **Step 2:** Recall the counting principles. - The number of ways to choose $k$ items from $n$ is given by combinations: $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$ - When selecting one from group A and one from group B, multiply the number of choices from each group. - When selecting one from either group A or group B, add the number of choices. **Step 3:** Solve part (a). Number of ways to pick one math major: $18$ (since choosing 1 from 18 is $\binom{18}{1} = 18$) Number of ways to pick one CS major: $325$ (similarly $\binom{325}{1} = 325$) Number of ways to pick one math and one CS major: $$18 \times 325 = 5850$$ **Step 4:** Solve part (b). Number of ways to pick one representative who is either math or CS major: Total number of majors: $18 + 325 = 343$ Number of ways to pick one: $$\binom{343}{1} = 343$$ **Final answers:** a) $5850$ b) $343$