

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Midterm
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Midterm
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\problem {\bf (8 points)}  You might be interested to know that 42
students in the class have formed a new living group--- 042 House---
for students who especially enjoy 6.042 and want to talk about it all
the time, even when they are at home.  For this problem, your
solutions may be expressions.

\begin{problemparts}

\problempart {\bf (4 points)} So far at 042 House there have been three
meetings, which house members refer to as $a$, $b$, and $c$.  (That's
the kind of people they are.)  The secretary recorded the following
attendance information.

\begin{itemize}
\item 34 attended meeting $a$
\unspace
\item 32 attended meeting $b$
\unspace
\item 30 attended meeting $c$
\unspace
\item 28 attended meetings $a$ and $b$
\unspace
\item 27 attended meetings $a$ and $c$
\unspace
\item 26 attended meetings $b$ and $c$
\unspace
\item 25 attended meetings $a$, $b$, and $c$
\end{itemize}

How many house members punted all three meetings?

\examonly{\vspace{1.5in}}

\solution{
Let $A$, $B$, and $C$ denote the sets of people that attended meetings
$a$, $b$, and $c$.  The number of people that attended at least one
meeting is $|A \cup B \cup C|$.  We can compute this quantity with the
Inclusion-Exclusion Principle:

\begin{eqnarray*}
|A \cup B \cup C|
    & = &   |A| + |B| + |C|
        - |A \cap B| - |A \cap C| - |B \cap C|
        + |A \cap B \cap C| \\
    & = &   34 + 32 + 30 - 28 - 27 - 26 + 25 \\
    & = &   40
\end{eqnarray*}

Since 40 people attended at least one meeting, two people punted all
three meetings.  }

\problempart {\bf (2 points)} The 042 House is about to have its first
wild party.  They have identified 23 distinct preparatory chores, such
as working out a good mix of practice problems to entertain the
guests.  One student must be assigned to each chore, and no student
can be assigned to two or more chores.  In how many ways can students
be assigned to chores?

\examonly{\vspace{0.75in}}

\solution{
This is the number of 23-permutations of a 42-element set, which is
$42!/19!$.  }

\problempart {\bf (2 points)}
Theory Pig has decided to visit the living group for 30 days, provided
that one student attend to his needs each day.  A student may attend
to Theory Pig any number of times.  In how many ways can the sequence
of attendants be chosen?

\solution{
There are 42 possible attendants each day.  By the product rule, there
are $42^{30}$ possible sequences of attendants.
} \end{problemparts}


\problem {\bf (10 points}) Indicate whether each of the following sets
is finite (F), countably infinite (CI), or uncountably infinite (UI)
by circling the right answer.  {\em Note that an even quantity is
necessarily finite.}

\bigskip

\begin{tabular}{lccc}
The set of all binary strings with even length.
    & F & \us{CI} & UI \\ \\
The set of all infinite binary strings with 1's in every even position.
    & F & CI & \us{UI} \\
(Odd positions may contain either a 0 or a 1.) \\ \\
The set of all infinite binary strings with an even number of 1's.
    & F & \us{CI} & UI \\ \\
The set of even primes.
    & \us{F} & CI & UI \\ \\
The set of all even-size sets of even-length binary strings.
    & F & \us{CI} & UI \\ \\
\end{tabular}











