Discrete Mathematics
Exam 1 Solutions
Ethan Bolker
October 16, 2014
The first question was worth 16 points. Each part of each succeeding question was worth 12
points, for a total of 100. (I didn’t count the last optional hard question.)
I tried to be reasonably generous with part credit.
Here’s the grade distribution, with approximate letter grade equivalents (you can’t take those
literally).
range 90-99 80-89 70-79 60-69 50-59 40-49 30-39 20-29
number 1 1 3 5 3 8 4 5
grade? A A A- B C+ C C-/D D/F
1. Consider the word MISSISSIPPI. (It’s a favorite for this kind of problem.) How many ways
are there to permute the letters if all four Is or all four Ss are together? (IIII, SSSS) .
I should not have to remind you that in mathematics and in computer science, “or” means
“and/or”.
Solution
If I treat IIII as a single letter there are 8!/4!2! permutations. The factorials in the denomi-
nator take into account the fact that there are four Ss and two Ps.
There are the same number of permutations containing SSSS.
I can add those two answers to find the number of permutations containing one or the other –
as long as I correct because I’ve double counted the permutations that contain both (inclusion-
exclusion principle). There are 5!/2! of those, so my answer is
8! 5!
2× − = 1680 − 60 = 1620.
4!2! 2!
That’s an interesting historical number: it’s the year the pilgrims landed in Plymouth on the
Mayflower.
I gave partial credit for knowing how to calculate the number of permutations when some
letters are repeated. I was surprised at how many students didn’t see the need to worry about
double counting the strings in which both blocks appeared. I’d hoped my hint would point
you in that direction.
2. 18 people have gathered for dinner. Tables at the restaurant seat 6.
(a) How many ways are there to divide the 18 people into three groups of 6?
Solution
I can choose the first group of 6 in 18!/6!12! ways, then the second group in 12!/6!6!
ways. The last 6 people make the last group. Multiplying these independent choices
gives me 18!/6!6!6! ways to choose the groups in order.
Now in the problem statement the tables aren’t mentioned. They are clearly indistin-
guishable. There is no way to assign a particular group to a particular table. That means
choosing the same three groups in any other order would lead to the same division, so I
need to divide by 3!. The answer is
18!
= 21, 237, 216
6!6!6!3!
1
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller ntombelanomfundo95. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $4.80. You're not tied to anything after your purchase.