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




\begin{enumerate}
\item There are 49 students in a class at MIT who either understand mathematical 
equations, exercise regularly, or love school. Of these:

\noindent
20 students understand mathematical equations.

\noindent
20 students exercise regularly.

\noindent
26 students love school.

\noindent
36 students understand mathematical equations or exercise regularly.

\noindent
38 students understand mathematical equations or love school.

\noindent
40 students exercise regularly or love school.

\vspace{1mm}

\noindent
How many students understand mathematical equations AND exercise
regularly AND love school?

\solution{
  
Let $A$ denote the set of students who understand mathematical
equations, $B$ denote the set of students who exercise
regularly, and $C$ denote the set of students who love school.
Then we are given that $ | A\cup B\cup C | = 49$, 
$| A |=20$, $| B |=20$, $| C |=26$, 
$| A\cup B |=36$, $| A\cup C |=38$, and $| B\cup C |=40$.
\begin{eqnarray*}
| A\cap B\cap C | & = & 
      | A\cap B | +| C | - | (A\cap B)\cup C |\\
& = & | A | + | B | - | A\cup B | + | C | 
      - | (A\cup C) \cap (B\cup C) |\\
& = & | A | + | B | - | A\cup B | + | C | 
      - | (A\cup C) | - | (B\cup C) | + | (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.
}    
\item Show that there are fewer than 
50,000 prime numbers less than or equal to 210,000. \hint they are actually far fewer than 50,000 (about 19,000)

\solution{
Since natural numbers are either composite or prime, we can instead
show that there are at least $210,000 - 50,000 = 160,000$ composite
numbers less than or equal to $210,000$.  

Let's count composite
numbers by counting the multiples of $2, 3, 5$, and $7$. Notice that in the calculation below, we need to subtract 1 each time because $2, 3, 5$, and $7$ should not be counted as composites since they are prime!

\[\begin{array}{llr}
\mbox{multiples of }2: &\lfloor 210,000/2 \rfloor -1 &= 105,000-1\\
\mbox{multiples of }3: &\lfloor 210,000/3 \rfloor -1&= 70,000-1\\
\mbox{multiples of }5: &\lfloor 210,000/5 \rfloor -1&= 42,000-1\\
\mbox{multiples of }7: &\lfloor 210,000/7 \rfloor -1&= 30,000-1\\
\hline
  &&+ 246,996
\end{array}\]

However, we have double counted the numbers which are multiples of two
of $\{2, 3, 5, 7\}$.  So, using inclusion/exclusion, we subtract these
back out\footnote{Notice that we do not subtract 1 from each result since 6, 10, 14 etc are composites} :

\[\begin{array}{llcr}
\mbox{multiples of }\{2,3\}: & \lfloor 210,000/6\rfloor   &= &  35,000\\
\mbox{multiples of }\{2,5\}: & \lfloor 210,000/10\rfloor  &= &  21,000\\
\mbox{multiples of }\{2,7\}: & \lfloor 210,000/14\rfloor  &= &  15,000\\
\mbox{multiples of }\{3,5\}: & \lfloor 210,000/15\rfloor  &= &  14,000\\
\mbox{multiples of }\{3,7\}: & \lfloor 210,000/21\rfloor  &= &  10,000\\
\mbox{multiples of }\{5,7\}: & \lfloor 210,000/35\rfloor  &= &   6,000\\
\hline
  &&& - 101,000
\end{array}\]

Now, we must add back in the numbers which are multiples of three of
$\set{2, 3, 5, 7}$:

\[\begin{array}{llcr}
\mbox{multiples of }\{2,3,5\}: & \lfloor 210,000/30\rfloor  &=& 7,000\\
\mbox{multiples of }\{2,3,7\}: & \lfloor 210,000/42\rfloor  &=& 5,000\\
\mbox{multiples of }\{2,5,7\}: & \lfloor 210,000/70\rfloor  &=& 3,000\\
\mbox{multiples of }\{3,5,7\}: & \lfloor 210,000/105\rfloor &=& 2,000\\
\hline
 &&& +  17,000
\end{array}\]

And subtract out the multiples of $2\cdot3\cdot5\cdot7 = 210$:

\[\begin{array}{llr}
\mbox{multiples of }\{2,3,5,7\}: & \lfloor 210,000/210\rfloor &=  1,000\\
\hline
 &&-  1,000
\end{array}\]

Totaling, we get $246,996 - 101,000 + 17,000 - 1,000 = 161,996$, which is
more than the $160,000$ composite numbers whose existence we needed to
establish.

} 
\end{enumerate}

\end{problem}
