\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}

\newcommand{\lcm}{\mbox{lcm}}
\begin{document}

\handout{sample}{Practice Problems}{Oct. 16, 1994}
\medskip

Here are some practice problems for Quiz 1.

\medskip
\begin{enumerate}

\item True or false.  (For a set $X$, ``$2^X$'' denotes the set of all 
subsets of $X$.)
\begin{itemize}
\item $\emptyset \in \{ \emptyset\}$.
\item $\emptyset \subseteq \{ \emptyset\}$.
\item $\emptyset \in \emptyset$.
\item $\emptyset \subseteq \emptyset$.
\item $\{ a,b \} \in \{a, b, \{a, b\}\}$.
\item $\{ a,b \} \subseteq \{a, b, \{a, b\}\}$.
\item $\{ a,b \} \subseteq 2^{\{a, b, \{a, b\}\}}$.
\item $\{\{ a,b \}\} \in 2^{\{a, b, \{a, b\}\}}$.
\item $\{a, b, \{a,b\}\} - \{a, b\} = \{a, b\}$.
\end{itemize}

\item Show that there is no bijection from $X$ to $2^X$.

\item
$\nats$ is a well-ordered set.  However, $\reals$ is not.  
Give a non-empty set of positive real numbers which
does not have a least element.

\item
For $a,b\in \nats$, the least common multiple, $\lcm(a,b)$, of $a$ and $b$
is the least positive number
such that $a\divides\lcm(a,b)$ and $b\divides\lcm(a,b)$.
Prove that $a\cdot b = \gcd(a,b)\cdot \lcm(a,b)$.

\item
For $n,m\in\nats$ with $n\geq m$, 
we recursively define ${n \choose m}$ (read ``$n$ choose $m$'') as follows.
\begin{itemize}
\item ${n \choose 0} =1$,
\item ${n \choose n} =1$,
\item ${n \choose m} = {{n-1} \choose m} + {{n-1} \choose {m-1}}$.
\end{itemize}
Prove that ${n \choose m} =\frac{n!}{m!(n-m)!}$.

\item
You have \$5 and want to spend it all on apples and bananas.  Apples are
80 cents, and bananas are 30 cents.  What are the possibilities?

\item
Let $F_n$ denote the $n$th Fibonacci number.  Prove that there are constants
$a,b,q,r$ such that $F_n = a\cdot q^n + b\cdot r^n$.  Identify these constants.

\item 
Let $G=(V,E)$ be an undirected graph.  Define the relation R as
\[
R = \{ (a,b) \in V\times V | \mbox{ there exists a path from $a$ to $b$} \}
\]
Show that $R$ is an equivalence relation.  What are the equivalence
classes of $R$?
Is $R$ an equivalence relation for directed graphs?

\item How many equivalence relations are there on a set of 4 elements?
%	Ans:  15.  (In general, the Bell number B_n.)

\item Draw directed graphs representing (1) a relation that is reflexive,
transitive, and antisymmetric,  and (2) a relations that is
reflexive, transitive, and neither symmetric nor antisymmetric.

\item Under what conditions does a relation represent a function?

\item
Show that every connected, undirected graph $G=(V,E)$ has a
spanning tree, that is there exits a graph $G'=(V,E')$ such that
$G'$ is a tree and $E'$ is a subset of $E$.

\item
Let $f:A \to B$ and $g: B\to C$ be functions.
\begin{enumerate}
\item
If $g \circ f: A\to C$ is a surjection, are $g$ and $f$ necessarily
surjections?

\item
If $g \circ f: A\to C$ is an injection, are $g$ and $f$ necessarily injections?
\end{enumerate}

\item
Prove: $(\neg A \wedge ((A\implies B)\implies C)) \implies C$.

\item
Let $S$ be a subset of $\{1,2,3, \ldots, 300\}$ with 201 elements.
Prove there exists $x,y\in S$, such that $3x\divides y$.

\item
Some real numbers have multiple decimal representations
(e.g., 0.29999... = 0.30000...).  Let S be the set of all such
real numbers.  Is S countable or uncountable?  Justify your answer.

\item
If $f(x) = \Theta(g(x))$, does $f(x)/g(x)$ converge?  
What if $f(x) = \omega(g(x))$
or $f(x) = o(g(x))$?

\item
Fund A will pay me \$2000 a year (starting today) for the next 20 years
(total of 20 payments).  Fund B will pay me \$1000 a year (starting
today) with an annual growth rate of 6\% for the next 25 years.  (i.e.
Fund B will pay \$1000 this year, \$1060 the next year, etc).  Given an
annual interest rate of 8\%, which fund do I prefer?


%	No probability (worse yet, ``odds'') yet!	-Steve
%	\item
%	You flip a coin 100 times.  You expect the outcome to be heads about 
%	50 times.   Estimate the odds that it's heads exactly 50 times.
%	\item
%	Consider an $n \times n$ 
%	matrix of 0's and 1's mod 2.  For large $n$, if the matrix
%	entries are chosen at random, what is the order of growth of the 
%	odds that the matrix is invertable?

\end{enumerate}

\end{document}


