\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

%\hidesolutions         
%\showsolutions
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal and Prof.~Charles E. Leiserson}

\begin{document}
\inclassproblems{8, Fri}


% source: CEL
% topics: counting, permutations, trees

\begin{problem}

\ 

\begin{problemparts}

\problempart In how many ways can $10$ customers line up at a
supermarket checkout?

\solution{$10!$, the number of permutations.}

\problempart In how many ways can $10$ customers line up at
two supermarket checkouts?

\solution{$11!$.  Drawing a tree helps.  The first student has $2$
choices of checkout.  The second student has $3$ choices: in the other
checkout from the first student, in the same checkout ahead of the
first student, or in the same checkout behind the first student.  No
matter where the second student goes, however, notice that the third
student has exactly $4$ choices.

An alternative way to see the answer is to add a dummy customer who
acts as a separator between the customers in one checkout and those in
the other.  Each permutation of the $10$ real customers plus the dummy
corresponds to a different way that the customers can line up, where
those customers to the left of the dummy go to checkout~\#1 and those
to the right of the dummy go to checkout~\#2.  (Later in the lecture,
we'll formalize this argument using bijections.)

Students should understand both approaches.
}

\problempart In how many ways can $10$ customers line up at three
supermarket checkouts?

\solution{$12!/2$.  The tree argument is a simple extension of part~(b):
$3$ choices for the first, $4$ for the second, etc.

The argument with two dummies is trickier.  There are $12!$
permutations of the $10$ customers and two dummies, but we don't need
to distinguish the two dummies from each other.  Indeed, for each
permutation where dummy~\#1 occurs before dummy~\#2 in the order,
there is exactly one permutation where dummy~\#2 occurs before
dummy~\#1.  Thus, we overcount by a factor of~$2$.

Once again, students should understand both approaches.
}

\problempart (Optional.) What is the general case for $n$ customers
and $m$ supermarket checkouts?

\solution{$(n+m-1)!/(m-1)!$.}

\end{problemparts}

\end{problem}




% source:  chestnut
% topics:  counting boolean functions

\begin{problem}
An $n$-input, $m$-output \emph{boolean} function is a mapping
$f:\set{0,1}^n\to\set{0,1}^m$.  

\begin{problemparts}
\problempart
How many $n$-input, $1$-output boolean functions are
there?  \hint Two boolean functions are different if there exists an
$n$-bit input on which they output different values.

\solution{
There are $2^n$ possible inputs to the boolean function.  Make a truth
table listing all $2^n$ inputs and the corresponding $2^n$ outputs.
Two boolean functions are different if they have different truth
tables (even if they agree on all rows except one).  There are
$2^{2^n}$ different possibilities for the set of outputs, and thus
$2^{2^n}$ $n$-input boolean functions.
}

\problempart How many $n$-input, $m$-output boolean functions are
there?

\solution{
Since the truth table now has $m2^n$ entries, there are $2^{m2^n}$
$n$-input, $m$-output boolean functions.
}

\end{problemparts}
\end{problem}



% source:  FALL 00, Pset 8, #5
% topics:  counting relations
\begin{problem}
On a set $S$ of $n$ elements, how many of the following types of
relations are there?  (An appendix is included if you need a reminder
of the definitions.)

\begin{problemparts}
\problempart binary relations

\solution{$2^{n^2}$. We look at the matrix that corresponds to the
relations such the element of the $n \times n$ matrix is 1 if the
corresponding pair is in the relation and it is 0 otherwise.  There
are $2^{n^2}$ many different possible boolean ($0-1$) $n \times n$
matrices. Another way of reasoning about this is to say that there are
$n^2$ possible ordered pairs, and any subset of those pairs is a
possible relation. If $A$ is the set of all pairs, then all possible
relations are just all possible subsets of $A$, and we know that
$\mbox{P}(A) = 2^{|A|} = 2^{n^2}$.}

\problempart symmetric binary relations

\solution{In a symmetric binary relation, if $(a,b)\in R$, then
$(b,a)\in R$.  The matrix associated with a symmetric relation is
symmetric (the entries in the triangle above the main diagonal are the
same as the entries in the triangle below the diagonal).  The total
number of entries is~$n^2$.  The number of entries on the diagonal is
$n$ and the number of entries on the upper side of the diagonal is
$(n^2-n)/2$.  Therefore, there are $n(n-1)/2 + n = n(n+1)/2$ entries
that can be set.  Hence, there are $2^{n(n+1)/2}$ different symmetric
matrices/relations.}

\problempart reflexive binary relations 

\solution{In a reflexive binary relations, $(a,a)\in R$ for all~$a\in
S$, and thus the matrix associated with a reflexive relation must have
$1$'s along the main diagonal.  These $n$ entries are fixed, and hence
the number of entries that can be set is $n^2 - n$.  The number of
matrices corresponding to reflexive relations is $2^{n^2 - n}$,
and hence so is the number of reflexive binary relations.

Using this idea you can count the number of relations that are not
reflexive by just substracting the number of reflexive relations from
the total number of relations.}

\problempart symmetric and reflexive binary relations

\solution{The matrix associated with a symmetric and reflexive
relation is symmetric and has $1$'s along the main diagonal.  The
total number of entries is $n^2$ and there are $(n^2-n)/2$ that
are on the upper side of the diagonal.  Hence the number of such
relations is $2^{(n(n-1))/2}$.
}

\problempart symmetric or reflexive binary relations

\solution{By inclusion-exclusion, the number of symmetric or reflexive
relations equals the number of reflexive relations plus the number of
symmetric relations minus the number of reflexive and symmetric
relations, which equals $2^{n(n+1)/2}+2^{n^2 - n}-2^{(n(n-1))/2}$.
Simplify at your peril.
}

\end{problemparts}
\end{problem}


% source:  FALL 00, Pset 8, #5
% topics:  counting graphs

\begin{problem}
Consider the set of undirected graphs on the set
$V=\set{1,2,\ldots,n}$ of vertices.  (Recall that undirected graphs
have no self-loops.)  Count the number of such graphs by exhibiting a
bijection with one of the types of relations in Problem~3 .  Prove
that your mapping is a bijection.

\solution{There exists a bijection $f$ from the set of undirected
graphs with vertices $V=\set{1,2,\ldots,n}$ to the set of symmetric
and reflexive binary relations.  We define $f$ to be the function that
maps any undirected graph $G$ to the symmetric and reflexive binary
relation $f(G)= \set{(a,b)\in V\times V: \mbox{$a = b$ or $(a,b)\in
G$}}$.

First, we show that $f$ is injective.  For any two distinct undirected
graphs $G_1$ and $G_2$ defined on $V$, one must contain an edge not in
the other, since otherwise they wouldn't be distinct.  Assume without
loss of generality that $(x,y)\in G_1$ and $(x,y)\not\in G_2$.  I
claim that $(x,y)\in f(G_1)$ and $(x,y)\not\in f(G_2)$.  The first
part of the claim follows from the definition of~$f$.  For the second
part, assume that $(x,y)\in G_2$.  Then, by the definition of $f$,
either $x = y$, which is not possible since undirected graphs have no
self-loops, or $(x,y)\in G_2$, which is not possible by assumption.
Thus, $f$ is injective.

Now, we show that $f$ is surjective.  For any symmetric reflexive
relation $R$ on $V$, consider the undirected graph $G$ with edge set
$\set{(a,b): \mbox{$a\neq b$ and $(a,b)\in R$}}$.  I claim that
$f(G)=R$.

Let $(a,b)\in R$.  If $a\neq b$, then $(a,b)\in G$ by definition
of~$G$, and hence $(a,b)\in f(G)$ by definition of~$f$.  If $a=b$,
then $(a,b)\in f(G)$, since $f(G)$ contains $(x,x)$ for all $x\in V$.
Thus, we have $R\subseteq f(G)$.

Now, let $(a,b)\in f(G)$.  If $a\neq b$, then $(a,b)\in G$ by
definition of~$f$, and hence $(a,b)\in R$ by definition of~$R$.  If
$a=b$, then $(a,b)\in R$, since $R$ is reflexive.  Thus, we have
$f(G)\subseteq R$.

Since $R\subseteq f(G)$ and $f(G)\subseteq R$, we have $f(G)=R$, and
hence $f$ is surjective, since it maps some undirected graph to~$R$.
Consequently, the number of undirected graphs with $n$ labeled
vertices is $2^{n(n-1)/2}$.  }

\end{problem}



%-----------------------------------------------------
\instatement{
\section{Appendix}

\subsection{Relations}

A binary relation $R$ on a set $A$ is a subset $R \subseteq A\times
A$.  A binary relation $R$ is
\begin{itemize}
\item\emph{reflexive} if $(a,a)\in R$ for every $a
\in A$;

\item\emph{symmetric} if $aRb$ implies $bRa$ for
every $a,b\in A$.
\end{itemize}



\subsection{Functions}

A function $f:A\to B$ is
\begin{itemize}
\item\emph{injective (one-to-one)} if $f(x) = f(y)$ imples that $x =
y$ for all $x$ and $y$ in the domain of $f$;

\item\emph{surjective (onto)} if for every element $b \in B$, there
exists an element $a \in A$ such that $f(a) = b$;

\item\emph{bijective (one-to-one correspondence)} if $f$ is both
injective and surjective.

\end{itemize}
}
\end{document}

\iffalse

% more counting, permutations, trees,..


% source: ?, fall 01 reading problem (Jaime)
% topic: counting, trees

\begin{problem} 
Suppose that in next week's reading problems,
\begin{itemize}
\item the first problem has $4$ true/false questions;

\item the second problem gives you $1$ choice among $4$ alternatives;

\item you know the answer to the third problem (and used it); and

\item the answer to the last problem is an integer from 15 to 20,
inclusive.
\end{itemize}
In how many possible ways could you answer the problems?

% Suggestions, have students draw a rough tree on the board for this

\solution{$384$.  There are $16$ answers for the first part, $4$ for
the second, $1$ for the third, and $6$ for the fourth, a total of
$16\cdot 4\cdot 1\cdot 6 = 384$.  Nice way to think about this is as a
tree, but hard to draw.}

\end{problem}


% SOURCE:  SPRING00, Pset 7 #9
% topic:  permutations
% changed chess to slider puzzle
\begin{problem} 
Karen is president of the MIT Fifteen Puzzle Club.  After a long and
grueling match, the $n$ players have gone home, leaving Karen to put
the their $n$ puzzles back in their respective lockers.

\begin{problemparts}

\problempart How many ways can Karen place puzzles in lockers so
that each locker contains exactly one puzzle in each locker,
disregarding the correctness of such placement?

\solution{$n!$.  
  There are $n$  puzzles that can be place in the first locker.
  $n-1$  puzzles to choose from for the second locker, $n-2$
   puzzles for the third... etc.  Therefore there are $n!$
  possible ways.  }

% \problempart 
% This begs the question: how many ways can Jack achieve the feat
% of placing every  puzzle in the wrong locker?  Give an expression
% for general $n$ and then approximate the value for $n=10$.

% \solution{This is the number of \textit{derangements} of the set of
%   $n$ elements.  We do not know a closed form for this number, so we
%   denote it by $D_n$ as derived in Rosen, \S 5.6.  To approximate
%   $D_{10}$ we will use Stirling's approximation, $D_{10}\approx$
%   something =) }

\problempart Say Karen recognizes Tina's puzzle, so she can place that
one correctly, but recognizes none of the other puzzles.  How many
possible ways can Karen place puzzles in lockers assuming she at least
gets Tina's right?

\solution{The answer is $(n-1)!$.  After placing Tina's  puzzle
in the right locker, we are left with $(n-1)$  puzzles and
$(n-1)$ lockers.  Thus, there are $(n-1)!$ ways to place the remaining
sets.  }

\problempart It turns out, however, that Karen really resents Tina's
puzzle prowess.  She decides to get even by putting Tina's puzzle in
another student's locker.  How many ways can she place puzzles in
lockers without placing Tina's puzzle into Tina's locker?

\solution{The answer is the total number of ways to place the puzzles
  minus the number of ways that place Tina's puzzle correctly, which
  gives $n! - (n-1)!$.  Another way to derive this solution is to
  observe that there are $(n-1)$ ways to place Tina's puzzle in the
  wrong locker and $(n-1)!$ ways to place the other puzzles.
  Consequently, there are a total of $(n-1)*(n-1)! = n(n-1)! - (n-1)!
  = n! - (n-1)!$ ways to place the puzzles.  }

\problempart Karen suddenly finds two more puzzles.  Now, she has
$n+2$ puzzles and only $n$ lockers.  She has given up worrying about
Tina now.  How many ways can she place the $n+2$ puzzles in $n$
lockers?

\solution{ The answer is $P(n+2,n) = \frac{(n+2)!}{2}$.  There are
$n+2$  puzzles to choose $n$ sets from and to be placed into $n$
lockers.  $P(n+2,n)$ is the number of ways to permute $n$ objects out
of $n+2$ objects which corresponds exactly to the situation here.  }

\problempart Its been a late night, Karen gives up and goes
home. Later on Tina comes by and decides that she will put the away
the $n$  puzzles and discard the two extra sets. After putting
her own set into her locker , she notices that Min and Josh actually
wrote their names on their sets. For reasons known only to Tina, she
decides to place the all the sets in the lockers without regard for
who they belongs to, so long as Min's and Josh's sets are not in
adjacent lockers (assume the lockers are arranged in a line and Tina's
locker is the first in the line).  How many ways can she place the
 puzzles?

\solution{ The number of ways in which Min's set and Josh's set are
next to each other can be counted by treating Min/Josh as one
unit. Tina has $n-1$  puzzles (all minus her own set which was
put inside her locker) to start rearrange with.  Treating Min/Josh as
a unit she now has n-2 sets to rearrange. The total number of
rearrangements where Josh is right before Min is (n-2)! and similarly,
the total number of rearrangements where Min is right before Josh is
(n-2)!.  Adding these two numbers, the total number of rearrangements
where Min and Josh are adjacent is 2*(n-2)!.  Subtracting the total
number of arrangements from that gives the number of arrangements
where Min and Josh are not adjacent : (n-1)! - 2*)n-2)!.}


\problempart 
Jack has a sudden change of heart and decides to be nice to
Tina.  At this time, he also realizes that Christos has
conscientiously written his name on the outside of his  puzzle, so
now Jack knows the correct destinations of two  puzzles.  How many
arrangements are there now?

\solution{As in part (b), we can simply create an injective function
  on the remaining elements, which gives us $(n-2)!$.}

\problempart Say Jack is taking mind-altering drugs and has again
changed his mind about Tina.  Still being able to discern Tina's
and Christos's  puzzles---but wishing to ill-place Tina's---Jack
can place  puzzles in lockers in how many ways?

\solution{Assign 1 to Tina's locker and  puzzle, and 2 to
  Christos's locker and  puzzle.  We know that $|A\cap
  B|=|A|-|A\cap\bar B|$, so if we take $A$ to be the set of functions
  with $f(2)=2$ and $B$ to be the set of functions with $f(1)\not=1$,
  then we know $|A|$ and $|A\cap\bar B|$, the latter of which is the
  solution to the previous part; so, the answer is
  $(n-1)!-(n-2)!=(n-2)(n-2)!$.  }


\end{problemparts}
\end{problem}


TOO LONG, NEVER GOT TO THIS LAST TIME (rad)

%------------------------------------------------
% source: tutorial 8 fall 01
% topic: Pigeon-hole
% last used: fall 01


\begin{problem} 

Let $S$ be the set of numbers $7, 77, 777, \ldots$. Prove that there
is an element of $S$ that is divisible by $2001$.

\solution{We use the pigeonhole principle. Let the pigeons be the
elements $s \in S$, and the holes be the numbers $0 \ldots 2000$.  Let
$s$ be placed in $s \bmod 2001$.

Since there are more than 2001 elements of $S$, some hole must have
two numbers, say $s_i$ and $s_j$, with $i$ and $j$ 7's respectively.
Without loss of generality, assume that $i<j$.

Then, $s_j - s_i = 77 \ldots 700\ldots0$ where there are $j-i$ 7's and
$i$ 0's.  So, $s_j - s_i = s_{j-i} \cdot 10^i$.  Since $s_j \bmod 2001
= r = s_i \bmod 2001$, $s_j - s_i \bmod 2001 = 0$, so $2001 \mid (s_j
- s_i)$.  But $gcd(2001,10^i) = 1$, so 2001 must divide $s_{j-i}$.

}
\end{problem}
\fi
