Each of these questions has multiple parts.
Presumably, we will select parts according to what other people like
best, length, balance of topics, and difficulty. 

1. (Infinite sets)

Indicate whether each of the following sets is finite (F), countably
infinite (CI), or uncountably infinite (UI) by circling the right
answer.

\begin{enumerate}
\item
The set of all subsets of the even numbers.         F   CI   UI   Ans. UI
\item
The set of all (finite) binary strings of even length. 
                                                    F   CI   UI   Ans. CI
\item
The set of all even primes.                         F   CI   UI   Ans. F
\item
The set of all infinite binary strings in which 1's only appear in
even-numbered positions (but they don't necessarily appear in all
even-numbered positions).                           F   CI   UI   Ans. UI
\item
The set of all infinite binary strings containing a (finite) even
number of 1's.                                      F   CI   UI   Ans. CI
\item
The set of all pairs of even-length strings.        F   CI   UI   Ans. CI
\item
The set of all even-size sets of even-length binary strings.
                                                    F   CI   UI   Ans. CI
\end{enumerate}


2. (Pigeonhole Principle)

The Pigeonhole Principle can be used to prove each of the following
statements.  In each case, say what the pigeons are, what the holes
are, and what the function is that maps pigeons to holes.

[[[Might want to give an example]]]

\begin{enumerate}
\item
In any group of 8 children, there are two who are born on the same day
of the week.

Pigeons:________________________  

Ans: 8 children

Holes:__________________________

Ans: 7 days of the week

Function:_______________________

was born on

\item
This afternoon, 19 doves flew through 32 holes in a fence in such a
way that at least one dove flew through each of the holes.
Therefore, some dove flew through at least 2 holes.

Pigeons:  32 holes

Holes:  19 doves

Function: is flown through by

\item
In any tournament digraph in which everyone wins at least 1 match,
there must be 2 nodes with the same number of wins.

Pigeons:  n nodes

Holes:  numbers 1, 2, ..., n-1

Function: wins exactly this number of games


\item
In any collection of 7 different subsets of $\{a,b,c,d,e\}$, the sets
aren't all pairwise disjoint.

Pigeons:
6 nonempty subsets

Holes:
5 elements a,b,c,d,e

Function:
contains as its smallest element
\end{enumerate}


3. (Unions, products, permutations)

You might be interested in knowing that 40 students in the class have
formed a new living group, for students who especially enjoy 6.042 and
want to talk about it all the time, even when they are at home.

\item
They have had 3 discussion meetings so far.
34 attended the first 6042 discussion meeting 
32 meeting 2
30 3
28 both 1 and 2
27 both 1 and 3
26 both 2 and 3
25 1, 2, and 3
Anyone who missed all three of the meetings was (think of a
penalty).
How many students were (...)?

40 - number attending at least one
Number attending at least one obtained usion inclusion/exclusion:
34 + 32 + 30 - 28 - 27 - 26 + 25 = 40
Answer is 0

\item
The 40 students work together on HW discussion in 20 groups of 2.
How many different slates of living group officers (pres, VP,
secy-treas) are possible, if you can't have 2 officers from the same
hw group?

40 x 38 x 36

\item
The living group has 40 different cleaning chores.
They plan to allocate chores to students, one chore per student, 
choosing chores in the order of their grads on this quiz.
(They haven't cleaned anything yet this term...)
How many different assignments of chores to students are there?

40!
(the choosing in order of quiz grades is irrelevant)

\item
Theory Pig has decided to visit the living group for 40 days, and
every day will choose some student to follow around.
He might follow the same student any number of times.
How many different patterns...

40^{40}
\end{enumerate}



