% This is a TeX file
% It is essentially a programming language for mathematics documents
% You can ignore this first portion of the file, as it is essentially a bunch of "include" statements.
\documentclass[10pt]{article}

\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{graphics}
\usepackage{fullpage}
\usepackage{fancyhdr}
\usepackage{hyperref}

\usepackage{algorithm,algorithmic}
\usepackage{multirow}

\setlength{\voffset}{-0.25in}
\setlength{\headsep}{0.25in}
\setlength{\parskip}{1em}
\setlength{\parindent}{0em}

% The following denotes a counter for the problems.
\newcounter{problem}
\newcommand{\problem}{\textbf{\refstepcounter{problem}Problem \theproblem.} }

% These are macro shortcuts! Helpful!
\def\vu{\mathbf{u}}
\def\vx{\mathbf{x}}
\def\vy{\mathbf{y}}
\def\vz{\mathbf{z}}
\def\vb{\mathbf{b}}
\def\vv{\mathbf{v}}
\def\vw{\mathbf{w}}

\renewcommand{\implies}{\rightarrow}
%\newcommand{\lnot}{\neg}
\renewcommand{\lor}{\vee}
\renewcommand{\land}{\wedge}
\newcommand{\xor}{\oplus}
\newcommand{\symmdiff}{\triangle}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\TRUE}{\mathbf{T}}
\newcommand{\FALSE}{\mathbf{F}}
\newcommand{\universe}{\mathcal{U}}


\def\N{\mathbb{N}}
\def\Q{\mathbb{Q}}
\def\C{\mathbb{C}}
\def\Z{\mathbb{Z}}
\def\R{\mathbb{R}}
\def\cP{\mathcal{P}}


\begin{document}
\pagestyle{fancyplain}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NOW you can start typing your text that will appear in the PDF!!!

% Note that anything after a '%' is a comment!

% Anything immediately after a '\' is a command. 
% Some denote formatting, some are for special characters.
% The '$' symbol starts and ends "math mode". Use this only for mathematical statements
% In math mode, any sequence of letters is meant to be a list of variables, so use "\sin x" for the sine of x, which will look much different from "sin x"
\chead{COM S 330 --- Homework 09 --- INSERT NAME HERE}

\textit{Type your answers to the following questions and submit a PDF file to Blackboard. 
One page per problem.}


% Problems about Structural Induction
% \clearpage
\problem\ [10pts] Let $S \subseteq \R$ be defined recursively using (Basis Step) $2015 \in S$, (Constructive Step) if $x, y\in S$, then $x - y \in S$ and $x^{|y|} \in S$.
Prove that $S = \Z$. [Hint: To show $\Z \subseteq S$, prove that $0$ and $-1$ are in $S$, and use these to construct any integer you want.]


% Problems about Structural Induction with Multiple Parameters
\problem\ [10pts] Let $S \subseteq \R$ be defined recursively using (Basis Step) $0 \in S$, (Constructive Step) If $x \in S$, then $x + 1 \in S$, $x + \pi\in S$, and $x + \sqrt{2} \in S$.
Prove that $S = \{ a + b\pi + c\sqrt{2} : a,b,c \in \N\}$.


% Problems about Counting, Product, Sum, Subtraction rules
\problem\ [10pts] Count the following things. Give your method and state which rules you are using.
\begin{enumerate}
\item\ [2pts] A \emph{palindrome} is a word that reads the same forwards and backwards. How many binary words of length $n$ are palindromes?


\item\ [2pts] Let $A = \{1,\dots,n\}$ for some integer $n \geq 1$, and let $B = \{1,2\}$. Count the number of \emph{surjective} functions $f : A \to B$.

\item\ [3pts] The class with $n$ students, $m$ TAs, and 1 instructor holds an election. They elect a president and a vice president, but the vice-president cannot ``out-rank'' the president (the instructor out-ranks the TAs and the TAs outrank the students). How many ways can the election complete?

\item\ [3pts] How many ways can we rearrange the symbols ``abcd123'' such that the letters appear in order, the numbers appear in order, but the letters and numbers can be mixed?
\end{enumerate}

% 
\problem\ [10pts] Demonstrate $\binom{n}{k}\binom{n-k}{\ell} = \binom{n}{k+\ell}\binom{k+\ell}{\ell}$ by using two methods to count the number of ways to create two disjoint committees of size $k$ and $\ell$ from a group of $n$ people












\end{document} 