\documentclass[11pt, twoside]{article}

\usepackage{graphics}
\usepackage{psfig}

\input{macros-course}
\setlength{\parskip}{0.2\baselineskip}          % Interparagraph Spacing

%%% rjr -- I was trying to avoid these, by this is maddening...
\newcommand{\mathify}[1]{\ifmmode{#1}\else\mbox{$#1$}\fi}
\newcommand{\mquote}[1]{\mathify{\textrm{``$#1$''}}}
\newcommand{\mdash}{\mathify{\textrm{-}}}
%\newcommand{\set}[1]{\mathify{\{#1\}}}
\newcommand{\where}{{\ \scriptstyle{|} \ }}
\newcommand{\size}[1]{\mathify{\left| #1 \right|}}
\newcommand{\equivalent}{\mathify{\ \Longleftrightarrow \ }}
\newcommand{\ifandonlyif}{\equivalent}
%\newcommand{\implies}{\mathify{\ \Longrightarrow \ }}
%\newcommand{\etc}{ {\scriptstyle\ldots} }
%\newcommand{\union}{\cup}
%\newcommand{\intersect}{\cap}
\newcommand{\kignore}[1]{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Printing the page layout parameters

\printlayout

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\typein[\answer]{Include solutions? (y/n) }
\def\yes{y}
\ifx\answer\yes
\typeout{}
\typeout{Solutions *INCLUDED*.}
\newcommand{\reading}[1]{}
\newcommand{\omitsolution}[1]{\textbf{Solution.} #1 }
\newcommand{\omitnonsolution}[1]{}
%\usepackage[dark,first,bottom]{draftcopy}
%\draftcopyName{Solutions}{155}
%
\newcommand{\handoutlabel}{sol7}
\newcommand{\handouttitle}{Problem Set 7 Solutions}
\newcommand{\handoutdate}{April 6, 2000}
\newcommand{\collaboration}{}
\newcommand{\titlebar}{%
  \handout{\handoutlabel}{\handouttitle}{\handoutdate}}
%
\else
\typeout{}
\typeout{Solutions *NOT INCLUDED*.}
\newcommand{\reading}[1]{%
%    \mbox{}\\ %
  \hrule%\mbox{} \\ %\bigskip %
  #1%
%    \mbox{} \\ %\bigskip %
  \hrule %
    %\vfill\mbox{}\newpage%
  }
\newcommand{\omitsolution}[1]{}
\newcommand{\omitnonsolution}[1]{#1}
%
\newcommand{\handoutlabel}{ps7}
\newcommand{\handouttitle}{Problem Set 7}
\newcommand{\handoutdate}{Tuesday, March 28, 2000}
\newcommand{\duedate}{Tuesday, April 4, 2000 in lecture}
\newcommand{\collaboration}{\collaborationnote}
\newcommand{\titlebar}{%
  \handout{\handoutlabel}{\handouttitle}{\handoutdate}
  \centerline{{\bf Due  Date: \duedate.}}
  \vspace*{\baselineskip}}
                                %
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}


\titlebar

\reading{%
  \begin{description}\itemsep 0\baselineskip
  \item[Self-study:] \mbox{} \\
    Self-study reading: Rosen \S 2.1--2.2\\
    Self-study problems: \S 2.1 3, 11, 17, 21, 25\ \ \S 2.2 1, 3, 15, 19
    
  \item[Reading:] \mbox{} \\[-\baselineskip]
    \vspace*{-0.5\baselineskip}
    \begin{description}\itemsep 0\baselineskip
    \item[Rosen, \textit{Discrete Mathematics and Its Applications}:]       \S 4.1--4.3
    \end{description}
  \end{description}
  }

\section*{Problems:}

\begin{problems}

% Pigeonhole principle
% ps3 : f99 : 3
  \problem Let $(x_i,y_i)$, $i=1,2,3,4,5$ be a set of five distinct
  points in the plane with integer coordinates.  Show that the
  midpoint of the line segment joining at least one pair of these
  points has integer coordinates.
  
  \omitsolution{The midpoint of the segment whose endpoints are $(a,b)$ and
    $(c,d)$ is $\left(\frac{a+c}{2},\frac{b+d}{2}\right)$.  Clearly the
    coordinates of these fractions will be integers as well if and only
    if $a$ and $c$ share parity (both odd or even) and $b$ and $d$ also
    share parity.  Thus, there are four possible pairs of parities:
    (odd,odd), (odd,even), (even,odd), (even,even).  Since we are given
    five points, the pigeonhole principle guarantees that at least two
    of them will have the same pair of parities; therefore, the midpoint
    of the line segment joining those two points will have integral
    coordinates.}
  
  \problem Divisibility
\begin{problemparts}
  \ppart Show that in any set of $n+1$ positive integers not exceeding
  $2n$ there must be two that are relatively prime.\footnote{If
    integers $a$ and $b$ are relatively prime, then they do not share
    any factors; i.e., for $c\in\naturals$, $c|a$ and $c|b$ implies
    that $c=1$.}

  \ppart Problem removed

\kignore{
  \ppart Show that in any set of $n+1$ positive integers not exceeding
  $2n$, there must be two such that one divides the other. {\bf Hint:}
  write each integer in the form $2^k m$, where $m$ is odd.
}

\end{problemparts}  

  \omitsolution{Partition the set of numbers from $1$ to $2n$ into the $n$
    pigeonholes $\{1,2\},\{3,4\},\ldots,\{2n-1,2n\}$. If we have $n+1$
    numbers from this set (the pigeons), then two of them must be in the
    same hole.  This means that among our collection are two consecutive
    numbers. Clearly consecutive numbers are relatively prime (since
    every common divisor must divide their difference, 1).}

\kignore{
  \problem Consider any sequence of $n$ (not necessarily distinct)
  integers $a_1,\ldots,a_n$.  Prove that there is always a subsequence
  $a_{j},a_{j+1},\ldots,a_k$ with $k \ge j$ such that $\sum_{i=j}^k$
  is divisible by $n$.
}

\problem Problem removed
  
% ps7 : s97 : 2
  \problem  Jelly beans of 8 different colors are in 6 jars.  There are 20
  jelly beans of each color.  Use the pigeonhole principle to prove
  that there is some jar that contains at least two beans each from two
  different colors of jelly beans.
  
  \omitsolution{There are 20 beans of each color. Since there are 6 jars, by
    the strong pigeonhole principle for each color there is a jar
    containing at least $20/6\geq 2$ beans of that color.  Since the
    number of colors is greater then the number of jars, using the
    pigeonhole principle again, there must be a jar containing two pairs
    of jelly beans from two different colors of jelly beans.}

% Sum/product rule
% ps7 : s98 : 6
  \problem Fourteen hackers and eight theoreticians are on the faculty
  of a school's EECS department.  The individuals are distinguishable.
  How many ways are there to select a committee of six members if at
  least 1 hacker must be on the committee?  You may express this in
  terms of binomial coefficients.
  
  \omitsolution{We need to count all possible combinations of people such
    that there is at least one hacker in every combination, but we must
    remember not to count any combinations multiple times.
    
    We can have committees with
    
    1 hacker, 5 theoreticians: $ { 14 \choose 1} {8 \choose 5}$\\
    2 hackers, 4 theoreticians: $ { 14 \choose 2} {8 \choose 4}$\\
    3 hackers, 3 theoreticians: $ { 14 \choose 3} {8 \choose 3}$\\
    4 hackers, 2 theoreticians: $ { 14 \choose 4} {8 \choose 2}$\\
    5 hackers, 1 theoretician: $ { 14 \choose 5} {8 \choose 1}$\\
    6 hackers, 0 theoreticians: $ { 14 \choose 6} {8 \choose 0}$\\
    
    So there are $ { 14 \choose 1} {8 \choose 5} + { 14 \choose 2} {8
      \choose 4} + { 14 \choose 3} {8 \choose 3} + { 14 \choose 4} {8
      \choose 2} + { 14 \choose 5} {8 \choose 1} + { 14 \choose 6} {8
      \choose 9}$ different possibilities for committees.
    
    Another way to solve this problem is to say that there are ${22
      \choose 6}$ different committees, and ${8 \choose 6}$ committees
    of just theoreticians.  So there are ${22 \choose 6} - {8 \choose
      6}$ different possibilities for committees.
}

% ps8 : f95 : 3
  \problem Consider the Towers of Hanoi game with $n$ disks and $3$
  distinct poles.  An arrangement of the disks on the poles is said to
  be legal if no disk rests on a smaller disk. How many different legal
  arrangements of the $n$ disks on the $3$ poles are there?
  
  \omitsolution{ Since each disk is different (and therefore
    distinguishable), we have at least $3^n$ different configurations
    by the product rule: 3 choices for the largest disk, 3 choices for
    the second largest disk, and so on.  Furthermore, since the disks
    on a particular pole must be in order from largest on the bottom
    to smallest on the top, there is a unique way to order the disks
    given a particular assignment to the poles; hence, there are
    exactly $3^n$ different configurations.}

  
% Incl/excl
% ps7 : f94 : 9
  \problem How many integers in the range from 1 to 1000 are not
  divisible by any of the numbers 6, 10, and 15?
  
  \omitsolution{Here we use inclusion-exclusion to count the number of
    integers from 1 to 1000 not divisible by 6, 10, or 15.  Make a
    table, and add the numbers with appropriate signs:
    
    \begin{tabular}{|c|r|r|c|}
      \hline
      divisible by & least common multiple & number of integers & include/exclude \\
      each of      & of divisors           &from 1 to 1000     & $+/-$\\
      \hline
      \hline
      &   1 & 1000 & $+$ \\
      6         &   6 & 166 & $-$ \\
      10        &  10 & 100 & $-$ \\
      15        &  15 &  66 & $-$ \\
      6, 10     &  30 &  33 & $+$ \\
      6, 15     &  30 &  33 & $+$ \\
      10, 15    &  30 &  33 & $+$ \\
      6, 10, 15 &  30 &  33 & $-$ \\
      \hline
    \end{tabular}
    
    \hspace{3in} These add up to 734.}

% ps7 : s98 : 3
  \problem A positive integer is called {\em square-free} if it is not
  divisible by the square of any positive integer greater than 1.  For
  example $35 = 5 \cdot 7$ is square-free but $18 = 2 \cdot 3^2$ is
  not.  $1$ is square-free.  Use inclusion-exclusion to find the
  number of square-free positive integers strictly less than 151.
  
  \omitsolution{We use inclusion-exclusion as done in lecture for the case
    of prime numbers. We first compute the number of positive integers
    less than 150 that are not square free.
    
    Let $A_2$ (respectively, $A_3$, $A_5$, $A_7$, $A_{11}$) be the set
    of multiples of $2^2$ (respectively, $3^2$, $5^2$, $7^2$, $11^2$)
    less than 150. The cardinality of the union of these sets is given
    by
    
    \begin {eqnarray*}
      |A_2 \cup A_3 \cup A_5 \cup A_7 | & = &
      |A_2| + |A_3| + |A_5| + |A_7| + |A_{11}|
      - |A_2 \cap A_3 | - |A_2 \cap A_5|\\
      & = & \lfloor 150/2^2 \rfloor +  \lfloor 150/3^2 \rfloor + \lfloor 150/5^2 \rfloor
      + \lfloor 150/7^2 \rfloor + \lfloor 150/11^2 \rfloor\\
      & &  - \lfloor 150/(2^23^2) \rfloor
      - \lfloor 150/(2^25^2 \rfloor\\
      & = & 37 + 16 + 6 + 3 + 1 -4-1\\
      & = & 58
    \end {eqnarray*}
    Therefore the number of square-free positive integers less than
    150 is
    
    \[ 150 - 58 = 92 \ . \]}

% Permutations/counting
% ps8 : f99 : 1
\problem Enumeration and permutations

\bparts

\ppart Kyle is manager of the MIT Chess Club.  After a long and
grueling match, the players have gone home, leaving Kyle to put the
players' unlabeled chess sets back in their lockers.  If there are
$n$ players/lockers and $n$ chess sets, how many ways could Kyle
place chess sets in lockers such that there is exactly one chess set
in each locker, disregarding the correctness of such placement?

\omitsolution{We can formulate this as a function-counting problem.  Since
  there are $n$ chess sets and $n$ lockers, we can assign each chess
  set a unique number between 1 and $n$ inclusive, and do the same for
  the lockers.  Then, we are looking for an injective function from
  $\set{1,\ldots,n}\rightarrow \set{1,\ldots,n}$.
  
  Note that the first element of the domain has $n$ possible mappings;
  the second has $n-1$ possible mappings (i.e., all but the first
  element); the third has $n-2$ possible mappings (i.e., all but the
  first two); and so on, for all $n$ elements of the domain.  This is
  simply $n!$, the number of permutations of $\set{1,\ldots,n}$.}

\kignore{
\ppart This begs the question: how many ways can Kyle achieve the feat
of placing every chess set in the wrong locker?  Give an expression
for general $n$ and then approximate the value for $n=10$.

\omitsolution{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 =)} }

\ppart Say Kyle recognizes Josh's chess set, so he can place that
one correctly, but recognizes none of the other chess sets.  How many
possible ways can Kyle place chess sets in lockers assuming he at
least gets Josh's right?

\omitsolution{We function count, as before.  Without loss of generality,
  assign Josh's chess set and locker the number 1, and set $f(1)=1$
  in our function.  We can now create an injective function on the
  remaining elements; by part (a), this is simply $(n-1)!$.  }

\ppart Say Kyle really resents Josh's brainpower, and decides to get
even by putting Josh's chess set in another student's locker.  How
many ways can he place chess sets in lockers assuming he does not
place Josh's chess set into Josh's locker?

\omitsolution{Again, we function count.  (Notice a pattern?)  Without loss
  of generality, assign Josh's chess set and locker the number 1,
  as before.  We can first choose an element $j\not=1$ from the domain
  to map to $1$ ($(n-1)$ ways).  Then, we note that we have $n-1$
  elements of the domain and $n-1$ elements of the codomain in which
  we want an injection, which we can choose in $(n-1)!$ ways from part
  (a).  This gives us $(n-1)(n-1)!$, which makes sense since, from
  part (b), $(n-1)(n-1)!+(n-1)!=n!$.}

\ppart Kyle has a sudden change of heart and decides to be nice to
Josh.  At this time, he also realizes that Shishir has
conscientiously written his name on the outside of his chess set, so
now Kyle knows the correct destinations of two chess sets.  How many
arrangements are there now?

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

\ppart Say Kyle is taking mind-altering drugs and has again changed
his mind about Josh.  Still being able to discern Josh's and
Shishir's chess sets---but wishing to ill-place Josh's---Kyle can
place chess sets in lockers in how many ways?

\omitsolution{Assign 1 to Josh's locker and chess set, and 2 to
  Shishir's locker and chess set.  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)!$.  }

\eparts



% ps7 : f95 : 2
\problem
On a set of $n$ elements how many of the following are there
\bparts

\ppart binary relations? \omitsolution{$2^{n^2}$ since there are this many
  different $0-1$ matrices of order $n$.}

\ppart symmetric binary relations? \omitsolution{The matrix associated with a
  symmetric relation is symmetric.  Since there are $2^ {n+{n\choose
      2}}$ different symmetric matrices there are an equal number of
  symmetric relations.}

\ppart reflexive binary relations? \omitsolution{The matrix associated with a
  reflexive relation has $1$'s along the main diagonal . Hence the
  number of such matrices, and therefore reflexive relations, is
  $2^{n^2 - n}$ .}

\ppart symmetric and reflexive binary relations? \omitsolution{The matrix
  associated with a symmetric and reflexive relation is symmetric and
  ha s $1$'s along the main diagonal. Hence the number of such
  relations is $2^{{n\choose 2} }$.}

\ppart symmetric or reflexive binary relations? \omitsolution{The number of
  symmetric or reflexive relations $=$ the number of reflexive
  relations $+$ the number of symmetric relations $-$ the number of
  reflexive and symmetric relations $= 2^{n^2 - n} + 2^{n+{n\choose
      2}} - 2^{{n\choose 2}}$.}

\eparts



\end{problems}

\end{document}
