\documentclass[12pt]{article}
\title{Math 187 Test II}
\author{Dr. Holmes}
\begin{document}
\maketitle
The exam begins at 7:50 am and ends at 9:30 am. You may use a standard
scientific calculator without graphing or symbolic computation
capabilities. If your calculator has built-in permutations and
combinations, make sure you write work that shows that you know how to
compute permutations (falling factorials) and combinations (binomial
coefficients) without using the built-in functions. In general, any
work done on a calculator should be fully set up on your paper. Cell
phones and PDAs must be turned off and out of sight.
Grades will be posted by the magic number on the first page.
\newpage
\begin{enumerate}
\item Venn diagrams
\begin{enumerate}
\item Give a pair of Venn diagrams illustrating the truth of $$A \cap
(B \cup C) = (A \cap B) \cup (A \cap C)$$ Be sure to include a key to
help me understand the shadings you use and to outline the final
result sets clearly.
\newpage
\item Give a pair of Venn diagrams illustrating the fact that
$$A-(B-C) = (A-B)-C$$ is false, and give explicit examples of finite
sets $A$, $B$, $C$ for which it is false (your diagram can help you do
this).
\end{enumerate}
\newpage
\item List all partitions of $\{1,2,3,4\}$ (a partition of a set $A$
is a set of nonempty subsets of $A$ such that each element of
$A$ belongs to exactly one element of the partition).
\newpage
\item How many different anagrams can be made from the word ANAGRAMS?
From the word DIFFERENT?
\newpage
\item You want to make a necklace with 20 beads of 5 different colors.
The necklace has a clasp past which beads can't be moved.
How many ways can the necklace be made if you have 4 beads of each color?
\vspace{1 in}
How does this change if there is no clasp, so beads can be moved freely
all the way around the necklace?
\vspace{1 in}
Suppose for the rest of the problem that you have 20 beads of each
color (so you can use as many beads of each color as you like, but
still no more than 20 beads in the necklace in all)?
\vspace{1 in}
In how many ways can you choose a handful of 20 beads to put on the necklace
(this is just a handful, order doesn't matter).
\vspace{1 in}
In how many ways can you make a necklace of 20 beads?
\newpage
\item How many subcommittees with five members can be formed from
a committee with ten members?
\vspace{1 in}
How many ways can the subcommittees be chosen if each subcommittee has
a chair and a treasurer chosen from among its five members?
\vspace{1 in}
Write the first four terms of the expansion of $(x+y)^10$ (here I do
want the coefficients fully computed, not just set up, and certainly not
in binomial coefficient notation).
\newpage
\item At a foreign language institute, 16 students study French,
19 study German, 17 study Russian, 8 study French and German, 7 study
German and Russian, 9 study French and Russian. Of the 31 students,
how many study all three languages?
You are required to set this up
and solve it using the inclusion-exclusion method, in a way which makes
it clear that you understand this method.
\newpage
\item Consider the semiformal sentence
For every integer $x$, there is an integer $y$ such that $y^2=x$.
Write this in formal quantifier notation (with $\forall$, $\exists$),
without any English words.
\vspace{1 in}
Give an English translation (plain English without any letters) of
what this says (it is not true!)
\vspace{1 in}
Write the negation of this sentence in quantifier notation with all
negations moved inside the quantifiers as far as possible.
\vspace{1 in}
Write the negation in semiformal English as above and as a natural
English statement (true this time).
\vspace{1 in}
\newpage
\item Properties of relations
\begin{enumerate}
\item Consider the relation ``$x$ is a full sibling of $y$'' on human
beings ($x$ and $y$ are brothers or sisters, excluding half-brothers
and half-sisters). Is this relation reflexive? irreflexive?
symmetric? antisymmetric? transitive? Explain each of your answers
briefly. Some of these are mildly tricky.
\newpage
\item Consider the relation $x\,T\,y$ on integers defined by $3|(x-y)$
($x-y$ is divisible by 3, or $x \equiv y \,{\tt mod} \,3$).
Prove that this is an equivalence relation (there are three things you
need to prove: list them (clearly identifying them by name) and prove
them).
\vspace{3 in}
List the equivalence classes under this relation if we restrict our
attention to positive integers less than 12.
\end{enumerate}
\newpage
\item Give a proof by contradiction that the sum of two consecutive
integers $n$ and $n+1$ cannot be even.
You may not use the theorem that odd numbers are not even. You may
use the fact that $\frac 12$ is not an integer, or the theorem that
there is no integer between 0 and 1. Don't forget to use the
definition of ``even''!
Much of the credit is
involved in setting up the proof correctly (demonstrating that you
know what a proof by contradiction is).
\newpage
\end{enumerate}
\end{document}