\documentclass[11pt]{article}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\usepackage{latexsym,amsmath,amssymb,epsfig}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.0in}
\begin{document}
\centerline{MATH 357 -- Combinatorics}
\centerline{Solutions for Problem Set 1}
\centerline{February 3, 2017}
\vskip 10pt
\noindent
1.5.10.  As is true in many cases, there is \emph{more than one correct approach} on 
this problem.  The most direct argument is probably this one:
\vskip 10pt
{\it Solution 1:}  Thinking of the pigeonhole principle, let the pigeons 
be the $n$ people, and the pigeonholes be the numbers of people known, which can 
only be $1,2,\ldots,$ or $n$.  Arguing 
by contradiction, suppose no two people know the same number of people.
Then exactly one person knows 1 person (him- or herself), exactly one person
knows 2 people, ... , and exactly one person knows $n$ people.  But this
is a contradiction because if one person knows all $n$ people, he must know
the person who only knew one person. But note that the problem said if $A$
knows $B$ then $B$ must also know $A$. So that person would have known at least
two people including him- or herself.  
\vskip 10pt 
{\it Solution 2:}  Here's another way, using the pigeonhole principle 
again.  Everyone in the group knows at least him- or herself.  If 
two or more people know only themselves, then we have two people in
the group who know just one person.  If there is exactly one person
who knows only him or herself, then the other $n-1$ people can know 
only $2,3, \ldots, n-2$ or $n-1$ people.  (Noone can know $n$ people
because none of them can know the person who knows only him- or herself.)
So we have $n-1$ pigeons placed into $n-2$ pigeonholes, and there must
be two people who know the same number of people.  Finally, if everyone
knows at least one other person, then they can only only $2,3,\ldots,n$
people.  This gives $n$ pigeons placed in $n-1$ pigeonholes again and
at least two people know the same number of people.
\vskip 10pt
\noindent
1.5.11 (Extra Credit)  Consider the ``slots'' between consecutive men
around the table as the pigeonholes and the $n+1$ women as the pigeons.
If any two consecutive slots both have at least one woman, we have a man seated between
two women.  The remaining case to consider is where no two consecutive
slots have women.  If $n$ is even, this means that only $n/2$ of the 
slots could be used.  But the generalized pigeonhole principle (Theorem 1.5.5)
implies that some one of those slots has strictly
more than $\left\lfloor\frac{(n+1) - 1}{n/2}\right\rfloor > 2$
women.  With three women together, a woman is sitting between two women.
If $n$ is odd, there can be at most $(n-1)/2$ slots that contain women
(as long as no two consecutive slots do).  But then again some
one of those slots has strictly more than  
$\left\lfloor\frac{(n+1) - 1}{(n-1)/2}\right\rfloor > 2$, 
women, so at least $3$ women. 
 So some woman is sitting between two other women again.  
\vskip 10pt
\noindent
2.1.14.  The set of possible $5$-person committees is in 1-1 correspondence
with the Cartesian product:
$${\rm Clergy} \times {\rm Scientists} \times {\rm Lawyers} \times {\rm Doctors} \times {\rm Lay}.$$
By the Multiplication Principle, the number of possible committees is $8\cdot 4\cdot 5\cdot 3\cdot 10 = 4800$.
{\it Comment:} Notice that the problem \emph{does not say} to continue and form a second and 
third committee with the people who are left over after the first committee is formed. 
\vskip 10pt
\noindent
2.1.15. The number of possible combinations of $n$ toppings is $2^n$ (it's the same
as the collection of subsets of the set of toppings).  We want the smallest $n$ such 
that $2^n > 1,000,000$, which is $n = 20$.  
\vskip 10pt
\noindent
2.1.19.  If $n$ is even, the first half of the word can be chosen arbitrarily 
and that determines the last half to get
a palindrome. This gives $26^{n/2}$ different palindromes and hence (Addition Principle)
$26^n - 26^{n/2}$ nonpalindromes, since no word is both a palindrome and a nonpalindrome.
Similarly, if $n$ is odd, then the number is $26^n - 26^{(n+1)/2}$ since now the middle
letter of the word can also be chosen arbitrarily.  {\it Comment:} 
These are two separate cases, so you do not want to combine them.  One is valid if $n$ is an
even number; the other is valid if $n$ is odd.
\vskip 10pt
\noindent
2.1.23.  We use the Multiplication Principle for all of these:
\begin{enumerate}
\item[(i)]  There are $9\cdot 10^4$ five-digit numbers (the leading digit cannot be zero).
\item[(ii)]  To count numbers that have no two equal digits, there are $9$ choices
for the leading digit (not $0$), then $9$ again for the second (which must be different from 
the first digit, but can be $0$), then $8$ for the third, $7$ for the fourth, and $6$ for 
the fifth.  So there are $9\cdot 9\cdot 8\cdot 7\cdot 6 = 27216$ such five-digit numbers.
\item[(iii)]  The ones-digit must be either $1,3,5,7$, or $9$ if the number is odd, then 
whatever that digit is, there are $8$ choices for the leading digit (not $0$ and not equal
to the ones-digit), $8$ choices for the second, $7$ choices for the third, and $6$ choices
for the fourth.  This gives $8\cdot 8\cdot 7\cdot \cdot 5 = 13440$ such numbers.
\item[(iv)] {\it Solution 1:}  By the Addition Principle the number of even numbers
with no two equal digits is equal to the number of all numbers with no two equal digits, 
minus the number of odd numbers with no two equal digits, so $27216 - 13440 = 13776$.
\item[] {\it Solution 2:}  These can also be counted as follows.  There are two cases.  If
the final digit is a zero, we have $9\cdot 8\cdot 7\cdot 6 \cdot 1 = 3024$ numbers ending
in zero with no two equal digits.  If the final digit is not zero, then there are four
other even numbers it could be, the first digit could be any one of 8 possibilities, etc.
giving $8\cdot 8\cdot 7\cdot 6\cdot 4 = 10752$ possibilities.  Then we get the total number
of even numbers with distinct digits by the Addition Principle:  $10752 + 3024 = 13776$
as before.  (Note that Solution 1 is certainly simpler!)
\end{enumerate}
\vskip 10pt
\noindent
2.2.7.  Let's take the sentence ``No two restaurants serve the same menu'' to 
mean that the menus are pairwise disjoint (equivalently, no single dish appears on any two 
different menus).  For instance, if tacos appear on the Mexican menu, they are not
also on the American menu.   Then by the Addition Principle, there are $6 + 7 + 10 + 8 = 31$
different choices for lunch.  (\emph{Comment:}  Just saying the menus are different 
is ambiguous here because we can't really tell whether that means they are just
different as sets, or whether they don't have any items in common.  If they
were just different as sets, we would not have enough information to answer the question!)
\vskip 10pt
\noindent
2.2.8.  By the Multiplication Principle, there are $26^6$ seven-letter words starting with 
a.  (See the comment in 2.1.19.)  Similarly there are $25^7$ words that do not 
contain a.  Since no word appears in both collections, by the Addition Principle, the
total number is $26^6 + 25^7 > 6.4 \times 10^9$, a large number of such words :)
\vskip 10pt
\noindent
2.2.11.  In order to answer this, we need to assume that no one menu item appearing
on any one menu appears on any other menu.  That is the sets of appetizers, entrees,
and desserts are all pairwise disjoint.  By the Multiplication and Addition Principles, 
the total number of possible dinners is 
$$5 \cdot 11 \cdot 4 + 5 \cdot 9 \cdot 6 + 4 \cdot 10 \cdot 8 + 2 \cdot 7 \cdot 5 + 7 \cdot 30 \cdot 9 = 
2770.$$ 
\end{document}
