\documentclass[12pt,letterpaper]{article}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amscd}
\usepackage{enumerate}
\usepackage{fancyhdr}
\usepackage{mathrsfs}
\usepackage{bbm}
\usepackage{framed}
\usepackage{mdframed}
\usepackage{cancel}
\usepackage{mathtools}
\usepackage{verbatim}
\usepackage{graphicx}
\usepackage[letterpaper,voffset=-.5in,bmargin=3cm,footskip=1cm]{geometry}
\setlength{\parindent}{0.0in}
\setlength{\parskip}{0.1in}
\allowdisplaybreaks
\headheight 15pt
\headsep 10pt
\newcommand\N{\mathbb N}
\newcommand\Z{\mathbb Z}
\newcommand\R{\mathbb R}
\newcommand\Q{\mathbb Q}
\newcommand\lcm{\operatorname{lcm}}
\newcommand\setbuilder[2]{\ensuremath{\left\{#1\;\middle|\;#2\right\}}}
\newcommand\E{\operatorname{E}}
\newcommand\V{\operatorname{V}}
\newcommand\Pow{\ensuremath{\operatorname{\mathcal{P}}}}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand\hint[1]{\textbf{Hint}: #1}
\newcommand\note[1]{\textbf{Note}: #1}
\newcounter{enum22i}
\newenvironment{22enumerate}{\begin{enumerate}[a.]\itemsep0em\setcounter{enumi}{\value{enum22i}}}{\setcounter{enum22i}{\value{enumi}}\end{enumerate}}
\newenvironment{22itemize}{\begin{itemize}\itemsep0em}{\end{itemize}}
\fancypagestyle{firstpagestyle} {
\renewcommand{\headrulewidth}{0pt}
\lhead{\textbf{CSCI 0220}}
\chead{\textbf{Discrete Structures and Probability}}
\rhead{M. Littman}
}
\fancypagestyle{fancyplain} {
\renewcommand{\headrulewidth}{0pt}
\lhead{\textbf{CSCI 0220}}
\chead{Final Exam}
\rhead{\textit{Monday, May 11}}
}
\pagestyle{fancyplain}
\begin{document}
\thispagestyle{firstpagestyle}
\begin{center}
{\huge \textbf{Final Exam}}
{\large \textit{Due: 11:59 pm EDT on Monday, May 11}}
\end{center}
Please do not include any identifying information about yourself in the handin, including your Banner ID.
Be sure to leave \textbf{at least 30 minutes} to upload your answers on Gradescope.
Regardless of whether a particular question explicitly tells you to show your work, you should always explain things so that other students in CS22 will be able to follow your reasoning. We are not testing your ability to answer, but your ability to explain.
\subsection*{Problem 0}
{\setcounter{enum22i}{0}
Please answer the following questions before you begin. We cannot grade your exam without your answers.
\begin{22enumerate}
\item Do you promise to not consult anyone (besides the course staff) about this exam?
\item Do you promise to not search for solutions on the Internet?
\item If you have a question about this exam, do you promise to only ask for clarifications via \textbf{private} Piazza posts?
\item Have you double checked when the deadline for this midterm is in your time zone?
\end{22enumerate}}
\newpage
\subsection*{Problem 1}
{
\nopagebreak
{\setcounter{enum22i}{0}
Prove that if a relation $R$ on a set $S$ is reflexive
and transitive, then the relation $R \cap R^{-1}$ is an equivalence
relation, where $R^{-1}$ is called the \emph{inverse} of
$R$ and is defined by $x R^{-1} y \Leftrightarrow y R x$.
}
}
\newpage
\subsection*{Problem 2}
{
\nopagebreak \newcommand\personB{Kristy}
\newcommand\personA{Kareem}
{\setcounter{enum22i}{0}
\personA\ and \personB\ are competing on a game show.
The final challenge is to each flip a coin in secret and then guess
the result of their partner's coin flip.
They can't communicate with each other at all during the challenge,
and will only know the result of their own coin flip.
If at least one of their guesses is correct, they will
win the game show; if not, they will be sent home empty handed.
You should justify all your answers.
\begin{22enumerate}
\item Assuming that they each guess uniformly at random,
what is the probability that they win?
\item \personA\ and \personB\ do some trial runs of the game in
preparation for the real deal. If they practice playing $n$
times, still guessing uniformly at random, what is the
expected number of times they win twice in a row? You can assume each practice round is independent. \\
(Winning three times in a row counts as winning twice in
a row twice).
\item \personA\ and \personB\ will get bored while practicing if they
see the same scenario over $k$ times (two practice rounds are the same
scenario if all flips and guesses are identical). They stop
practicing as soon as they get bored. What is the maximum number
of rounds they practice?
\item Let true represent heads and false represent tails. \\
Let $f_1$ and $f_2$ represent the results of \personA 's and
\personB 's coin flips, respectively, and let $r_1$ and $r_2$
represent \personA 's and \personB 's guesses, respectively. \\
(For instance, if \personA\ flips heads and guesses tails while
\personB\ flips tails and guesses heads, we would have $f_1=T$,
$f_2=F$, $r_1=F$, and $r_2=T$). \\
Write a logical expression that is true when \personA\
and \personB\ win the game and false otherwise.
\item Prove that the following is a valid proposition: \\
$$(p \iff \lnot q) \lor (q \iff p).$$
Here, the $\iff$ symbol means ``if and only if.'' You can use either truth tables or logical rewrite rules, but either way be sure to show your work (for truth tables, the intermediate columns; for logical rewrite rules, each step and the rule applied).
\item \personA\ and \personB\ don't want to leave their fate
to chance! Before going on the show, they decide on a plan to ensure
that they will always win. How should they each guess? Remember
that they each flip their coin \textit{before} making a guess.
\end{22enumerate}
}
}
\newpage
\subsection*{Problem 3}
{
\nopagebreak
{\setcounter{enum22i}{0}
In this problem, we will find out how many graphs there are with $n$ vertices such that each vertex has even degree. In each part, we consider two graphs to be unique if they have different edge sets, even if they are isomorphic.
\begin{22enumerate}
\item Prove that there are $\displaystyle 2^{n \choose 2}$ graphs with $n$ vertices.
\item Prove that in any graph, the number of vertices of odd degree is even.
\item Find a bijection between the set of graphs with $n-1$ vertices and the set of graphs with $n$ vertices such that each vertex has even degree. Prove that your mapping is bijective. \\
\textit{Hint:} Add a vertex and some edges to a graph with $n-1$ vertices and use part b.
\item How many graphs are there with $n$ vertices such that each vertex has even degree? Justify your answer.
\end{22enumerate}
}
}
\newpage
\subsection*{Problem 4}
{
\nopagebreak
{\setcounter{enum22i}{0}
In this problem, you will sketch another proof of Fermat's Little Theorem
using the Binomial Theorem and modular arithmetic.
As a reminder, Fermat's Little Theorem states that for any integer $a$ and any prime number $p$,
\[a^{p} \equiv a \pmod{p}\]
and the Binomial Theorem states that, for any integers $a$, $b$, and $n$:
\[(a + b)^{n} = \sum_{i=0}^{n}{n\choose i}a^{n-i}b^{i}\]
\begin{22enumerate}
\item
Prove that, for any prime number $p$ and any integer $0 < i < p$, \\$p$ divides $\displaystyle{p \choose i}$.
\item
Prove that, for integers $a$ and $b$ and a prime number $p$, $\displaystyle{(a + b)^{p} \equiv a^{p} + b^{p} \pmod{p}}$.
\item
Using induction, apply the previous part to prove Fermat's Little Theorem (in the above form) for all $a > 0$. \\ \textit{Hint:} Use the fact that the congruence in part b holds when $b$ is equal to 1.
\end{22enumerate}
}
}
\newpage
\subsection*{Problem 5}
{
\nopagebreak
{\setcounter{enum22i}{0}
$\mathbb{E}$ is the edge set of a complete graph with vertices $V$.
Consider a graph $G$, where $V(G)=V$ and $E(G) \subseteq \mathbb{E}$. The
complement of $G$, $G^c$, is the graph where $V(G^c)=V$ and $E(G^c) = \mathbb{E} - E(G)$.
Prove that, if a graph $G$ is not connected, then $G^c$ is
connected. (Note that we only defined undirected graphs in this class.)
}
}
\end{document}