Description
Problem 1. (25 points)
How many bitstrings of length 10 contain either five consecutive 0s or five consecutive 1s?
Solution.
Bit strings that have 5 consecutive 0s or 1s: 2 · (25 + 25
) = 128
2 posibilities must be taken out to satisfy either: 1111100000&0000011111
128 − 2 = 126
1
Problem 2. (25 points)
A computer network consists of six computers. Each computer is directly connected to zero or more of the
other computers. Show that there are at least two computers in the network that are directly connected to
the same number of other computers.
Solution.
Say the 6 computers are named C0, C1, C2, C3, C4, and C5
Cn can be connected to a possible 0,1,2,3,4, or 5 computers.
If Cn is connected to 0 computers, then it is not possible for Cm to be connected to 5 computers.
In the same manner, if Cn is connected to 5 computers, then it is not possible for Cm to be connected to 0
computers.
The only choices all 6 computers have are either being connected to 0,1,2,3, or 4 computers or to connect to
1,2,3,4, or 5 computers. A total of 5 options for 6 computers.
∴ With 6 computers and 5 choices, the Pigeonhole principle says that at least two must have the same
number of direct connections.
2
Problem 3. (25 points)
How many ways are there for a horse race with four horses to finish if ties are possible?
Note: any number of the four horses may tie.
Solution.
1 is 1st,1 is 2nd, 1 is 3rd, 1 is 4th: 4! = 24
1 is 1st,1 is 2nd, 2 are 3rd:
4
1
·
3
1
= 12
1 is 1st,2 are 2nd, 1 is 3rd:
4
1
·
3
2
= 12
1 is 1st,3 are 2nd:
4
1
= 4
2 are 1st,2 are 2nd:
4
2
= 6
2 are 1st,1 is 2nd, 1 is 3rd:
4
2
· 2 = 12
3 are 1st,1 is 2nd:
4
3
= 12
4 are 1st: 1
Total: 75
3
Problem 4. (25 points)
1. How many different strings can be made from the word PEPPERCORN when all the letters are used?
2. How many of these strings start and end with the letter P?
3. In how many of these strings (from part 1) are the three letter Ps consecutive?
Solution.
1.
10!
3!2!2! = 151200
2.
8!
2!2! = 10080
3.
8!
2!2! = 10080
Aggie Honor Statement: On my honor as an Aggie, I have neither given nor received any unauthorized
aid on any portion of the academic work included in this assignment.
Checklist: Did you…
1. abide by the Aggie Honor Code?
2. solve all problems?
3. start a new page for each problem?
4. show your work clearly?
5. type your solution?
6. submit a PDF to eCampus?
4
Powered by TCPDF (www.tcpdf.org)
