CS 2620 : Discrete Structures Problems on section 6.1 (Counting principles) 1. H
ID: 648211 • Letter: C
Question
CS 2620 : Discrete Structures
Problems on section 6.1 (Counting principles)
1. How many positive integers less than 10000 are divisible by exactly one of 7 and 11? Explain your answer or show your work. [4 points]
2. How many 4-element DNA sequences contain exactly three of the four bases A, C, G, and T? Explain your answer or show your work. [4 points]
3. How many license plates can be made using either four uppercase English letters followed by three digits or four digits followed by three uppercase English letters? Explain your answer or show your work. [4 points]
4. How many strings of four decimal digits end with an odd digit? Explain your answer or show your work. [4 points]
Problems on section 6.2 (Pigeonhole principle)
5. Provide justification in favor of or against the statement
Explanation / Answer
1. How many positive integers less than 10000 are divisible by exactly one of 7 and 11
the number that is divisible by both 7 and 11 must be divisible by 77(since 7 x 11)
so 10000/77=129 numbers
2.How many 4-element DNA sequences contain exactly three of the four bases A, C, G, and T?
There are 4 ways of choosing which base (A, C, G, or T) represents the pair.
There are 4 choose 2 = 6 ways of choosing which 2 positions in the 4-element sequence are occupied by the pair.
Once the pair has been established, there are 3 ways of choosing the base for the first of the remaining 2 unoccupied positions, and then 2 ways of choosing the base for the remaining unoccupied position.
From the fundamental counting principle, there are 4(6)(3)(2) = 144 possible sequences
3.(26^3 * 10^3) + (26^4 * 10^2)
You have two sets of plates. In the first, for every combo of 3 letters, there are 1000 combos of 3 number, 000 to 999. You multiply these to get the total number in that group.
The second group is similar, then you add the two results.
4)
We have 10 choices each for the first three digits, then 5 for the final digit,
for (103)(5) = 5000 strings
5)
NO, consider we select 1,2,3,4,5,6 then on;y pair(5,6) is only 11..no other pair gives sum 11..so that condition fails
6) as 12 signs are there so 12x5 = 60 people must there. and 61 people must have sign that we needed
7)As you said out of 50 27 are true..so 23 are false....so 23 pairs possible
8)you said 16 systems are there. 7 of them are servers so 8 of them are systems. so 8 pairs possible.
9)There are 5 possible places where one could place the ab. This leaves four additional
characters, which we can choose in order, in (24)(23)(22)(21) ways. There are thus (5)(24)(23)(22)(21) such strings.