\Question{Hit or Miss?}
State which of the proofs below is correct or incorrect.
For the incorrect ones, please explain clearly where the logical error in the proof lies.
Simply saying that the claim or the induction hypothesis is false is \emph{not} a valid explanation of what is wrong with the proof.
You do not need to elaborate if you think the proof is correct.
\begin{Parts}
\Part
\textbf{Claim:} For all positive numbers $n \in \mathbb{R}$, $n^2 \ge n$.
\begin{proof}
The proof will be by induction on $n$. \\
\emph{Base Case:} $1^2 \ge 1$. It is true for $n=1$. \\
\emph{Inductive Hypothesis:} Assume that $n^2 \ge n$. \\
\emph{Inductive Step:} We must prove that $(n+1)^2 \ge n+1$.
Starting from the left hand side,
\begin{align*}
(n+1)^2 &= n^2+2n+1 \\
&\ge n+1.
\end{align*}
Therefore, the statement is true.
\end{proof}
\Part
\textbf{Claim:} For all negative integers $n$, $-1-3-\cdots+(2n+1) = -n^2$.
\begin{proof}
The proof will be by induction on $n$. \\
\emph{Base Case:} $-1 = -(-1)^2$. It is true for $n=-1$. \\
\emph{Inductive Hypothesis:} Assume that $-1-3-\cdots+(2n+1) = -n^2$. \\
\emph{Inductive Step:} We need to prove that the statement is also true for $n-1$ if it is true for $n$, that is,
$-1-3-\cdots+(2(n-1)+1) = -(n-1)^2$. Starting from the left hand side,
\begin{align*}
-1-3-\cdots+(2(n-1)+1)
&= (-1-3-\cdots + (2n+1))+(2(n-1)+1) \\
&= -n^2 + (2(n-1)+1) \quad \text{(Inductive Hypothesis)}\\
&= -n^2 + 2n - 1 \\
&= -(n-1)^2.
\end{align*}
Therefore, the statement is true.
\end{proof}
% \Part
% \textbf{Claim:} For all positive integers $n$, $\sum\limits_{i=0}^n 2^{-i} \le 2$.
% \begin{proof}
% We will prove a stronger statement, that is, $\sum\limits_{i=0}^n 2^{-i} = 2-2^{-n}$, by induction on $n$. \\
% \emph{Base Case:} $n=1 \le 2-1$. It is true for $n=1$. \\
% \emph{Inductive Hypothesis:} Assume that $\sum\limits_{i=0}^n 2^{-i} = 2-2^{-n}$. \\
% \emph{Inductive Step:} We must show that $\sum\limits_{i=0}^{n+1} 2^{-i} = 2-2^{-(n+1)}$. Starting from the left hand side,
% \begin{align*}
% \sum\limits_{i=0}^{n+1} 2^{-i}
% &= \sum\limits_{i=0}^{n} 2^{-i} + 2^{-(n+1)} \\
% &= (2-2^{-n})+2^{-(n+1)} \quad\text{(Inductive Hypothesis)} \\
% &= 2-2^{-(n+1)}.
% \end{align*}
% Since $\sum\limits_{i=0}^n 2^{-i} = 2-2^{-n} \le 2$, the claim is true.
% \end{proof}
\Part
\textbf{Claim:} For all nonnegative integers $n$, $2n=0$.
\begin{proof}
We will prove by strong induction on $n$. \\
\emph{Base Case:} $2 \times 0 = 0$. It is true for $n=0$. \\
\emph{Inductive Hypothesis:} Assume that $2k=0$ for all $0 \le k \le n$. \\
\emph{Inductive Step:} We must show that $2(n+1)=0$. Write $n+1 = a+b$ where $0 < a,b \le n$.
From the inductive hypothesis, we know $2a = 0$ and $2b=0$, therefore,
\begin{align*}
2(n+1) = 2(a+b) = 2a + 2b = 0+0 =0.
\end{align*}
The statement is true.
\end{proof}
% \Part
% \textbf{Claim:} Every positive integer $n\ge2$ has a unique prime factorization. \\
% In other words, let $2 \le p_1, p_2, \hdots, p_i \le n$ be all prime numbers that divide $n$,
% there is only one unique way to write $n$ as a product of primes,
% \begin{align*}
% n = p_1^{d_1} \cdot p_2^{d_2} \dotsm p_i^{d_i},
% \end{align*}
% where $d_1, d_2, \hdots, d_i \in \mathbb{N}$.
% \begin{proof}
% We will prove by strong induction on $n$. \\
% \emph{Base Case:} 2 is a prime itself. It is true for $n=2$. \\
% \emph{Inductive Hypothesis:} Assume that the statement is true for all $2 \le k \le n$. \\
% \emph{Inductive Step:} We must prove that the statement is true for $n+1$.
% If $n+1$ is prime, then it itself is a unique prime factorization.
% Otherwise, $n+1$ can be written as $x \times y$ where $2 \le x,y \le n$.
% From the inductive hypothesis, both $x$ and $y$ have unique prime factorizations.
% The product of unique prime factorizations is unique, therefore, $n+1$ has a unique prime factorization.
% \end{proof}
\end{Parts}
\Question{A Coin Game}
Your "friend" Stanley Ford suggests you play the following game with him. You each start with a single stack of $n$ coins. On each of your turns, you select a stack of coins (that has at least two coins) and split it into two stacks, each with at least one coin. Your score for that turn is the product of the sizes of the two resulting stacks (for example, if you split a stack of 5 coins into a stack of 3 coins and a stack of 2 coins, your score would be $3 \cdot 2 = 6$). You continue taking turns until all your stacks have only one coin in them. Stan then plays the same game with his stack of $n$ coins, and whoever ends up with the largest total score over all their turns wins.
Prove that no matter how you choose to split the stacks, your total score will always be $\frac{n(n - 1)}{2}$. (This means that you and Stan will end up with the same score no matter what happens, so the game is rather pointless.)
\Question{Calculator Enigma}
Suppose you have a calculator on which the only working keys are $3, 6, 9, (, ), +, *, -,$
and the decimal point.
Prove that the only numbers you can make this calculator display are of the form $\frac{3k}{10^\ell}$ for $k \in \mathbb{Z}, \ell \in \mathbb{N}$; that is, show that the only numbers you can display are multiples of three with a decimal point inserted somewhere.
\textit{Hint: Use the well-ordering principle. What set might it be useful to define a well-ordering on?}
\Question{Build-Up Error?}
What is wrong with the following "proof"? In addition to finding a counterexample, you should explain what is fundamentally wrong with this approach, and why it demonstrates the danger build-up error.
{\bf False Claim:}~If every vertex in an undirected graph has degree at least 1, then the graph is connected.
{\em Proof:}~We use induction on the number of vertices $n \ge 1$.
{\em Base case:} There is only one graph with a single vertex and it has degree 0. Therefore, the base case is vacuously true, since the if-part is false.
{\em Inductive hypothesis:} Assume the claim is true for some $n \ge 1$.
{\em Inductive step:} We prove the claim is also true for $n+1$. Consider an undirected graph on $n$ vertices in which every vertex has degree at least 1. By the inductive hypothesis, this graph is connected. Now add one more vertex $x$ to obtain a graph on $(n + 1)$ vertices, as shown below.
\vspace{-8pt}
\begin{center}
\includegraphics[width=0.2\textwidth]{src/problems/graphtheory/resources/falseind.png}
\end{center}
\vspace{-8pt}
All that remains is to check that there is a path from $x$ to every other vertex $z$. Since $x$
has degree at least 1, there is an edge from $x$ to some other vertex; call it $y$. Thus, we
can obtain a path from $x$ to $z$ by adjoining the edge $\{x,y\}$ to the path from $y$ to $z$. This
proves the claim for $n+1$.
\nosolspace{1cm}
\Question{Proofs in Graphs}
Please prove or disprove the following claims.
\begin{Parts}
\Part In Old California, all roads were one way streets. Suppose Old California had
$n$ cities ($n \geq 2$) such that for every pair of cities $X$ and $Y$,
either $X$ had a road to $Y$ or $Y$ had a road to $X$. Prove or disprove that
there existed a city which was reachable from every other city by traveling through at
most 2 roads.
[\textit{Hint:} Induction]
\Part
In lecture, we have shown that a connected undirected graph has an Eulerian tour if and only if every vertex has even degree.
Consider a connected graph $G$ with $n$ vertices which has exactly $2m$ vertices of
odd degree, where $m > 0$. Prove or disprove that there are $m$ walks that \emph{together}
cover all the edges of $G$ (i.e., each edge of $G$ occurs in exactly one of the $m$ walks,
and each of the walks should not contain any particular edge more than once).
\end{Parts}
\Question{Always, Sometimes, or Never}
In each part below, you are given some information about a graph $G$. Using only the information in the current part, say whether $G$ will always be planar, always be non-planar, or could be either. If you think it is always planar or always non-planar, prove it. If you think it could be either, give a planar example and a non-planar example.
\begin{Parts}
\Part $G$ can be vertex-colored with $4$ colors.
\Part $G$ requires 7 colors to be vertex-colored.
\Part $e \leq 3v - 6$, where $e$ is the number of edges of $G$ and $v$ is the number of vertices of $G$.
\Part $G$ is connected, and each vertex in $G$ has degree at most 2.
\Part Each vertex in $G$ has degree at most 2.
\end{Parts}
\Question{Bipartite Graphs}
An undirected graph is bipartite if its vertices can be partitioned into two disjoint sets $L$, $R$ such that each edge connects a vertex in $L$ to a vertex in $R$ (so there does not exist an edge that connects two vertices in $L$ or two vertices in $R$).
\begin{Parts}
\Part
Suppose that a graph $G$ is bipartite, with $L$ and $R$ being a bipartite partition of the vertices. Prove that $\sum\limits_{v \in L} \deg(v) = \sum\limits_{v \in R} \deg(v)$.
\Part
Suppose that a graph $G$ is bipartite, with $L$ and $R$ being a bipartite partition of the vertices. Let $s$ and $t$ denote the average degree of vertices in $L$ and $R$ respectively. Prove that $s/t = |R|/|L|$.
\Part
A double of a graph $G$ consists of two copies of $G$ with edges joining
the corresponding ``mirror'' points. Now suppose that $G_1$ is a bipartite
graph, $G_2$ is a double of $G_1$, $G_3$ is a double of $G_2$, and so on. (Each $G_{i+1}$ has twice as many vertices as $G_i$).
Show that $\forall n \geq 1$, $G_n$ is bipartite.
% \Part
% Prove that a graph is bipartite if and only if it can be $2$-colored. (A graph can be $2$-colored if every vertex can be assigned one of two colors such that no two adjacent vertices have the same color).
\end{Parts}
\Question {Modular Arithmetic Solutions}
Find all solutions (modulo the corresponding modulus) to the following equations. Prove that there are no other solutions (in a modular setting) to each equation.
\begin{Parts}
\Part $2x \equiv 5 \pmod{15}$
\Part $2x \equiv 5 \pmod{16}$
\Part $5x \equiv 10 \pmod{25}$
\end{Parts}