\Question{Short Answer: Logic}
For each question, please answer in the correct format. When
an expression is asked for, it may simply be a number, or an expression
involving variables in the problem statement, you have to figure
out which is appropriate.
\begin{enumerate}
\item
Let the statement, $(\forall x \in R, \exists y \in R) \ G(x,y)$, be
true for predicate $G(x,y)$ and $R$ being the real numbers.
Which of the following statements is certainly true, certainly false, or possibly true.
\begin{enumerate}
\item
$G(3,4)$
\item
$(\forall x \in R) G(x,3)$
\item
$(\exists y) G(3,y)$
\item
$(\forall y) \neg G(3,y)$
\item
$(\exists x) G(x,4)$
\end{enumerate}
\item True or False? \\
$(\forall x) (\exists y) (P(x,y) \land \neg Q(x,y)) \equiv \neg (\exists x) (\forall y) (P(x,y) \implies Q(x,y))$
\item True or False? \\
$(\exists x) ((\forall y P(x,y)) \land (\forall z Q(x,z))) \equiv (\exists x) ((\forall y) (P(x,y)) \land (\exists x)(\forall z) Q(x,z)$
\item
Give an expression using terms involving $\lor,\land$ and $\neg$ which is true if and only if
exactly one of $X,Y$, and $Z$ are true. (Just to remind you: $(X \land Y \land Z)$ means
all three of $X$,$Y$,$Z$ are true, $(X \lor Y \lor Z)$ means at least one of $X$,$Y$
and $Z$ is true.)
\end{enumerate}
\Question{Equivalent or Not}
Determine whether the following equivalences hold, and give brief justifications for your answers. Clearly state whether or not each pair is equivalent.
\begin{Parts}
\Part $\forall x~\exists y~\big(P(x)\Rightarrow Q(x,y)\big)~\equiv~\forall x~\big(P(x)\Rightarrow(\exists y~Q(x,y))\big)$
\Part $\neg\exists x~\forall y~\big(P(x,y)\Rightarrow\neg Q(x,y)\big)~\equiv~\forall x~\big( (\exists y~P(x,y)) \land (\exists y~Q(x,y)) \big)$
\Part $\forall x~\big((\exists y~Q(x,y))\Rightarrow P(x)\big)~\equiv~\forall x~\exists y~\big(Q(x,y)\Rightarrow P(x)\big)$
\end{Parts}
\Question{Counterfeit Coins}
\begin{Parts}
\Part
Suppose you have $9$ gold coins that look identical, but you also know
one (and only one)
of them is counterfeit. The counterfeit coin weighs slightly less
than the others. You also have access to a balance scale to compare
the weight of two sets of coins --- i.e., it can tell you whether
one set of coins is heavier, lighter, or equal in weight to another
(and no other information). However, your access to this scale is
very limited.
Can you find the counterfeit coin using {\em just two weighings}?
Prove your answer.
\Part
Now consider a generalization of the same scenario described above.
You now have $3^n$ coins, $n \geq 1$, only one of which is counterfeit.
You wish to find the counterfeit coin with just $n$ weighings.
Can you do it? Prove your answer.
\end{Parts}
\Question{Proof Checker}
In this question, you will play ``CS70 Grader'':
you are tasked with checking someone else's attempt at a proof.
For each of the ``proofs'' below, say whether you think it is correct or incorrect.
If you think the proof is incorrect, explain clearly and concisely where the logical error in the proof lies.
(If you think the proof is correct, you do not need to give any explanation.)
Simply saying that the claim (or the inductive hypothesis) is false is not a valid explanation.
\begin{Parts}
\Part \textbf{Claim}: for all $n\in\N$, $(2n+1$ is a multiple of $3) \implies (n^2+1$ is a multiple of $3)$.
\textbf{Proof}: proof by contraposition. Assume $2n+1$ is not a multiple of 3.
\begin{itemize}
\item If $n=3k+1$ for $k\in\N$, then $n^2+1=9k^2+6k+2$ is not a multiple of 3.
\item If $n=3k+2$ for $k\in\N$, then $n^2+1=9k^2+12k+5$ is not a multiple of 3.
\item If $n=3k+3$ for $k\in\N$, then $n^2+1=9k^2+18k+10$ is not a multiple of 3.
\end{itemize}
In all cases, we have concluded $n^2+1$ is not a multiple of 3, so we have proved the claim.
\Part \textbf{Claim}: for all $n\in\N$, $n<2^n$.
\textbf{Proof}: the proof will be by induction on $n$.
\begin{itemize}
\item Base case: suppose that $n=0$. $2^0=1$ which is greater than $0$, so the statement is true for $n=0$.
\item Inductive hypothesis: assume $n<2^n$.
\item Inductive step: we need to show that $n+1<2^{n+1}$. By the inductive hypothesis, we know that $n<2^n$. Plugging in $n+1$ in place of $n$, we get $n+1<2^{n+1}$, which is what we needed to show. This completes the inductive step.
\end{itemize}
\Part \textbf{Claim}: for all $x,y,n\in\N$, if $\max(x,y)=n$, then $x\leq y$.
\textbf{Proof}: the proof will be by induction on $n$.
\begin{itemize}
\item Base case: suppose that $n=0$. If $\max(x,y)=0$ and $x,y\in\N$, then $x=0$ and $y=0$, hence $x\leq y$.
\item Inductive hypothesis: assume that, whenever we have $\max(x,y)=k$, then $x\leq y$ must follow.
\item Inductive step: we must prove that if $\max(x,y)=k+1$, then $x\leq y$. Suppose $x,y$ are such that $\max(x,y)=k+1$. Then, it follows that $\max(x-1,y-1)=k$, so by the inductive hypothesis, $x-1\leq y-1$. In this case, we have $x\leq y$, completing the induction step.
\end{itemize}
\end{Parts}
\Question{Preserving Set Operations}
Prove that inverse images preserve set operations but images typically do not:
\begin{enumerate}
\item $f^{-1}(A \cup B) = f^{-1}(A) \cup f^{-1}(B)$.
\item $f^{-1}(A \cap B) = f^{-1}(A) \cap f^{-1}(B)$.
\item $f^{-1}(A \setminus B) = f^{-1}(A) \setminus f^{-1}(B)$.
\item $f(A \cup B) = f(A) \cup f(B)$.
\item $f(A \cap B) \subseteq f(A) \cap f(B)$, and give an example where equality does not hold.
\item $f(A \setminus B) \supseteq f(A) \setminus f(B)$, and give an example where equality does not hold.
\end{enumerate}
\Question{Grid Induction}
A bug is walking on an infinite 2D grid.
He starts at some location $(i, j) \in \N^2$ in the first quadrant,
and is constrained to stay in the first quadrant (say, by walls along the x and
y axes).
Every second he does one of the following (if possible):
\begin{enumerate}[(i)]
\item Jump one inch down, to $(i, j-1)$.
\item Jump one inch left, to $(i-1, j)$.
\end{enumerate}
For example, if he is at $(5, 0)$, his only option is to jump left to $(4, 0)$.
Prove that no matter how he jumps, he will always reach $(0, 0)$ in finite time.
\Question{A Tricky Game}
\begin{Parts}
\Part CS 70 course staff invite you to play a game: Suppose there are $n^2$ coins in a $n\times n$ grid ($n > 0$), each with their heads side up. In each move, you can pick one of the $n$ rows or columns and flip over all of the coins in that row or column. However, you are not allowed to re-arrange them in any other way. You have an unlimited number of moves. If you happen to reach a configuration where there is exactly one coin with its tails side up, you will win the game. Are you able to win this game? Find all values of $n$ for which you can win the game, and prove your statement. In other words, for each value of $n$ that you listed, prove that you can win the game; then, prove that it is impossible to win the game for all other values of $n$.
\Part (Optional) Now, suppose we change the rules: If the number of ``tails'' is between 1 and $n-1$, you win. Are you able to win this game? Does that apply to all $n$? Prove your answer.
\end{Parts}