%
% LaTeX Problem Set Template by Sachin Padmanabhan
% I created this when I was a freshman in CS 103,
% and I continue to use it to this day.
%
% Hope you enjoy!
%
% There may be problems with this template.
% If so, feel free to contact me.
%
\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
\usepackage[margin=1in]{geometry}
\usepackage{multicol}
\usepackage{bm}
\usepackage{listings}
\PassOptionsToPackage{usenames,dvipsnames}{color} %% Allow color names
\usepackage{pdfpages}
\usepackage{algpseudocode}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage{wasysym}
\usepackage[thinlines]{easytable}
\usepackage{minted}
\usepackage{wrapfig}
\usepackage{hyperref}
\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#2}
\author{Sachin Padmanabhan}
\date{\today}
\lhead{Sachin Padmanabhan}
\chead{Problem Set \#2}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Winter 2018}
\rfoot{\thepage}
\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\absfit}[1]{\left\lvert #1 \right\rvert}
\newcommand{\norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\eval}[3]{\left[#1\right]_{#2}^{#3}}
\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\pd}[1]{\frac{\partial}{\partial #1}}
\newcommand{\inner}[1]{\langle#1\rangle}
\newcommand{\cond}{\bigg|}
\newcommand{\rank}[1]{\mathbf{rank}(#1)}
\newcommand{\range}[1]{\mathbf{range}(#1)}
\newcommand{\nullsp}[1]{\mathbf{null}(#1)}
\newcommand{\repr}[1]{\left\langle#1\right\rangle}
\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Tr}{\mathbf{Tr}}
\DeclareMathOperator{\diag}{\mathbf{diag}}
\DeclareMathOperator{\dist}{\mathbf{dist}}
\DeclareMathOperator{\prob}{\mathbf{prob}}
\DeclareMathOperator{\dom}{\mathbf{dom}}
\DeclareMathOperator{\E}{\mathbf{E}}
\DeclareMathOperator{\Q}{\mathbb{Q}}
\DeclareMathOperator{\R}{\mathbb{R}}
\DeclareMathOperator{\var}{\mathbf{var}}
\DeclareMathOperator{\quartile}{\mathbf{quartile}}
\DeclareMathOperator{\conv}{\mathbf{conv}}
\DeclareMathOperator{\VC}{VC}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator{\Ber}{Bernoulli}
\DeclareMathOperator{\NP}{\mathbf{NP}}
\DeclareMathOperator{\coNP}{\mathbf{coNP}}
\DeclareMathOperator{\TIME}{\mathsf{TIME}}
\DeclareMathOperator{\polytime}{\mathbf{P}}
\DeclareMathOperator{\PH}{\mathbf{PH}}
\DeclareMathOperator{\SIZE}{\mathbf{SIZE}}
\DeclareMathOperator{\ATIME}{\mathbf{ATIME}}
\DeclareMathOperator{\SPACE}{\mathbf{SPACE}}
\DeclareMathOperator{\ASPACE}{\mathbf{ASPACE}}
\DeclareMathOperator{\NSPACE}{\mathbf{NSPACE}}
\DeclareMathOperator{\Z}{\mathbb{Z}}
\DeclareMathOperator{\N}{\mathbb{N}}
\DeclareMathOperator{\EXP}{\mathbf{EXP}}
\DeclareMathOperator{\NEXP}{\mathbf{NEXP}}
\DeclareMathOperator{\NTIME}{\mathbf{NTIME}}
\DeclareMathOperator{\DTIME}{\mathbf{DTIME}}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\BPP}{\mathbf{BPP}}
\DeclareMathOperator{\ZPP}{\mathbf{ZPP}}
\DeclareMathOperator{\RP}{\mathbf{RP}}
\DeclareMathOperator{\coRP}{\mathbf{coRP}}
\DeclareMathOperator{\BPL}{\mathbf{BPL}}
\DeclareMathOperator{\IP}{\mathbf{IP}}
\DeclareMathOperator{\PSPACE}{\mathbf{PSPACE}}
\DeclareMathOperator{\NPSPACE}{\mathbf{NPSPACE}}
\DeclareMathOperator{\SAT}{\mathsf{SAT}}
\DeclareMathOperator{\NL}{\mathbf{NL}}
\DeclareMathOperator{\PCP}{\mathbf{PCP}}
\DeclareMathOperator{\PP}{\mathbf{PP}}
\DeclareMathOperator{\cost}{cost}
\let\Pr\relax
\DeclareMathOperator*{\Pr}{\mathbf{Pr}}
\definecolor{shadecolor}{gray}{0.95}
\theoremstyle{plain}
\newtheorem*{lem}{Lemma}
\theoremstyle{plain}
\newtheorem*{claim}{Claim}
\theoremstyle{definition}
\newtheorem*{answer}{Answer}
\newtheorem{theorem}{Theorem}[section]
\newtheorem*{thm}{Theorem}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}
\setlength{\parindent}{0pt}
\pagestyle{fancy}
\RecustomVerbatimEnvironment{Verbatim}{BVerbatim}{}
\hypersetup{urlcolor=blue}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\begin{document}
\maketitle
\section{Implies and False}
Although propositional logic has many different connectives,
it turns out that any formula in propositional
logic can be rewritten as an equivalent propositional
formula that uses only the $\neg$, $\land$, and $\top$ connectives.
(You don't need to prove this).
In this problem,
you will prove a different result:
every formula in propositional
logic can be rewritten as an equivalent logical formula purely using the
$\rightarrow$ and $\perp$ connectives.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Find a formula that's logically equivalent to $\neg p$
that uses only the variable $p$ and the $\rightarrow$ and $\perp$ connectives.
No justification is necessary.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Find a formula that's logically equivalent to $\top$
that uses only the $\rightarrow$ and $\perp$ connectives.
No justification is necessary.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Find a formula that's logically equivalent to $p \land q$
that uses only the variables $p$ and $q$ and the $\rightarrow$
and $\perp$ connectives.
No justification is necessary.
\textit{\textcolor{blue}{As a hint, what happens if you negate an implication?}}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{enumerate}
Since you can express $\neg$, $\land$, and $\top$ using just $\rightarrow$
and $\top$,
every possible formula in propositional logic can
be expressed using purely the $\rightarrow$ and $\bot$ connectives.
Nifty!
\section{Ternary Conditionals}
Many programming languages support a
\emph{ternary conditional operator}.
For example, in C, C++, and Java,
the expression $x$ ? $y$ : $z$ means
``evaluate the boolean expression $x$.
If it's true, the entire expression evaluates to $y$.
If it's false, the entire expression evaluates to $z$.'' \\
In the context of propositional logic,
we can introduce a new ternary connective ?: such that $p$ ? $q$ : $r$
means ``if $p$ is true, the connective evaluates to the truth value of $q$,
and otherwise it evaluates to the truth value of $r$.''
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Based on this description, write a truth table for the ?: connective.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Find a propositional formula equivalent to $p$ ? $q$ : $r$
that does not use the ?: connective.
Justify your answer by writing a truth table for your new formula.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{enumerate}
It turns out that it's possible to rewrite any formula
in propositional logic using only ?:, $\top$, and $\perp$.
The rest of this question will ask you to show this.
\begin{enumerate}[resume*]
\item Find a formula equivalent to $\neg p$
that does not use any connectives besides ?:, $\top$, and $\perp$.
No justification is necessary.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Find a formula equivalent to $p \rightarrow q$
that does not use any connectives besides ?:, $\top$, and $\perp$.
No justification is necessary.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{enumerate}
Since all remaining connectives can be written purely
in terms of $\neg$ and $\rightarrow$,
any propositional formula using the seven standard connectives
can be rewritten using only the three connectives ?:, $\top$, and $\perp$. \\
The fact that all propositional formulas can be written
purely in terms of ?:, $\top$, and $\perp$ forms the basis for
the \textit{binary decision diagram},
a data structure for compactly encoding propositional formulas.
Binary decision diagrams have applications in program optimization,
graph algorithms, and computational complexity theory.
Take CS166 or CS243 for more info!
\section{Executable Logic}
\begin{shaded}
Submit your edited $\mathsf{ExecutableLogic.cpp}$ file through GradeScope.
\end{shaded}
\section{First-Order Negations}
\textit{\textbf{(We will cover the material necessary to solve this problem on Monday. You can also read over the Guide to
Negations, which covers all the skills you'll need.)}} \\
For each of the first-order logic formulas below,
find a first-order logic formula that is the negation of the
original statement.
Your final formula must not have any negations in it
except for direct negations of predicates.
For example,
the negation of the formula
$\forall x.\ (P(x) \rightarrow \exists y.\ (Q(x) \land R(y)))$
could be found by
pushing the negation in from the outside inward as follows:
\begin{align*}
&\neg (\forall x.\ (P(x) \rightarrow \exists y.\ (Q(x) \land R(y)))) \\
&\exists x.\ \neg(P(x) \rightarrow \exists y.\ (Q(x) \land R(y))) \\
&\exists x.\ (P(x) \land \neg\exists y.\ (Q(x) \land R(y))) \\
&\exists x.\ (P(x) \land \forall y.\ \neg(Q(x) \land R(y))) \\
&\exists x.\ (P(x) \land \forall y.\ (Q(x) \rightarrow \neg R(y)))
\end{align*}
Show every step of the process
of pushing the negation into the formula
(along the lines of what is done above), and
\textit{please preserve the indentation from the original formula} as you go.
You don't need to formally prove that your negations are correct. \\
We strongly recommend reading
over the Guide to Negations before starting this problem.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item
$\begin{aligned}[t]
&\exists p.\ (\textit{Problem}(p) \land \\
&\qquad \forall g.\ (\textit{Program}(g) \rightarrow
\neg \textit{Solves}(g, p)) \\
&)
\end{aligned}$
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item
$\begin{aligned}[t]
&\forall x \in \R.\ \forall y \in \R.\ (x < y \rightarrow \\
&\qquad \exists q \in \Q.\ (x < q \land q < y) \\
&)
\end{aligned}$
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item
$(\forall x.\ \forall y.\ \forall z.\ (R(x, y) \land
R(y, z) \rightarrow R(x, z))) \rightarrow
(\forall x.\ \forall y.\ \forall z.\ (R(y, x) \land R(z, y)
\rightarrow R(z, x)))$
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item
$\begin{aligned}[t]
&\forall x.\ \exists S.\ (\textit{Set}(S) \land \\
&\qquad \forall z.\ (z \in S \leftrightarrow z = x) \\
&)
\end{aligned}$
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item
$\begin{aligned}[t]
&\forall k.\ (\textit{SixClique}(k) \rightarrow \\
&\qquad \exists t.\ (\textit{Triangle}(t, k)\ \land \\
&\qquad\qquad (\forall e.\ (\textit{Edge}(e, t) \rightarrow
\textit{Red}(e)) \lor \forall e.\ (\textit{Edge}(e, t) \rightarrow
Blue(e))) \\
&\qquad) \\
&)
\end{aligned}$
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{enumerate}
\section{Vacuous Truths}
\textit{\textbf{(We will cover the material necessary to solve this problem on Monday. You can also read over the Guide to
Negations, which covers all the skills you'll need.)}} \\
A statement is called \textbf{\textit{vacuously true}} if either
\begin{itemize}
\item it's an implication of the form $P \rightarrow Q$ where $P$ is false,
\item it's a universally-quantifed implication $\forall x.\ (P(x) \rightarrow Q(x))$ where $P(x)$ is never true, or
\item it's a universally-quantifed implication $\forall x \in S.\ Q(x)$ where $S$ is the empty set.
\end{itemize}
These statements are true \textit{by definition}. In the first case,
the truth table for the $\rightarrow$ connective says the
implication is true when the antecedent is false, and in the second
and third cases we just define these sorts of statements to be true. \\
You might be wondering why exactly this is the case.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Negate the propositional formula $P \rightarrow Q$ and push the negations as deep as possible. Now, look at
the resulting formula. Explain why when $P \rightarrow Q$ is vacuously true, its negation is false.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Negate the first order formula $\forall x.\ (P(x) \rightarrow Q(x))$ and push the negations as deep as possible. Now,
look at the resulting formula. Explain why if the original formula is vacuously true, then its negation is false.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Negate the first order formula $\forall x \in S.\ Q(x)$ and push the negations as deep as possible. Now, look
at the resulting formula. Explain why if the original formula is vacuously true, then its negation is false.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{enumerate}
Your answers to parts (i), (ii), and (iii) of this problem give another justification for vacuous truths. The
three classes of statements given above have false negations in the indicated cases, and therefore to keep
everything consistent we choose to define them as true.
\begin{enumerate}[resume,label*=\roman*.,ref=\roman*]
\item Now, look back over the code you wrote for parts (ii), (iv), and (v) of the Executable Logic problem.
In the course of writing those functions, you should not have needed to add in any special
case logic to handle groups of people where the formulas were vacuously true. (If you did, see if
you can go back and remove it!) Briefly explain why it's not necessary to handle these cases explicitly
and why your code, as written, will correctly handle empty inputs without any special-case logic.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{enumerate}
Your answer to part (iv) of this problem gives a different intuition for why statements would be vacuously
true - vacuous truth naturally follows from how we might think about checking whether a universally-quantifed
formula would be true.
\section{This, But Not That}
\begin{shaded}
Submit your five edited $\mathsf{.people}$ files through GradeScope.
\end{shaded}
\section{Translating into Logic}
\textit{\textbf{(We will cover the material necessary to solve this problem on Monday. You can also read over the Guide to
First-Order Translations, which covers all the skills you'll need.)}} \\
In each of the following,
you will be given a list of first-order predicates and functions
along with an English sentence.
In each case,
write a statement in first-order logic that expresses
the indicated sentence.
Your statement may use any first-order construct
(equality, connectives, quantifiers, etc.),
but you \textbf{\textit{must}} only use the predicates, functions,
and constants provided.
You do not need to provide the simplest formula
possible, though we'd appreciate it if you made an effort to do so.
\smiley \ We \textit{\textbf{highly}} recommend reading the
Guide to First-Order Logic Translations before starting this problem.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Given the predicate
\qquad $\textit{Natural}(x)$,
which states that $x$ is an natural number
and the functions
\qquad $x + y$, which represents the sum of $x$ and $y$, and
\qquad $x \cdot y$, which represents the product of $x$ and $y$
write a statement in first-order logic that says
``for any $n \in \N$, $n$ is even if and only if
$n^2$ is even.''
\textit{\textcolor{blue}{Try translating this statement assuming you have a predicate Even(x). Then, rewrite your solution without
using Even(x). Numbers aren't a part of FOL, so you can't use the number 2 in your solution.}}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Given the predicates
\qquad $\textit{Person}(p)$,
which states that $p$ is a person;
\qquad $\textit{Kitten}(k)$,
which states that $k$ is a kitten; and
\qquad $\textit{HasPet}(o, p)$,
which states that $o$ has $p$ as a pet,
write a statement in first-order logic that says
``someone has exactly two pet kittens and no other
pets.''
\textit{\textcolor{blue}{ Make sure your formula requires that the person
have \textit{exactly} two pet kittens; look at the lecture example of
uniqueness as a starting point. Good questions to ask --
is your formula false if everyone has exactly one pet
kitten? Is it false if everyone has exactly three pet kittens? }}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item The \textbf{\textit{axiom of pairing}}
is the following statement:
given any two distinct objects $x$ and $y$,
there's a set containing $x$ and $y$ and nothing else.
Given the predicates
\qquad $x \in y$, which states that $x$ is an element of $y$, and
\qquad $\textit{Set}(S)$, which states that $S$ is a set,
write a statement in first-order logic that expresses the axiom of pairing.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Given the predicates
\qquad $x \in y$, which states that $x$ is an element of $y$, and
\qquad $\textit{Set}(S)$, which states that $S$ is a set,
write a statement in first-order logic that says
``every set has a power set.''
\textit{\textcolor{blue}{ As a warm-up, solve this problem assuming you have a predicate
$X \subseteq Y$ that says that X is a subset of Y.
Once you have that working, see if you can solve the full version of this problem. }}
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\item Given the predicates
\qquad $\textit{Lady}(x)$, which states that $x$ is a lady;
\qquad $\textit{Glitters}(x)$, which states that $x$ glitters;
\qquad $\textit{SureIsGold}(x, y)$,
which states that $x$ is sure that $y$ is gold;
\qquad $\textit{Buying}(x, y)$, which states that $x$ buys $y$; and
\qquad $\textit{StairwayToHeaven}(x)$,
which states that $x$ is a Stairway to Heaven;
write a statement in first-order logic that says
``there's a lady who's sure all that glitters is gold,
and she's buying a Stairway to Heaven.''
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{enumerate}
\section{Hereditary Sets}
Let's begin with a fun little definition:
\begin{center}
A set $S$ is called a \textbf{\textit{hereditary set}}
if all its elements are hereditary sets.
\end{center}
This definition might seem strange because it's self-referential --
it defines the hereditary sets in terms of
other hereditary sets!
However, it turns out that this is a perfectly reasonable
definition to work with,
and in this problem you'll explore some properties
of these types of sets.
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Given the self-referential nature
of the definition of hereditary sets,
it's not even clear that hereditary sets even exist at all!
As a starting point,
prove that there is at least one hereditary set.
\begin{shaded}
Provide a proof here.
\end{shaded}
\item Prove that if $S$ is a hereditary set,
then $\wp(S)$ is also a hereditary set.
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}
\textit{\textcolor{blue}{ Before you turn in these proofs, be sure to read over the Proofwriting Checklist and to go one item at a time through each of your proofs. Here are a few specific things to look for:
\begin{itemize}
\item If you want to prove in part (ii) that a set T is a hereditary set, you need to prove the statement ``every
element of T is a hereditary set.'' That's a universally-quantifed statement. If you're proving it
via a direct proof, you'll probably need to pick some arbitrary element $x \in T$, then prove that x is a
hereditary set by making specific claims about the variable x. Read over your proof and make sure
that (1) you've introduced a new variable to refer to some arbitrarily-chosen element of T and that
(2) you're making specific claims about the variable x, rather than talking in general about how elements
of T behave. You may need to introduce multiple variables in the course of your proofs.
\item A common mistake we see people make when they're just getting started is to restate definitions in
the abstract in the middle of a proof. For example, we commonly see people say something like
``since $A \subseteq B$, we know that every element of A is an element of B.'' When you're writing a proof,
you can assume that whoever is reading your proof is familiar with the definitions of relevant
terms, so statements like the one here that just restate a definition aren't necessary. Instead of restating
definitions, try to apply those definitions. A better sentence would be something to the effect of
``Since $x \in A$ and $A \subseteq B$, we see that $x \in B$,'' which uses the definition to conclude something about a
specific variable rather than just restating the definition.
\item Although we've just introduced first-order logic as a tool for formalizing definitions and reasoning
about mathematical structures, the convention is to \textbf{not} use first-order logic notation (connectives,
quantifiers, etc.) in written proofs. In a sense, you can think of first-order logic as the stage crew in
the theater piece that is a proof -- it works behind the scenes to make everything come together, but
it's not supposed to be in front of the audience. Make sure that you're still writing in complete sentences,
that you're not using symbols like $\forall$ or $\rightarrow$ in place of words like ``for any'' or ``therefore,'' etc.
\end{itemize}
}}
\newpage
\section{Symmetric Latin Squares}
A \textbf{\textit{Latin square}} is an $n \times n$ grid filled with
the numbers $1,2,3,\dots,n$ such that every number appears
in every row and every column exactly once.
For example, the following are Latin squares:
\begin{figure}[h!]
\centering
\begin{minipage}{2cm}
\begin{TAB}(e,0.5cm,0.5cm){|c|c|c|}{|c|c|c|}
1 & 2 & 3 \\
3 & 1 & 2 \\
2 & 3 & 1
\end{TAB}
\end{minipage}
\begin{minipage}{2.5cm}
\begin{TAB}(e,0.5cm,0.5cm){|c|c|c|c|}{|c|c|c|c|}
4 & 2 & 1 & 3 \\
1 & 3 & 2 & 4 \\
3 & 1 & 4 & 2 \\
2 & 4 & 3 & 1
\end{TAB}
\end{minipage}
\begin{minipage}{3cm}
\begin{TAB}(e,0.5cm,0.5cm){|c|c|c|c|c|}{|c|c|c|c|c|}
1 & 3 & 5 & 2 & 4 \\
2 & 4 & 1 & 3 & 5 \\
3 & 5 & 2 & 4 & 1 \\
4 & 1 & 3 & 5 & 2 \\
5 & 2 & 4 & 1 & 3
\end{TAB}
\end{minipage}
\end{figure}
A \textbf{\textit{symmetric Latin square}} is a Latin square that is
symmetric across the main diagonal (the one from the
upper-left corner to the lower-right corner).
That is, the elements at positions $(i, j)$ and $(j, i)$ are always the same.
For example:
\begin{figure}[h!]
\centering
\begin{minipage}{2cm}
\begin{TAB}(e,0.5cm,0.5cm){|c|c|c|}{|c|c|c|}
1 & 2 & 3 \\
2 & 3 & 1 \\
3 & 1 & 2
\end{TAB}
\end{minipage}
\begin{minipage}{2.5cm}
\begin{TAB}(e,0.5cm,0.5cm){|c|c|c|c|}{|c|c|c|c|}
4 & 2 & 3 & 1 \\
2 & 3 & 1 & 4 \\
3 & 1 & 4 & 2 \\
1 & 4 & 2 & 3
\end{TAB}
\end{minipage}
\begin{minipage}{3cm}
\begin{TAB}(e,0.5cm,0.5cm){|c|c|c|c|c|}{|c|c|c|c|c|}
1 & 2 & 3 & 4 & 5 \\
2 & 4 & 5 & 3 & 1 \\
3 & 5 & 2 & 1 & 4 \\
4 & 3 & 1 & 5 & 2 \\
5 & 1 & 4 & 2 & 3
\end{TAB}
\end{minipage}
\end{figure}
Prove that in any $n \times n$ symmetric Latin square
where $n$ is odd, every number $1, 2, 3, \dots, n$ must appear
at least once on the main diagonal. \\
\textit{\textcolor{blue}{ As a hint: split the Latin square into three regions --
the main diagonal and the two regions above and below
the main diagonal. Then think about how often each element
appears in each group. }} \\
\textit{\textcolor{blue}{ Once you've written up a draft of your proof for this problem, try out the following exercise as a way of
checking your work. If you look at the sample Latin squares shown above, you can see that the result given
above is not true in the case where the Latin square isn't symmetric, and it's also not true in the case where
the square has even size. As a result, if your proof does not specifically use the fact that the Latin square is
symmetric and does not specifically use the fact that the Latin square has odd size, it has to contain an error
somewhere. Otherwise, you could change the setup to the problem and end up with a proof of an incorrect
result. (Do you see why this is?) So go back over your proof and ask yourself -- where, specifically, am I
making reference to the fact that the Latin square is symmetric? Where, specifically, am I making reference
to the fact that the Latin square has odd size? And why would my proof break down if I eliminated either
of those references? }} \\
\textit{\textcolor{blue}{ Going forward, this approach to checking your proofs --
perturbing the starting assumptions and seeing
where your logic breaks down -- is an excellent way to smoke out any underlying logic errors. }}
\begin{shaded}
Provide a proof here.
\end{shaded}
\newpage
\section{Tournament Winners}
Here's one more problem to help you practice your proofwriting.
It's a classic CS103 problem,
and we hope that you enjoy it! \\
\begin{wrapfigure}{l}{3.75cm}
\begin{tikzpicture}[x=1.5cm, y=1.5cm]
\node[draw, circle] (C) at (1, 0) {$C$};
\node[draw, circle] (B) at
(0.30901699437494745, 0.9510565162951535) {$B$};
\node[draw, circle] (A) at
(-0.8090169943749473, 0.5877852522924732) {$A$};
\node[draw, circle] (E) at
(-0.8090169943749475, -0.587785252292473) {$E$};
\node[draw, circle] (D) at
(0.30901699437494723, -0.9510565162951536) {$D$};
\path[->] (B) edge (A);
\path[->] (C) edge (A);
\path[->] (D) edge (A);
\path[->] (A) edge (E);
\path[->] (B) edge (C);
\path[->] (B) edge (D);
\path[->] (E) edge (B);
\path[->] (C) edge (D);
\path[->] (C) edge (E);
\path[->] (D) edge (E);
\end{tikzpicture}
\end{wrapfigure}
A \textbf{\textit{tournament}}
is a contest among $n$ players.
Each player plays a game against
each other player,
and either wins or loses the game
(let's assume that there are no draws).
We can visually represent a tournament by drawing a circle for each
player and drawing arrows between pairs of players
to indicate who won each game.
For example,
in the tournament to the left,
player $A$ beat player $E$, but
lost to players $B$, $C$, and $D$. \\
A \textbf{\textit{tournament winner}}
is a player in a tournament who, for each other player,
either won her game against that player,
or won a game against a player who in
turn won his game against that player (or both).
For example, in the graph on
the left,
players B, C, and E are tournament winners.
However, player D is \textbf{\textit{not}} a tournament winner,
because he neither beat player C,
nor beat anyone who in turn beat player C.
Although player D won against
player E, who in turn won against player B,
who then won against player C, under our definition player D
is not a tournament winner.
\emph{(Make sure you understand why!)} \\
\begin{enumerate}[label*=\roman*.,ref=\roman*]
\item Let $T$ be an arbitrary tournament
and $p$ be any player in that tournament.
Prove the following statement:
if $p$ won more games than anyone else in $T$
or is tied for winning the greatest number of games,
then $p$ is a tournament winner in $T$.
\textit{\textcolor{blue}{ This problem is a lot easier to solve if you draw the right picture. Something to think about: what happens if a player p \textbf{isn't} a winner in a tournament? What would that mean about player p? And finally, be careful
not to make broad claims about tournaments or tournament structures without first proving them! }}
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}
A corollary of the result you proved in part (i) is that every tournament with at least one player must have
at least one tournament winner -- you can always pick someone who won the most games or is tied for
winning the most games. However, note that you can win a tournament without necessarily winning the
most games -- for example, player $E$ in the above example tournament is a winner, though player $E$ only
won a single game! \\
Whenever you prove a new mathematical result (in this case, every tournament with at least one player
has at least one winner), it's useful to ask how ``resilient'' that result is. In other words, if we relax our definition
of a tournament a little bit, can we still necessarily guarantee that we can always find a winner? The
answer is no, and in fact, even slightly weakening the definition of a tournament invalidates this result. \\
Let's introduce one more definition. A \textbf{\textit{pseudotournament}} is like a tournament,
except that exactly one pair of people don't play each other.
\begin{enumerate}[resume*]
\item Prove that for any $n \geq 2$,
there's a pseudotournament $P$ with $n$ players
and no tournament winners.
\textit{\textcolor{blue}{ Think about the structure of what you're being asked to prove here. There's both a universal and an existential component to this statement. How do you prove an existential statement? }}
\begin{shaded}
Provide a proof here.
\end{shaded}
\end{enumerate}
\section*{Optional Fun Problem: Insufficient Connectives
(1 Point Extra Credit)}
On some of the earlier problems on this problem set, you
that every propositional logic formula could be
written in terms of just the $\neg$, $\land$, and $\top$. You also saw that you could use just $\rightarrow$ and $\bot$, or alternatively that you could just use ?:, $\top$, and $\bot$. \\
Interestingly, you cannot express every possible propositional logic formula using just the $\leftrightarrow$ and $\bot$ connectives. Prove why not.
\begin{shaded}
\begin{answer}
Write your answer here.
\end{answer}
\end{shaded}
\end{document}