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

%\hidesolutions         
%\showsolutions
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

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

%% Pigeon-hole, Inclusion-exclusion, sum rule, product rule

% source: ?, problem repository
% last used: fall 01
% topics: false proofs for counting
% \begin{problem} 
% 
% In each case, state whether the argument is correct or incorrect. If
% incorrect, try to fix it.  If correct, prove it.
% \begin{problemparts}
% 
% \problempart Since there are 26 letters in the English alphabet, the
% Product Rule implies that the number of four-letter English words is
% $26^4$.
% 
% \solution{Incorrect. Not every four letter sequence is an English
% word, \eg ``xxxx'' is not English. The best we can do here is say that
% the number of four-letter English words is less than $26^4$.}
% 
% \problempart The number of 4-digit numbers which have a digit 7
% somewhere is $4 * 10^3$, since by the sum rule, we must add the counts
% for each position the 7 could be in; and since for each such position,
% there are $10^3$ possible numbers by the product rule. (Assume that
% the numbers can have leading zeros and that each digit can take values
% 0-9.)
% 
% \solution{Incorrect, since it double counts numbers containing more
% than one 7 (for example 7707 is counted 3 times). The sum rule does
% not apply if the sets being added are not disjoint. There are many
% different ways of counting this, however one very elegant way of
% counting this is by counting the complement --- the number of 4-digit
% numbers with at least one 7 is just the number of all possible 4-digit
% numbers minus the number of those which do \emph{not} contain 7,
% namely, $10^4 - 9^4$. This is a common way of counting things where
% {\em at least one} special event occurs.
% 
% Another way to do this is to count the number of 4-digit numbers with
% 1 7 exactly, 2 7's exactly, etc.  There are $4*9^3$ with 1 7,
% $\frac{4*3*9^2}{2}$ with 2 7's, $\frac{4*3*2*9}{3*2}$ with 3 7's, and
% 1 with 4 7's.}
% 
% \end{problemparts}
% \end{problem} 

%% New Problem (RAD) fall 02
%% real time debugging?

\begin{problem} 
Let $S$ be the set of all $4$-digit base-$10$ numbers that contain the
digit $7$ somewhere.  (Numbers can start with a $0$, and thus $0007\in
S$.)  The size of $S$ can be determined in several different ways.

\begin{problemparts}
\problempart Determine $\card{S}$ by counting the number of all
possible $4$-digit numbers minus the number of those that do
\emph{not} contain~$7$.

\solution{
\begin{eqnarray*}
\card{S} & = & 10^4 - 9^4\\ 
& = & 3439\ .
\end{eqnarray*}
}

\problempart Determine $\card{S}$ by counting the set of numbers where
the first $7$ occurs in the first digit, where the first $7$ appears
as the second digit, where the first $7$ appears as the third digit,
and where the first $7$ appears as the last digit.

\solution{
\begin{eqnarray*}
\card{S} & = & 1\cdot 10\cdot 10 \cdot 10 \\
& & \hspace*{1em} + 9 \cdot 1 \cdot 10 \cdot 10 \\
& & \hspace*{1em} + 9 \cdot 9 \cdot 1 \cdot 10 \\
& & \hspace*{1em} + 9 \cdot 9 \cdot 9 \cdot 1 \\
& = & 1000 + 900 + 810 + 729\\
& = & 3439\ .
\end{eqnarray*}
}

\problempart Determine $\card{S}$ by counting the number of $4$-digit
numbers with exactly one $7$, with exactly two $7$'s, with exactly
three $7$'s and with exactly four $7$'s.

\solution{
\begin{eqnarray*}
\card{s} & = & 4\cdot 9^3 + 6\cdot 9^2 + 4\cdot 9 + 1\\
& = & 2916 + 486 + 36 + 1\\
& = & 3439\ .
\end{eqnarray*}
}

\problempart Argue in each case that the counting method is correct by
arguing that (1) everything has been counted at least once (2) nothing
has been counted twice.

\solution{


\textbf{Part A:}
$\card{S} = \card{ \text{all 4-digit base-10 numbers} } - \card{ \text{4-digit base-10 numbers with no seven} }$

All 4-digit numbers with a seven is counted \emph{exactly} once in $\card{ \text{\emph{all 4-digit base-10 numbers}} }$.  
4-digit numbers without a seven are counted once in  $\card{ \text{\emph{all 4-digit base-10 numbers}} }$ but are subtracted away in $\card{ \emph{\text{4-digit base-10 numbers with no seven}} }$, so they are not counted.  


\textbf{Part B:}
Let $P_i$ represent the set of 4-digit numbers with the first seven appearing in the $ith$ digit.  Then we count as follows:

$\card{S} = \card{P_1} +  \card{P_2} +  \card{P_3} +  \card{P_4}$

This way of calculating $\card{S}$ utilizes the sum rule.  Each of the sets $P_i$ represent the numbers where the first seven appears in the $ith$ position, with $i$ being 1, 2, 3, or 4.  These sets are disjoint because the first occurrence of the seven cannot be in more than one position.  This guarantees that numbers with a seven only are counted once.

Numbers with a seven must be counted somewhere because the $7$ must appear first in some position between $1$ and $4$, and will be included in one of the $P_i$s.  Numbers with no seven will not be counted in any of the sets.


\textbf{Part C:}
Let  $S_i$ represent the set of 4-digit numbers with exactly $i$ sevens.  Then we count as follows:

$\card{S} = \card{S_1} +  \card{S_2} +  \card{S_3} +  \card{S_4}$

This way of calculating $\card{S}$ again utilitizes the sum rule.  Each of the sets $S_i$ represent 4 digit numbers with \emph{exactly} $i$ sevens.  They are disjoint since a number can not have exactly $i$ sevens, but also have exactly $j$ sevens, where $i \neq j$.  This guarantees that all numbers with a seven are only counted once.

Numbers that have a seven must have either 1 seven, 2 sevens, 3 sevens, or 4 sevens.  Therefore, they would be included in one of the above $S_i$s and would be accounted for.  4-digit numbers cannot have more than 4 sevens, and 4-digit numbers with 0 sevens are not counted.

}

\end{problemparts}
\end{problem}


\begin{problem}
% \problemdata     
% {S01-PS7-1}           
% {sets, inclusion-exclusion}              
% {} 		
% {S01-PS7}
% {S01 Karger}

Each of the $49$ students in an MIT class understands mathematical
equations, exercises regularly, or loves literature.  Of these,

\begin{itemize}
\item
$20$ students understand mathematical equations,

\item
$20$ students exercise regularly,

\item
$26$ students love literature,

\item
$36$ students understand mathematical equations or exercise regularly,

\item
$38$ students understand mathematical equations or love literature, and

\item
$40$ students exercise regularly or love literature.
\end{itemize}

\begin{problemparts}
\problempart
How many students understand mathematical equations \emph{and}
exercise regularly \emph{and} love literature?

\solution{ 

Let $A$ denote the set of students who understand mathematical
equations, let $B$ denote the set of students who exercise regularly,
and let $C$ denote the set of students who love literature.  We are
given that $ \card{A\cup B\cup C} = 49$, $\card{A}=20$, $\card{B}=20$,
$\card{C}=26$, $\card{A\cup B}=36$, $\card{A\cup C}=38$, and
$\card{B\cup C}=40$; whence
\begin{eqnarray*}
\card{A\cap B\cap C} & = & 
      \card{A\cap B} +\card{C} - \card{(A\cap B)\cup C}\\
& = & \card{A} + \card{B} - \card{A\cup B} + \card{C} 
      - \card{(A\cup C) \cap (B\cup C)}\\
& = & \card{A} + \card{B} - \card{A\cup B} + \card{C} 
      - \card{A\cup C} - \card{B\cup C} + \card{A\cup B \cup C}\\
& = & 20 + 20 - 36 + 26 - 38 - 40 + 49\\
& = & 1\ .
\end{eqnarray*}
In line 1 we apply inclusion-exclusion, in line 2 we apply
inclusion-exclusion and distributive laws, and in line 3 we apply
inclusion-exclusion.  

Ask the students to verify their answers by drawing the Venn diagram.

}


\problempart Suppose you don't know the number of students in the
class, but the rest of the information is the same.  What is the
largest possible number of students who understand mathematical
equations \emph{and} exercise regularly \emph{and} love literature?
For this situation, how many students are in the class?

\solution{

Since $A\cap B\cap C \subseteq A\cap B$, it follows that we must have
$\card{A\cap B\cap C} \leq \card{A\cap B}$, and likewise, we have
$\card{A\cap B\cap C} \leq \card{A\cap C}$ and $\card{A\cap B\cap C}
\leq \card{B\cap C}$.  By inclusion-exclusion, we have
\begin{eqnarray*}
\card{A\cap B} & = & \card{A} + \card{B} - \card{A\cup B}\\
& = & 20 + 20 - 36\\
& = & 4\ ,
\end{eqnarray*}
and similarly,
\begin{eqnarray*}
\card{A\cap C} & = & \card{A} + \card{C} - \card{A\cup C}\\
& = & 20 + 26 - 38\\
& = & 8
\end{eqnarray*}
and
\begin{eqnarray*}
\card{B\cap C} & = & \card{B} + \card{C} - \card{B\cup C}\\
& = & 20 + 26 - 40\\
& = & 6\ .
\end{eqnarray*}
The strongest of the three constraints is therefore $\card{A\cap B\cap
C} \leq \card{A\cap B} = 4$.  Plugging the value $4$ in for
$\card{A\cap B\cap C}$, we find we can satisfy all the conditions of
the problem.  (Verify by Venn diagram.)  The total number of students
is~$52$.

Make sure the students understand that obtaining the constraint
$\card{A\cap B\cap C} \leq 4$ is insufficient.  They also must show
that $4$ actually works.

}

\end{problemparts}

\end{problem}

\end{document}
