% 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 --- Solutions}

\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.]

\begin{proof}
($S \subseteq \Z$) We use Structural Induction.

(Basis) $2015 \in \Z$.

(Constructive Step) Suppose that $x, y \in \Z$. Then $x - y \in Z$ and since $|y|$ is a nonnegative integer, $x^{|y|}$ is also an integer.

($\Z \subseteq S$) We use induction on $|i|$ to show that every element $i \in \Z$ is in $S$.

Case $|i| = 0$: $2015\in S$ and hence $0 = 2015 - 2015 \in S$.

Case $|i| = 1$: Since $0$ and $2015$ are in $S$, we have $1 = 2015^0 \in S$.
Also, since $0$ and $1$ are in $S$, $-1 = 0 - 1$ is in $S$.

(Induction Hypothesis) Let $n \geq 1$ and suppose that for every $i \in \Z$ with $|i| = n$ we have $i \in S$.

Case $|i| = n+1$: Since $n \in S$ and $-1 \in S$, we have $n + 1 = n - (-1) \in S$.
Since $0$ and $n+1$ are in $S$, we have $-(n+1) = 0 - (n+1) \in S$.
\end{proof}

% Problems about Structural Induction with Multiple Parameters
\clearpage
\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\}$.

\begin{proof}
Let $T = \{ a + b\pi + c\sqrt{2} : a,b,c \in \N\}$.

($S \subseteq T$) We use Structural Induction.

(Basis) $0 = 0 + 0\pi + 0\sqrt{2}$.

(Constructive Step) Suppose that $x = a + b\pi + c\sqrt{2}$ for some $a, b, c\in \N$.

The first construction is $x + 1 = (a+1) + b\pi + c\sqrt{2} \in T$.
The first construction is $x + \pi = a + (b+1)\pi + c\sqrt{2} \in T$.
The first construction is $x + \sqrt{2} = a + b\pi + (c+1)\sqrt{2} \in T$.


($T \subseteq S$) We use induction on $a+b+c$ to show that every element $a + b\pi + c\sqrt{2} \in T$ is in $S$.

Case $0$: $a + b + c = 0$ means $a = 0$, $b = 0$, and $c= 0$, so $0 + 0\pi + 0\sqrt{2} = 0 \in S$.

(Induction Hypothesis) Let $n \geq 0$ and suppose that for all $a,b,c \in \N$ with $a+b+c = n$ we have $a + b\pi + c\sqrt{2} \in S$.

Case $a + b + c = n+1$: Since $n + 1 > 0$, at least one of $a$, $b$, or $c$ is strictly positive.

If $a > 0$, then $x = (a-1) + b\pi + c\sqrt{2} \in S$ by the induction hypothesis and hence $a+b\pi + c\sqrt{2} = x + 1\in S$.

If $b > 0$, then $x = a + (b-1)\pi + c\sqrt{2} \in S$ by the induction hypothesis and hence $a+b\pi + c\sqrt{2} = x + \pi\in S$.

If $c > 0$, then $x = a + b\pi + (c-1)\sqrt{2} \in S$ by the induction hypothesis and hence $a+b\pi + c\sqrt{2} = x + \sqrt{2}\in S$.
\end{proof}


% Problems about Counting, Product, Sum, Subtraction rules
\clearpage
\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?

There are $2^{\lceil n/2\rceil}$ binary palindromes of length $n$.

\begin{proof}
If $n$ is even, then $n = 2k$ where $k = \lceil n/2\rceil$.
Select the letters $x_1\dots x_k$ in order, giving $2^k$ possible choices \textit{by the product rule}.
The rest of the string is the reversal, $x_kx_{k-1}\dots x_1$, completing the palindrome.

If $n$ is odd, then $n = 2k-1$ where $k = \lceil n/2\rceil$.
Select the letters $x_1\dots x_k$ in order, giving $2^k$ possible choices \textit{by the product rule}.
The rest of the string is the reversal, $x_{k-1}\dots x_1$, completing the palindrome (notice that the letter $x_k$ is not duplicated).
\end{proof}

\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$.

There are $2^n-2$ surjective functions.

\begin{proof}
There are $2^n$ functions from $A$ to $B$ \textit{by the product rule}.

There is one function $f_1$ where $f_1(a) = 1$ for all elements $a \in A$.

There is one function $f_2$ where $f_2(a) = 2$ for all elements $a \in A$.

These are the only two functions that are not surjective (since there must be at least one element of the codomain that is not in the range, leaving the rest of the elements being sent to the other element of $B$).
\textit{By the sum rule,} if $s$ is the number of surjective functions, then $1 + 1 + s = 2^n$ and hence $s = 2^n - 2$.
\end{proof}

\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?

There are $(m+n) + m(m+n-1) + n(n-1)$ ways to complete the election.

\begin{proof}
We separate the election possibilities into three types: President is Instructor, President is a TA, and President is a Student.

There is 1 way to elect the instructor as the president.
Then there are $m+n$ ways to elect a TA or a student as vice-president.
By the product rule, there are $m+n$ ways to hold an election with the instructor being president.

There are $m$ ways to elect a TA as the president.
Once a TA is elected president, the instructor cannot be elected vice-president.
There are $m+n-1$ remaining students and TAs that could be elected vice-president.
By the product rule, there are $m(m+n-1)$ ways to hold an election with a TA being president.

There are $n$ ways to elect a student as the president.
Once a student is elected president, the instructor and the TAs cannot be elected vice-president.
There are $n-1$ remaining students that could be elected vice-president.
By the product rule, there are $n(n-1)$ ways to hold an election with a student being president.

The three situations above describe disjoint possibilities.
Thus, by the sum rule there are $m+n+m(n+n-1)+n(n-1)$ ways to hold the election.
\end{proof}

\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?

There are $\frac{7!}{4!3!} = \frac{7\cdot 6 \cdot 5}{3\cdot 2\cdot 1} = 35$ ways to rearrange the symbols.

\begin{proof}
There are several ways to count this!

One process is to rearrange all of the seven letters in one of the $7!$ ways, then rearrange the letters to be in order and rearrange the numbers to be in order.
Each ordering will appear $4!\cdot 3!$ ways, so by the division rule there are $\frac{7!}{4!\cdot 3!}$ ways.

Another process is to select the four positions for the letters, then the positions of the letters is forced in those positions and the numbers are force to be in the remaining three positions.
There are $\binom{7}{4} = \frac{7!}{4!\cdot 3!}$ ways to select these four positions.


Yet another process is to select the three positions for the numbers, then the positions of the numbers is forced in those positions and the letters are force to be in the remaining four positions.
There are $\binom{7}{3} = \frac{7!}{3!\cdot 4!}$ ways to select these four positions.
\end{proof}

\end{enumerate}

% 
\clearpage
\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

\begin{proof}
One process: There are $\binom{n}{k}$ ways to select the first committee from $n$ people.
From the remaining $n-k$ people, there are $\binom{n-k}{\ell}$ ways to select the second committee.
By the product rule, there are $\binom{n}{k}\binom{n-k}{\ell}$ ways to select these two committees.

Another process: There are $\binom{n}{k+\ell}$ ways to select the people that will be on \emph{some} committee.
Then, from the $k+\ell$ people we can select the $\ell$ people to be on the second committee (the remaining $k$ people are on the first committee).
By the product rule, there are $\binom{n}{k+\ell}\binom{k+\ell}{\ell}$ ways to select these two committees.

Since we counted the same thing in two different ways, the two numbers must be equal.
\end{proof}










\end{document} 