%sample.tex
\documentclass[12pt]{article}
\usepackage{homework}
\sethwtitle{HW1 - Math 310 - Spring 2011}%
\sethwauthor{Mark Goadrich}%
\makehwheader%

\begin{document}
\setlength{\parskip}{10pt plus 1pt minus 1pt}

\makehwtitle%

\section{Sets and Logic}

\subsection{$A=\{1, 2, 3, 4\}, C=\{5, 6, 7, 8\}, B=\{n ~|~ n \in A$ and $n + m = 8$ for some $m \in C\}$. Show that A is not a subset of B.}

\subsection{In a group of students, each student is taking a mathematics course or a computer science course or both. One-fifth of those taking a mathematics course are also taking a computer science course, and one-eighth of those taking a computer science course are also taking a mathematics course. Are more than one-third of the students taking a mathematics course?}

\subsection{Write the truth table for $(p ~ \vee ~ q ) ~ \wedge ~ \neg ~ p$}

\subsection{Write the truth table for $\neg ~ (p ~ \wedge ~ q ) ~ \vee (~ \neg ~ q ~ \vee ~ r)$}

\subsection{Show whether or not $(p ~ \rightarrow ~ q) ~ \wedge ~ (q ~ \rightarrow ~ r) ~\equiv ~ (p ~ \rightarrow r)$}

\subsection{Write the negation of "Shirley will either take the bus or catch a ride to school" using DeMorgan's laws.}

\subsection{Determine if the following argument in valid}
\begin{align}
&(p ~ \rightarrow q) ~ \wedge ~ (r ~ \rightarrow ~ s) \\
&p ~ \vee ~ r \\
 \hline
&\therefore ~ q ~ \vee ~ s
\end{align}

\subsection{Determine the truth value of $\forall x (x > 1 \rightarrow \frac{x}{x^2 + 1} < \frac{1}{3})$ and  $\exists x (x > 1 \rightarrow \frac{x}{x^2 + 1} < \frac{1}{3})$}

\subsection{Show symbolically that the conclusion follows from the hypothesis. HYPOTHESIS: Everyone in the discrete mathematics class loves proofs. Someone in the discrete mathematics class has never taken calculus. CONCLUSION: Someone who loves proofs has never taken calculus.}

\pagebreak

\section{Proofs}

\subsection{Prove that for all integers $m$ and $n$, if $m$ and $m + n$ are even, then $n$ is even.}

\subsection{Prove or disprove that $\overline{X - Y} = \overline{Y - X}$ for all sets $X, Y$.}

\subsection{Prove or disprove that $X \times (Y \cup Z) = (X \times Y) \cup (X \times Z)$ for all sets $X, Y, Z$. }

\subsection{Show, by giving a proof by contradiction, that if 100 balls are placed in 9 boxes, some box contains 12 or more balls.}

\subsection{Prove that for every $n \in \mathbb{Z}, n^3 + n$ is even.}

\subsection{Use induction to prove that for every positive integer $n$, $1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \cdots + n(n + 1) = \frac{n(n + 1)(n + 2)}{3}$}

\subsection{Given $n$ 0's and $n$ 1's distributed in any manner whatsoever around a circle, show, using induction on $n$, that it is possible to start at some number and proceed clockwise around the circle to the original starting position so that, at any point during the cycle, we have seen at least as many 0's as 1's.}

\subsection{Show that postage of 24 cents or more can be achieved by using only 5-cent and 7-cent stamps.}

\subsection{Suppose you begin with a pile of $n$ stones and split this pile into $n$ piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile you multiply the number of stones in each of the two smaller piles you form, so that if these piles have $r$ and $s$ stones in them, respectively, you compute $rs$. Show that no matter how you split the piles, the sum of the products computed at each step equals $\frac{n(n-1)}{2}$}

\pagebreak

\section{Functions, Sequences, Relations and Algorithms}

\subsection{Let $f$ be a function from $X$ to $Y$. Prove that $f$ is one-to-one if and only if $f(A \cap B) = f(A) \cap f(B)$ for all subsets $A$ and $B$ of X.}

\subsection{For the sequence $r_n = 3 \cdot 2^n - 4 \cdot 5^n, n \ge 0$ prove that $r_n = 7r_{n - 1} - 10r_{n - 2}, n \ge 2$.}

\subsection{Let $u$ be the sequence defined by $u_1 = 3, u_n = 3 + u_{n-1}, n \ge 2$. Find a formula for the sequence $d$ defined by $d_n = \prod_{i=1}^n u_i$.}

\subsection{$(x, y) \in R$ if 3 divides $x - y$. Is this relation reflexive, symmetric, antisymmetric, transitive, and/or a partial order?}

\subsection{Let $X$ be a nonempty set. Define a relation on $\mathcal{P}(X)$, the powerset of $X$, as $(A, B) \in R$ if $A \subset B$. Is this relation reflexive, symmetric, antisymmetric, transitive, and/or a partial order?}

\subsection{Let $X = \{1, 2, \ldots, 10\}$. Define a relation $R$ on $X \times X$ by $(a, b) R (c, d)$ if $a + d = b + c$. Show that $R$ is an equivalence relation on $X \times X$. List one member of each equivalence class of $X \times X$.}

\subsection{Write the standard method of adding two positive decimal integers, taught in elementary school, as an algorithm.}

\subsection{Write an algorithm to multiply two $n \times n$ matricies.}

\subsection{Write a recursive algorithm for finding a mode of a list of integers.}

\end{document}
%end of sample.tex
