\documentclass[11pt]{article}
\usepackage{fullpage} % 1 inch margins on standard letter size paper
\usepackage{amsmath}  % AMS math macros
\usepackage{amssymb}  % Additional math symbols from AMS

\title{Assignment 1}
\author{Your name here}

\begin{document}
\maketitle

\begin{enumerate}
\item
  One of the constructions in this class will take a set of states $Q$
  for one machine and create a new machine which uses a set of states
  $R$ which is the set of all subsets of $Q$ (you don't need to know
  what a ``machine'' or ``state'' really is in this -- it's all about
  the sets).

  \begin{enumerate}
  \item
    What is the mathematical terminology? In other words, $R$ is the
    \rule{1in}{0.4pt} of $Q$.
  \item
    If $Q=\{a,b,c\}$, what is $R$?
  \item
    Prove that for any set $Q$, the size of $R$ satisfies
    $|R|=2^{|Q|}$.
  \end{enumerate}
\item
  Describe each of the following sets in high-level plain English (no
  formulas!). For example, the set $\{x\,|\,x=2k+1 \text{ for } k\geq 1\}$
  is ``The set of odd integers greater than or equal to 3.'' Do
  \textbf{not} simply restate things as written here (in other words, do
  not say ``The set of integers $x$ for which $x=2k+1$ and
  $k\geq 1$'').

  The sets below are all sets of binary strings (note that $\{0,1\}^*$
  denotes the set of all binary strings), and in addition to the
  notation in the book (pages 13--14) we define $c_0(x)$ to be the
  number of $0$'s in string $x$, and $c_1(x)$ to be the number of
  $1$'s in $x$. For example, if $x=\texttt{011010001}$ then
  $c_0(x)=5$ and $c_1(x)=4$.

  \begin{enumerate}
  \item
    $\{x\,|\,x\in\{0,1\}^* \text{ and } |x|=2k \text{ for some integer } k\}$
  \item
    $\{x\,|\,x\in\{0,1\}^* \text{ and } c_0(x)=c_1(x)\}$
  \item
    $\{x\,|\,x\in\{0,1\}^* \text{ and } c_1(x)=2k+1 \text{ for some
      integer } k\}$
  \item
    $\{x\,|\,x\in\{0,1\}^* \text{ and } x=x^{\mathcal{R}}\}$
  \end{enumerate}
\item
  We define a function $f$ to update the position of a robot on a
  3-position number-line, with valid positions $-1$, $0$, and
  $+1$, and an ``out of bounds'' position ``out''. The set of
  positions is denoted $P=\{\text{out}, -1, 0, +1\}$. The valid set of
  moves is $M=\{\text{Left}, \text{Right}\}$. Once out of bounds, the
  robot cannot come back to a valid position. The position update
  function $f: P\times M\rightarrow P$ is given in the following
  table:

  \begin{tabular}{|l|c|c|}\hline
    & Left & Right \\\hline\hline
    out & out & out \\\hline
    $-1$ & out & $0$ \\\hline
    $0$ & $-1$ & $+1$ \\\hline
    $+1$ & $0$ & out \\\hline
  \end{tabular}
  
  For example, $f(0,\text{Right})=+1$ and
  $f(-1,\text{Left})=\text{out}$.

  \begin{enumerate}
  \item
    Explain in your own words what the notation
    ``$f:P\times M\rightarrow P$'' means.
  \item
    What is
    $f(f(f(f(f(0,\text{Left}),\text{Right}),\text{Right}),\text{Left}),\text{Right})$?
    \textbf{Show your work!}
  \item
    What is
    $f(f(f(f(f(0,\text{Left}),\text{Right}),\text{Right}),\text{Right}),\text{Left})$?
    \textbf{Show your work!}
  \end{enumerate}
\item
  Prove by contradiction: Any undirected graph with $n\geq 2$ vertices
  must have two vertices with the same degree.
\item
  Use induction to prove that for all $n\geq 1$,
  \[ \sum_{x=0}^{n-1} x(x-1) = \frac{n(n-1)(n-2)}{3}.\]
\item
  Let $G$ be a directed graph with $n$ vertices, and let $v$ and
  $w$ be any two nodes in the graph. Prove that if there is a path
  from node $v$ to node $w$ of length $n$, then there is another
  path from $u$ to $v$ with length greater than $2n$. (\emph{Hint:
  Think about what is appropriate in the following blank, and how that
  is important to this property: ``Any path with $n$ edges in an
  $n$-vertex graph must contain a
  \rule{1in}{0.4pt}.'' Note that this is just to get
  you thinking. Any property you fill in that blank with needs to be
  proved as part of the overall proof -- you can't just state it, even
  if you think it's obvious.})
\end{enumerate}

\end{document}
