Discrete math
Math 2200 Winter 2021
Exam 3: Chapters 10, 11, 12, 13, and 14
Exam 3 is due in Canvas by 11:59 pm EST on Sunday, May 9th . I will be grading your Exam 3
submissions by Tuesday, May 11th. They will be graded on correctness. You will see after each
problem what I expect to see when grading your Exams. I will also be posting solutions to Exam
3 in the Exam Solutions folder under Files in Canvas on Monday, May 10th. Thank you.
1: A cook must prepare dinner every day for a week (seven days,
starting with Sunday). The main course each day consists of ONE of the
following: beef, chicken, lamb, fish. How many menus for the week are
possible
i. If there are no restrictions on the main course?
ii. If there must be fish on Friday?
iii. If beef must be served at least once?
iv. If beef must be served at least twice?
v. If the same food may not be served two days in a row?
vi. If no food may be served if it was served on either of the
previous two days?
vii. If there must be fish on Friday and the same food may not
be served two days in a row?
viii. If the foods served on the first four days must all be
different and the foods served on the last four days must all
be different? (Wednesday is overlapped here)
When grading this I will be looking for:
• For each part, the calculations you made in finding the count
• For each part, the final count totally resolved (for example if your answer is 25, write 32)
2: Consider strings of length 12 using symbols from {𝑎, 𝑏, 𝑐, 𝑑}.
i. How many such strings have exactly five 𝑎′𝑠?
ii. How many such strings have three of each letter?
iii. How many such strings have exactly five 𝑎′𝑠 and four 𝑏′𝑠?
iv. How many such strings have exactly five 𝑎′𝑠 or four 𝑏′𝑠
(remember that the word “or” is used in the inclusive
sense)?
When grading this I will be looking for:
• For each part, the calculations you made in finding the count
• For each part, the final count totally resolved (for example if your answer is 25, write 32)
3: How many permutations are there of all the letters in the following
words?
i. DISCRETE
ii. MATHEMATICAL
iii. NOON
When grading this I will be looking for:
• For each part, the calculations you made in finding the count
• For each part, the final count totally resolved (for example if your answer is 25, write 32)
4: How many ways are there to distribute 25 cookies (the cookies are
indistinguishable) to four different people if each person must get
between 2 and 10 cookies, inclusive? Assume that all the cookies must
be distributed.
When grading this I will be looking for:
• For each part, the calculations you made in finding the count
• For each part, the final count totally resolved (for example if your answer is 25, write 32)
5: Show that if 𝑆 is a set containing 10 positive integers less than 54
(not including 54), then at least two different (not necessarily disjoint)
four-element subsets of 𝑆 have the same sum.
When grading this I will be looking for:
• A demonstration of your use of the pigeonhole principle to solve this problem
• A well-organized writing of the solution
6: Find the coefficient of 𝑥4𝑦5 in the expansion of each of the following
expressions.
i. (𝑥 + 𝑦)9
ii. (4𝑥 + 5𝑦)9
iii. (𝑥 − 3𝑦)9
When grading this I will be looking for:
• The use of the Binomial Theorem to assist in finding the coefficient
• The coefficient
7: Three kinds of prizes were awarded to some of the 100 competitors
in a race: blue ribbons for speed, red ribbons for endurance, and green
ribbons for form. Suppose that 13 blue ribbons, 25 red ribbons, and 23
green ribbons were given out. Also suppose that the total number of
people who won two ribbons (of different colors) was 17; but that no
one won three ribbons. How many people won no ribbons?
When grading this I will be looking for:
• The use of the Inclusion-Exclusion Principle in answering this question
• The final count
8:
In other words, find an isomorphism from the vertex set
{𝑈1, 𝑈2,𝑈3,𝑈4, 𝑈5, 𝑈6} to the vertex set {𝑉1, 𝑉2, 𝑉3, 𝑉4, 𝑉5, 𝑉6} that
preserves edges.
When grading this I will be looking for:
• The isomorphism between the vertices that preserves edges represented as either a set of ordered pairs or a mapping
9:
For the graph given above
i. Does the graph have an Euler Circuit? If so, state an Euler
Circuit in the graph.
ii. Does the graph have an Euler Trail? If so, state an Euler Trail
in the graph.
iii. Does the graph have a Hamiltonian Cycle? If so, state a
Hamiltonian Cycle in the graph.
iv. Does the graph have a Hamiltonian Path? If so, state a
Hamiltonian Path in the graph.
When grading this I will be looking for:
• For each part, first a “yes” or “no” answer
• For each part, if “yes” is answered, then you write an example of the circuit, trail, cycle,
or path being asked for (for example, <A, B, C, A> is a cycle – not Hamiltonian)
10:
Given the tree above
i. Which vertex is the Root of the tree?
ii. Which vertices are the Descendants of vertex B?
iii. Which vertices are the Ancestors of vertex H?
iv. Which vertices are the Children of vertex D?
v. Which vertices are the Leaves of this tree?
When grading this I will be looking for:
• The answers to each part. This one should be quick.
11:
Given the prefix code tree above
i. Encode the string “brad!”
ii. Decode the binary string “10101100111100”
When grading this I will be looking for:
• The answer for each part written out. Again, this one should be quick.