% polyhedral solutions case analysis?
% prove at least 55 minutes to leave the island

\documentclass[twoside,12pt]{article}
\usepackage{light}

%\hidesolutions
\showsolutions

\begin{document}

\problemset{1}{February 1, 2005}{Monday, February 7 at 9 PM in Room 32-044}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\nand}{\text{ nand }}

\begin{problem}
The connectives $\wedge$ (and), $\vee$ (or), and $\implies$ (implies)
come often not only in computer programs, but also everyday speech.
But devices that compute the \textit{nand} operation are preferable in
computer chip designs.  Here is the truth table for nand:
%
\[
\begin{array}{cc|c}
P & Q & P \text{ nand } Q \\ \hline
\true & \true & \false \\
\true & \false & \true \\
\false & \true & \true \\
\false & \false & \true
\end{array}
\]
%
For each of the following expressions, find an equivalent expression
using only nand and $\neg$ (not).
%
\bparts

\ppart $A \wedge B$

\solution{$\neg (A \nand B)$}

\ppart $A \vee B$

\solution{$(\neg A) \nand (\neg B)$}

\ppart $A \implies B$

\solution{$A \nand (\neg B)$}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
A self-proclaimed ``great logician'' has invented a new quantifier, on
par with $\exists$ (``there exists'') and $\forall$ (``for all'').
The new quantifier is symbolized by $U$ and read ``there exists a
unique''.  The proposition $Ux\ P(x)$ is true iff there is
\textit{exactly one} $x$ for which $P(x)$ is true.  The logician has
noted, ``There used to be two quantifiers, but now there are three!  I
have extended the whole field of mathematics by 50\%!''

\bparts

\ppart Write a proposition equivalent to $U x\ P(x)$ using only the
$\exists$ quantifier, =, and logical connectives.

\solution{
\[
\exists x\ (P(x) \wedge \neg (\exists y\ (\neg (x = y) \wedge P(y)))
\]
}

\ppart Write a proposition equivalent to $U x\ P(x)$ using only the
$\forall$ quantifier, =, and logical connectives.

\solution{
\[
\neg \forall x\ (\neg P(x) \vee \neg \forall y\ (x = y \vee \neg P(y)))
\]
}
\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
A media tycoon has an idea for an all-news television network called
LNN: The Logic News Network.  Each segment will begin with the
definition of some relevant sets and predicates.  The day's happenings
can then be communicated concisely in logic notation.  For example, a
broadcast might begin as follows:

\begin{quotation}\noindent
``THIS IS LNN.  Let $S$ be the set $\set{ \mbox{Bill}, \mbox{Monica},
\mbox{Ken}, \mbox{Linda}, \mbox{Betty} }$.  Let $D(x)$ be a predicate
that is true if $x$ is deceitful.  Let $L(x, y)$ be a predicate that
is true if $x$ likes $y$.  Let $G(x, y)$ be a predicate that is true
if $x$ gave gifts to $y$.''
\end{quotation}

Complete the broadcast by translating the following statements into
logic notation.

\bparts

\ppart If neither Monica nor Linda is deceitful, then Bill and
Monica like each other.

\solution{
\[
(\neg (D(\mbox{Monica}) \vee D(\mbox{Linda}))) \implies
(L(\mbox{Bill}, \mbox{Monica}) \wedge L(\mbox{Monica}, \mbox{Bill}))
\]
}

\ppart Everyone except for Ken likes Betty, and no one except Linda
likes Ken.

\solution{
\begin{eqnarray*}
\forall x \in S\ (x  =   \mbox{Ken} \wedge \neg L(x, \mbox{Betty})) \vee
           (x \neq \mbox{Ken} \wedge      L(x, \mbox{Betty})) \wedge \\
\quad \quad
\forall x \in S\ (x  =   \mbox{Linda} \wedge      L(x, \mbox{Ken})) \vee
           (x \neq \mbox{Linda} \wedge \neg L(x, \mbox{Ken}))
\end{eqnarray*}
}

\ppart If Ken is not deceitful, then Bill gave gifts to
Monica, and Monica gave gifts to someone.

\solution{
\[
\neg D(\mbox{Ken}) \implies
        (G(\mbox{Bill}, \mbox{Monica}) \wedge
        \exists x \in S\ G(\mbox{Monica}, x))
\]
}

\ppart Everyone likes someone and dislikes someone else.

\solution{
\[
\forall x \in S\ \exists y \in S\ \exists z \in S\ (y \neq z) \wedge L(x, y) \wedge \neg L(x, z)
\]
}

\eparts
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bigskip

\begin{center}
\parbox{5.25in}{\textbf{The remaining problems will be graded primarily
on the clarity of your proofs--- not on whether you have the right
idea.  In fact, if you can't figure out the right idea, we'll give it
to you-- just ask your TA!}}
\end{center}

\bigskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Let $n$ be a postive integer.  Prove that $\log_2 n$ is rational if
and only if $n$ is a power of 2.  Assume any basic facts about
divisibility that you need; just state your assumptions explicitly.
\end{problem}

\solution{ \textbf{Assumption:} If $n^b$ is a power of 2, then $n$ is
a power of 2.

\begin{proof}
We prove that if $n$ is a power of 2, then $\log_2 n$ is rational and
vice-versa.

First, we prove that if $n$ is a power of 2, then $\log_2 n$ is
rational.  Assume that $n$ is a power of 2.  Then $n = 2^k$ for some
integer $k \geq 0$.  Thus, $\log_2 n = \log_2 2^k = k$, which is a
rational number.

Next, we prove that if $\log_2 n$ is rational, then $n$ is a power of
2.  Assume that $\log_2 n$ is rational.  That means there exist
integers $a$ and $b$ such that:
%
\[
\log_2 n = \frac{a}{b}
\]
%
We can rewrite this equation as follows:
%
\begin{align*}
n & = 2^{a/b} & \text{(Take 2 to power of each side.)} \\
n^b & = 2^a & \text{(Take the $b$-th power of each side.)}
\end{align*}
%
Thus, $n^b$ is a power of 2.  By our assumption, $n$ is a power of 2.
\end{proof}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
A \textit{triangle} is a set of three people such that either every
pair has shaken hands or no pair has shaken hands.  Prove that among
every six people there is a triangle.  Suggestion: Initially, break
the problem into two cases:
%
\begin{enumerate}
\item There exist at least three people who shook hands with person $X$.
\item There exist at least three people didn't shake hands with $X$
\end{enumerate}
%
(Why must at least one of these conditions hold?)
\end{problem}

\solution{
\begin{proof}
We use case analysis.  Let $X$ denote one of the six people.  There
are two possibilities:
%
\begin{enumerate}
\item There exist three people who shook hands with person $X$.  Now
there are two further possibilities:
%
\begin{enumerate}
\item Among these three, some pair shook hands.  Then these two and
$X$ form a triangle.
\item Among these three, no pair shook hands.  Then these three form a
triangle.
\end{enumerate}
%
\item Otherwise, at most two people shook hands with person $X$.
Thus, there exist three people who didn't shake hands with $X$.
Again, there are two further possibilities:
%
\begin{enumerate}
\item Among these three, every pair shook hands.  Then these three
form a triangle.
\item Among these three, some pair didn't shake hands.  Then these two
and $X$ for a triangle.
\end{enumerate}
\end{enumerate}
\end{proof}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Let $x$ and $y$ be nonnegative real numbers.  The \textit{arithmetic
mean} of $x$ and $y$ is defined to be $(x + y) / 2$, and the
\textit{geometric mean} is defined to be $\sqrt{x y}$.  Prove that the
arithmetic mean is equal to the geometric mean if and only if $x = y$.
\end{problem}

\solution{
\begin{proof}
We construct a chain of if-and-only-if implications.  The arithmetic
mean is equal to the geometric mean if and only if:
%
\begin{align*}
\frac{x + y}{2} & = \sqrt{x y} && \iff & x + y & = 2 \sqrt{x y} \\
&&& \iff & (x + y)^2 & = 4 x y \\
&&& \iff & x^2 + 2 x y + y^2 & = 4 x y \\
&&& \iff & x^2 - 2 x y + y^2 & = 0 \\
&&& \iff & (x - y)^2 & = 0 \\
&&& \iff & x - y & = 0 \\
&&& \iff & x & = y
\end{align*}
\end{proof}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Use case analysis to prove that all integral solutions to the equation
%
\[
\frac{1}{m} + \frac{1}{n} = \frac{1}{e} + \frac{1}{2}
\]
%
subject to these constraints
%
\begin{align*}
m & \geq 3 &
n & \geq 3 &
e & > 0
\end{align*}
%
are in this table:
%
\[
\begin{array}{ccc}
m & n & e \\ \hline
3 & 3 & 6 \\
3 & 4 & 12 \\
3 & 5 & 30 \\
4 & 3 & 12 \\
5 & 3 & 30
\end{array}
\]
%
These equations reveal something fundamental about the geometry of our
three-dimensional world; we'll revisit them in about three weeks.
\end{problem}

\solution{
\begin{proof}
We use case analysis.  Since $m \geq 3$, one of four cases must hold:
%
\begin{enumerate}
\item $m = 3$.  There are now four subcases:
\begin{enumerate}
\item $n = 3$.  Rewriting the equation in the form
%
\[
e = \frac{1}{\frac{1}{m} + \frac{1}{n} - \frac{1}{2}}
\]
%
and subtituting in $m = n = 3$ implies that $e = 6$, which is the
first solution.
\item $n = 4$.  Substituting the values of $m$ and $n$ into the
equation show that $e = 12$, which is the second solution.
\item $n = 5$.  Substituting into the equation shows that $e = 30$,
which is the third solution.
\item $n \geq 6$.  This implies:
%
\[
\frac{1}{m} + \frac{1}{n} \leq \frac{1}{3} + \frac{1}{6} = \frac{1}{2}
\]
%
Thus, the left side of the equation is strictly less than the right
for all $e > 0$, so there are no solutions in this case.
\end{enumerate}
%
\item $m = 4$.  There are two subcases:
%
\begin{enumerate}
\item $n = 3$.  Subsituting gives $e = 12$, which is the fourth
solution.
\item $n \geq 4$.  This implies:
%
\[
\frac{1}{m} + \frac{1}{n} \leq \frac{1}{4} + \frac{1}{4} = \frac{1}{2}
\]
%
Again, the left side of the equation is strictly less than the right
for all $e > 0$, so there are no solutions in this case.
\end{enumerate}
%
\item $m = 5$.  There are two subcases:
%
\begin{enumerate}
\item $n = 3$.  Subsituting gives $e = 30$, which is the fifth
solution.
\item $n \geq 4$.  This implies:
%
\[
\frac{1}{m} + \frac{1}{n} \leq \frac{1}{5} + \frac{1}{4} < \frac{1}{2}
\]
%
Again, the equation can not hold, so there are no solutions in this
case.
\end{enumerate}
%
\item $m \geq 6$.  This implies:
%
\[
\frac{1}{m} + \frac{1}{n} \leq \frac{1}{6} + \frac{1}{3} = \frac{1}{2}
\]
%
Once more, the equation can not hold, so there are no solutions in
this case.
\end{enumerate}
\end{proof}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
