%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%% PREAMBLE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[12pt,letterpaper]{article}

\usepackage{amsmath}               % Enviornments, etc. for typsetting math.
\usepackage{amsthm}                % Theorem/proof enviornments.
\usepackage{amssymb}               % Various symbols.
\usepackage{geometry}              % Easy interface to set page margins.
\usepackage{fancyhdr}              % Custom headers/footers, page styles.
\usepackage[shortlabels]{enumitem} % Stuff for enumerate, itemize environments.
\usepackage{tikz}

%%%%%%%%%% VARIOUS HOUSEKEEPING %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\geometry{margin=3cm}              % Sets margins on all sides.
\pagestyle{fancyplain}             % Sets page style.
\headheight 35pt                   % Sets the height of the header.
\headsep 10pt                      % Sets space between the header and the body.

\setlength{\parindent}{0em}        % Sets paragraph indentation.
\setlength{\parskip}{0.5em}        % Sets space between paragraphs.

\setlist[itemize]{leftmargin=*}    % Normalize left margin in itemize.
\setlist[enumerate]{leftmargin=*}  % Normalize left margin in enumerate.

% The answer environment definition.
\newenvironment{answer}[1]{
  \subsubsection*{Problem \hwnum.#1}
}

%%%%%%%%%% ASSIGNMENT INFORMATION %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Edit these as appropriate.
\newcommand\course{CS 22}
\newcommand\semester{Spring 2017}  % <-- current semester
\newcommand\banner{B01300206}      % <-- your banner id
\newcommand\hwnum{3}               % <-- homework number

%%%%%%%%%% HEADER %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\lhead{\banner\\\course\ --- \semester}
\chead{\textbf{\Large Homework \hwnum}}
\rhead{\today}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%% DOCUMENT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
\begin{answer}{1}
Let $S$ be the quaternary string representation of $T$. \\
That is, for each $(X,Y)$ in $T$ represented by $t$, it is related to an $s$ in $S$ such that: \\
$s$ is a base-4 string of length $n$, and the $k$th digit represents whether the $k$th element of $A$ is in $X$ and whether the $k$th element of $A$ is in $Y$. For example: \\
The $k$th digit in $s$ is a 0 iff $X$ does not contain the $k$th element of $A$ and $Y$ does not contain the $k$th element of $A$. \\
The $k$th digit in $s$ is a 1 iff $X$ contains the $k$th element of $A$ and $Y$ does not contain the $k$th element of $A$. \\
The $k$th digit in $s$ is a 2 iff $X$ does not contain the $k$th element of $A$ and $Y$ contains the $k$th element of $A$. \\
The $k$th digit in $s$ is a 3 iff $X$ contains the $k$th element of $A$ and $Y$ contains the $k$th element of $A$. \\
As each digit of $s$ is determined by whether an element is in $X$ and whether it is in $Y$ through if and only if, any $s$ related to a $t$ is related to only that $t$. i.e. the relation between $S$ and $T$ is injective.\\
As each digit of $s$ can only be $0,1,2,3$, each digit represents some combination of whether an element of $A$ is in $X$ and $Y$, so each $s$ of length $n$ represents some combination of whether the $n$ elements of $A$ are in $X$ and $Y$. i.e. the relation between $S$ and $T$ is surjective. \\
As the relation between $S$ and $T$ is injective and surjective, it is a bijective relation. \\
The bijective relation implies that the cardinality of $S$ and $T$ are equal, so the two sets are of equal sizes. \\
\end{answer}

\begin{answer}{2}
\begin{enumerate}[a.]
\item
\begin{proof} \hspace{1 mm}
\begin{description}
\item[Base case]: $n = 1$.\\
\begin{align*}
\sum_{i=1}^{1} i^2 &= 1^2 = 1 \\
\frac{1^3}{3} + \frac{1^2}{2} + \frac{1}{6} &=
\frac{1}{3} + \frac{1}{2} + \frac{1}{6} = 1 \\
\sum_{i=1}^{1} i^2 &=
\frac{1^3}{3} + \frac{1^2}{2} + \frac{1}{6} \\
\end{align*}
\item[Inductive step]: Let $k \in \mathbb{Z_+}$.
\begin{align*}
Assume \sum_{i=1}^{k} i^2 &= \frac{k^3}{3} + \frac{k^2}{2} + \frac{k}{6}. \\
1^2 + 2^2 + \ldots + k^2 &= \frac{k^3}{3} + \frac{k^2}{2} + \frac{k}{6}. \\
1^2 + 2^2 + \ldots + k^2 + (k+1)^2 &= \frac{k^3}{3} + \frac{k^2}{2} + \frac{k}{6} + (k+1)^2 \\
1^2 + 2^2 + \ldots + k^2 + (k+1)^2 &= \frac{k^3}{3} + \frac{k^2}{2} + \frac{k}{6} + k^2 + 2k + 1 \\
1^2 + 2^2 + \ldots + k^2 + (k+1)^2 &= \frac{k^3}{3} + k^2 + k + \frac{1}{3} + \frac{k^2}{2} + k + \frac{1}{2} + \frac{k}{6} + \frac{1}{6} \\
1^2 + 2^2 + \ldots + k^2 + (k+1)^2 &= \frac{k^3 + 3k^2 + 3k + 1}{3} + \frac{k^2+2k+1}{2} + \frac{k+1}{6} \\
1^2 + 2^2 + \ldots + k^2 + (k+1)^2 &= \frac{(k+1)^3}{3} + \frac{(k+1)^2}{2} + \frac{k+1}{6} \\
\sum_{i=1}^{k+1} i^2 &= \frac{(k+1)^3}{3} + \frac{(k+1)^2}{2} + \frac{k+1}{6} \\
\end{align*}
\end{description}
By the process of inductive proof, the statement is valid for all $k \in \mathbb{Z_+}$
\end{proof}
\item
The 'victory case' of this game is if only one pile contains one or more spoons. \\
Whoever takes their turn then wins the game by removing all the spoons left. \\
The base case of this game is if the two piles each contain one spoon. \\
Whoever takes their turn then loses the game as they are forced to remove the last spoon from one of the piles, leaving their opponent with the victory case. \\
If either pile has more than one spoon while the other has precisely one, whoever takes their turn then can win by removing all but one spoon from the bigger pile. \\
The game starts with two equal piles of spoons. If the game is not in the base case, and the first player removes some number of spoons from a pile without leaving it empty, the second player removes the same amount of spoons from the other pile so the piles are equal again. \\
If at any point the first player takes all the spoons from one pile, the second player can win. \\
Eventually, as each turn both players take a positive amount of spoons from either pile, the first player will be forced to leave one spoon in either pile, allowing the second player to bring the game to the base case and win. \\
\end{enumerate}
\end{answer}

\begin{answer}{3}
\begin{proof}
\begin{description}
\item[Base case]: $n = 1$.\\
$1 = 1 \times 3^0$
\item[Inductive step]: Let $n \in \mathbb{Z_+}$. \\
Assume $n$ can be written as: \\
$a_k 3^k + a_{k-1}3^{k-1} + \ldots +a_1 3^1 + a_0$ where each
$a_i \in \left\{ -1, 0, 1 \right\}.$ \\
If $a_0 = -1$, then $n+1$ can be written as: \\
$a_k 3^k + a_{k-1}3^{k-1} + \ldots +a_1 3^1 + 0$ \\
If $a_0$ = 0, then $n+1$ can be written as: \\
$a_k 3^k + a_{k-1}3^{k-1} + \ldots +a_1 3^1 + 1$ \\
If $a_0$ = 1, then $n+1$ can be written as: \\
$a_k 3^k + a_{k-1}3^{k-1} + \ldots + (a_1 + 1) 3^1 + (-1)$ if $a_1 \not = 1$ \\
If $a_1$ = 1, the 1 is carried up through all of the $a_i$ until either: \\
$a_i \not = 1$, and $n + 1$ can be expressed as \\
$a_k 3^k + a_{k-1}3^{k-1} + \ldots + a_{i+1} 3 ^ {i+1} + (a_i + 1) 3^i + (-1) 3^{i-1} + \ldots + (-1) 3^1 + (-1)$ \\
or $i = k$, in which case $n + 1$ can be expressed as \\
$1 \times a_{k+1} + (-1) 3^k + (-1) 3^{k-1} + \ldots + (-1) 3^1 + (-1)$ \\
In adding 1 to $n$, the ternary representation of $n$ adds 1 to its final term with coefficient $a_i \not = 1$ and subtracts 2 from the coefficients of all following terms, changing them from $1$ to $-1$. \\
As $2(3^0 + 3^1 + \ldots + 3^{i-1}) + 1 = 3^{i}$, the process adds 1 to the representation.
\end{description}
By the process of inductive proof, the statement is valid for all $n \in \mathbb{Z_+}$
\end{proof}
\end{answer}
\begin{answer}{4}
\begin{enumerate}[a.]
\item The resultant function $R_{TSR}$ would be:
\begin{description}
\item[Reflexivity]: \\
Reflexive, because any superset of a reflexive relation is still reflexive. Expanding a reflexive relation without expanding its domain does not affect its reflexivity, since every element in the domain is already related to itself.
\item[Symmetry]: \\
Symmetric, because the transitive closure of a symmetric relation is still symmetric. Any new elements added to make the relation transitive must have its symmetric element added as well. To create a transitive closure, elements $t$ are added to the relation, s.t. if $(a,b) \in R_{SR}$ and $(b,c) \in R_{SR}$, then $t = (b,c)$ is added to the relation if not already in it. But if $(a,b)$ and $(b,c)$ are both in $R_{SR}$, then $(b,a)$ and $(c,b)$ are both in the relation, and $(c,a)$ must be added as well to create the transitive closure.
\item[Transitivity]: \\
Transitive because it is a transitive closure of $R_{SR}$.
\item[Equivalence]: \\
An equivalence relation because it is reflexive, symmetric, and transitive.
\end{description}
\item The resultant function $R_{RST}$ would be:
\begin{description}
\item[Reflexivity]: \\
Reflexive, because it is a reflexive closure of $R_{ST}$.
\item[Symmetry]: \\
Symmetric, because any elements added to a symmetric relation to form a reflexive closure are in the form $(e,e)$ thus symmetric. $R_{ST}$ was a symmetric relation because it is a symmetric closure of $R_T$.
\item[Transitivity]: \\
Either transitive or not. An example of both is provided below. \\ \\
Consider the relation $R$ on $A = \{1,2,3\}$ be defined as the set $\{(1,2), (1,3)\}$. \\
Its transitive closure $R_T$ is still $\{(1,2), (1,3)\}$. \\
The symmetric closure of $R_T$, $R_{ST}$ is $\{(1,2), (1,3), (2,1), (3,1)\}$. \\
The reflexive closure of $R_{ST}$, $R_{RST}$ is $\{(1,2), (1,3), (2,1), (3,1), (1,1), (2,2), (3,3)\}$. \\
$R_{RST}$ is reflexive and symmetric, but it is not transitive. \\
$(2,1)$ and $(1,3)$ are in the relation, but $(2,3)$ is not. \\
\\
Consider the relation $Q$ on $A = \{1,2,3\}$ be defined as the set $\{(1,1)\}$. \\
Its transitive closure $Q_T$ is still $\{(1,1)\}$. \\
The symmetric closure of $Q_T$, $Q_{ST}$ is still $\{(1,1)\}$. \\
The reflexive closure of $Q_{ST}$, $Q_{RST}$ is $\{(1,1), (2,2), (3,3)\}$. \\
$R_{RST}$ is reflexive, symmetric, and transitive.
\item[Equivalence] : \\
Possibly an equivalence relation, but not necessarily as its transitivity is not certain.
\end{description}
\end{enumerate}
\end{answer}
\begin{answer}{5}
\begin{enumerate}[a.]
\item
\begin{proof}
Assume for any integer $n$, $n^{2} -2$ is divisible by $4$. \\
i.e. $n^2 - 2$ can be written in the form $4k$, where $k \in \mathbb{Z}$. \\
$n^2 = 4k + 2$ \\
$n^2$ is divisible by 2, as $4k + 2$ is divisible by 2. \\
Therefore, as shown in class, $n$ cannot be odd as $n^2$ is not odd. \\
If $n$ is even, it can be written in the form $2j$, where $j \in \mathbb{Z}$. \\
$n^2 = 4j^2$. \\
$4j^2 = 4k + 2$, which cannot be true when $j,k \in \mathbb{Z}$. \\
Therefore $n$ is neither even nor odd, therefore $n^2 - 2$ is not divisible by 4. \\
\end{proof}
\item
\begin{proof}
If $n$ is odd, then $n \times n$ is odd. \\
If $n \times n$ is odd, then $(n \times n) \times n = n^3$ is odd. \\
If $n^3$ is odd, then $n^3 \div n = n^2$ is odd. \\
If $n^2$ is odd, then $n^2 \div n = n$ is odd. \\
\end{proof}
\item
\begin{proof} For any integer $n$, $n^3 - n$ can be written in the form: \\
$n \times (n+1) \times (n-1)$ \\
One of $n, n+1, n-1$ must be divisible by 3 because: \\
If $n$ is not divisible by 3, its remainder when dividing by 3 must be either 1 or 2. \\
If the remainder when $n \div 3$ is equal to 1, then $n-1$ is divisible by 3. \\
If the remainder when $n \div 3$ is equal to 2, then $n+1$ is divisible by 3. \\
The product of any number divisible by 3 is divisible by 3. \\
$n \times (n + 1) \times (n - 1)$ is divisible by 3. \\
$n^3 - n$ is divisible by 3. \\
\end{proof}
\end{enumerate}
\end{answer}
\end{document}