\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{anyfontsize}
\usepackage[super]{nth}
\usepackage{ulem}
\usepackage{multicol}
\usepackage{phaistos}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage[all,arc]{xy}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}

\homework{2: Induction/Recursion}{Due Thursday, Week 1, at the start of class.}

Solve \textbf{one} of the following \textbf{three} problems.  As always, prove your claims!

\begin{enumerate}
\item[0.]  Do any of the problems that no-one solved on the previous set!

\item Let $S$ be a set of $n$ distinct real numbers.  Suppose that $A_S$ is the collection of all of the values given by averaging two distinct elements in $S$; that is,
\begin{align*}
A_S = \left\{ \frac{x+y}{2} ~\Bigg|~ x, y \in S, x \neq y\right\}.
\end{align*}
For example, if $S = \{ 1, 3, 5, 7\}$, we have $A_S = \{2, 3, 4,5,6\}$; alternately, if $S = \{1,2,3,5\}$, we have $A_S = \{1.5, 2, 2.5, 3, 3.5, 4\}$.

For any given $n \in \mathbb{N}$, what is the smallest possible size for the set $A_S$?


\item Take any $n \in \mathbb{N}$ that is greater than zero.  A \textbf{pleasant decomposition}\footnote{I made this term up!} of $n$ is any way in which we can write $n$ as the sum $a_1 + \ldots + a_k$ of positive integers, for arbitrary $k$, such that 
\begin{itemize}
\item $a_1 \leq a_2 \leq a_3 \leq \ldots a_k$, and 
\item $a_k \leq a_1+1$.  
\end{itemize}
For example, $n = 5$ has five different pleasant decompositions:
\begin{align*}
5 &= 5,\\
&= 2+3,\\
&= 1 + 2 + 2,\\
&= 1 + 1 + 1+ 2, \textrm{ and} \\
&= 1 + 1 + 1 + 1 + 1.\\
\end{align*}
For any given $n \in \mathbb{N}$, how many pleasant decompositions does $n$ have?

\item  Take any positive rational number $p/q$.  Show that we can write $p/q$ as the quotient of products of factorials of prime numbers (where these primes may be repeated.)  For example,
\begin{align*}
\frac{10}{9} = \frac{2! \cdot 5!}{3! \cdot 3!}
\end{align*}
\end{enumerate}





\end{document}