 \documentclass[12pt,twoside]{article}

\usepackage{amsmath}

\input{../handouts/macros-course}

\def\cent{{\not\!\mathrm{c}}}
\renewcommand{\implies}{\longrightarrow}


%\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}
\askaboutsolutions

\begin{document}
\handout{tut1}{Mini-Quiz 1}{February 9, 2001}

\begin{enumerate}
\item Write your name:
\item (Rosen 1.2.13).  Determine whether $(\neg q \wedge (p \implies q))
  \implies  \neg p)$ is a tautology.

\end{enumerate}
\newpage

\thispagestyle{empty}

\mbox{}

\setcounter{page}{0}

\newpage

\handout{tut1}{Tutorial 1 Problems}{February 9, 2001}

\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%From Spring97
\problem{The Superman Problem}

\noindent Cast the following into propositional symbols, and verify or
refute:\\

{\em \noindent If Superman were able and willing to prevent evil, he would do
  so. If Superman were unable to prevent evil, he would be impotent.
  If he were unwilling to prevent evil, he would be malevolent.
  Superman does not prevent evil. If Superman exists, he is neither
  impotent nor malevolent. Therefore, Superman does not exist.}\\

A: Superman were able to prevent evil. \\
W: Superman were willing to prevent evil. \\
I: Superman is impotent. \\
M: Superman is malevolent. \\
P: Superman prevents evil. \\
E: Superman exists. \\

\solution{
\medskip
\textbf{Solution:}\\
We have the following assumptions:\\
\begin{tabular}{lll}
1 & $A \land W \rightarrow P$ &
    If Superman were able and willing to prevent evil, he would do so.\\
2 & $\neg A \rightarrow I$ &
    If Superman were unable to prevent evil, he would be impotent. \\
3 & $\neg W \rightarrow M$ &
    If he were unwilling to prevent evil, he would be malevolent. \\
4 & $\neg P$ & Superman does not prevent evil. \\
5 & $E \rightarrow \neg (M \lor I)$ &
    If Superman exists, he is neither impotent nor malevolent.
\end{tabular}\\[\medskipamount]
We now use these assumptions to prove $\neg E$, that Superman does not exist.\\
\begin{tabular}{lll}
  (i)   & $\lnot(A \land W)$ & Assumptions 1 and 4; modus tollens. \\
  (ii)  & $\lnot A \lor \lnot W$ & DeMorgan. \\
  (iii) & $(\neg A \lor \neg W) \rightarrow (I \lor M)$ & Assumptions 2 and 3. \\
  (iv) & $I \lor M$ & (ii) and (iii); modus ponens. \\
  (v)  & $\lnot E$ & Assumption 5 together with (iv); modus tollens.
\end{tabular}\\[\medskipamount]
Step (iii) above uses the fact that
\begin{displaymath}
  \bigl((a \rightarrow b) \land (c \rightarrow d)\bigr)
  \rightarrow
  \bigl((a \lor c) \rightarrow (b \lor d)\bigr),
\end{displaymath}
which should be proven as a separate lemma.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 \problem Identify \emph{precisely} what the bugs are in each of
 the following false proofs.

\begin{problemparts}
\ppart\label{log10}
\begin{align*}
    3 &> 2 \\
    3 \log_{10} (1/2) &> 2 \log_{10}(1/2) \\
    \log_{10} (1/2)^3 &> \log_{10} (1/2)^2 \\
    (1/2)^3 &> (1/2)^2 \\
    \mbox{Therefore, } 1/8 &> 1/4!
\end{align*}

\solution{$\log x < 0$, for $0<x<1$, so since both sides of the inequality
``$3 > 2$'' are being multiplied by the negative quantity
$\log_{10}(1/2)$, the inequality in the second line should have been the
reverse of the first line, that is, $<$ instead of $>$.}


\ppart\label{cents}
You are richer than you think:
\[1 \cent = \$0.01 = (\$0.1)^2 = (10\cent)^2 = \$1.\]

\solution{$\$0.01 = \$(0.1)^2 \neq (\$0.1)^2$ because the units $\$^2$ and
$\$$ don't match (just as in physics the difference between $sec^2$ and
$sec$ indicates the difference between acceleration and velocity).}

\ppart\label{millions} Consider the following scheme to make millions.
Obtain a slab of gold $10'' \times 11'' \times 1''$.  Then cut out two
little one-inch triangles at the corners.  These triangles are the
profit.  Finally, slide the two slabs together again and note that the
rectangle is now $11'' \times 10'' \times 1''$---the same size as it
was before we removed the small triangles.  By repeating the process,
we can produce an unlimited supply of gold!


\solution{The picture makes the little triangles look like right
  triangles, but they aren't.  So when the two large pieces left after
  the little triangles are removed are slid together, they do not form
  a rectangle, which means the resulting shape is not the same as the
  original figure. (This illustrates why ``proof by diagram'' is
  mathematically suspicious.)  }


\ppart
\textbf{Claim}: Every polynomial $p(x) = ax^2 + bx +c$ over $\complex$
(the complex numbers) has two roots.

Sounds good, but the claim is false.  Find the counterexamples and then
restate the claim so it is correct.


\begin{proof}[Suggested proof]
Using the usual formulas for the roots of a quadratic, let
\begin{eqnarray*}
r_1 & ::= & \frac{-b + \sqrt{D}}{2a}, \mbox{ and} \\
r_2 & ::= & \frac{-b - \sqrt{D}}{2a}, \mbox{ where}\\
D & ::= & b^2-4ac.
\end{eqnarray*}

To verify that $r_1$ is a root, note that
\begin{eqnarray*}
a{r_1}^2 & = &  a({\frac{-b +\sqrt{d}}{2a}})^2\\
& = & a\frac{b^2 -2b\sqrt{D} + D}{4a^2}\\
& = & \frac{b^2 -2b\sqrt{D} + b^2 -4ac}{4a}\\
& = & \frac{2b^2 -2b\sqrt{D} -4ac}{4a}\\
& = & \frac{b^2 -b\sqrt{D} -2ac}{2a}
\end{eqnarray*}
and
\begin{eqnarray*}
br_1 & = & b\frac{-b+\sqrt{D}}{2a}\\
 & = & \frac{-b^2+b\sqrt{D}}{2a}
\end{eqnarray*}
so
\begin{eqnarray*}
p(r_1) &=&{r_1}^2 + br_1 + c\\
& = & \frac{b^2 -b\sqrt{d} -2ac}{2a} + \frac{-b^2+b\sqrt{d}}{2a} +c\\
 & = & \frac{-2ac}{2a} + c = - c + c = 0,
\end{eqnarray*}
as claimed.  A similar calculation confirms that $p(r_2)=0$.
\end{proof}


\solution{%
The polynomial $0x^2 + 0x + 1$ has no roots.  The proof failed for this
case since it divides by $a$, which is unsound  when $a=0$.

The polynomial $x^2 + 2x + 1$ has only one root.  For $a\neq 0$, the
algebra is ok, but the proof assumes that $r_1 \neq r_2$, which will be
false when $D = 0$.

The proof is correct for polynomials with $a\neq 0 \neq D$ (even
though when $D < 0$, the meaning of $\sqrt{D}$ is ambiguous as we saw
in lecture). So these two conditions are required to make the claim
correct.}

\end{problemparts}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\problem
%From Spring00
A {\em group} is a set $G$ together with a binary operation $\cdot: G
\times G \rightarrow G$ that satisfies the following axioms.


Identify at least two ``normal'' sets and operations on them
  that satisfy the group axioms.

\begin{enumerate}
  
\item $\forall a,b,c \in G,(a \cdot b) \cdot c = a \cdot (b \cdot
  c)$.\label{axiom:associativity}
  
\item $\exists e \in G$ (called the {\em identity}) such that $\forall
  a \in G, a \cdot e = e \cdot a = a$.\label{axiom:identity}
  
\item $\forall a \in G, \exists a^{-1} \in G$ (called the {\em
    inverse} of $a$), such that $a \cdot a^{-1} = a^{-1} \cdot a =
  e$.\label{axiom:inverse}

\end{enumerate}

\solution{%
  Addition defines a group on the integers, and multiplication a group
  on the positive rationals.
  
  As an example of a finite group, let $G$ be the set of truth values,
  i.e., $G = \{T, F\}$, and the binary operation~$\cdot$ be~XOR. In
  this group, $F$~is the identity and $T$~is its own inverse.
  
  (The above group can be generalized: Consider for instance all 8-bit
  binary numbers and let the group operation be bit-wise XOR. This
  gives a group with 256~elements where 0 is the identity and every
  element is its own inverse.)}

Using the three group axioms prove the following propositions.

\begin{problemparts}

\ppart Show, by contradiction, that the identity element is unique.

\solution{%
  \begin{proof}[Proof by contradiction]
    Suppose there are two identities $e_1$ and~$e_2$ such that $e_1
    \neq e_2$. Then, by axiom~\ref{axiom:identity}, $e_1 e_2 = e_1$
    since $e_2$~is an identity, but, according to the same axiom, $e_1
    e_2 = e_2$ since $e_1$~is an identity. Thus $e_1 = e_2$, which
    contradicts our assumption that $e_1 \neq e_2$.
  \end{proof}}

\ppart Show that for every $g \in G$, the inverse of~$g$ is unique.
We can therefore write the inverse element as $g^{-1}$ with no fear of
ambiguity.

\solution{%
  \begin{proof}[Proof by contradiction]
    Consider an arbitrary $g \in G$.  Suppose there are two different
    inverses of~$g$; we denote them by $g^{-1}$ and~$g^*$. According
    to axiom~\ref{axiom:inverse}, $g^{-1}g = e$ and $gg^* = e$ since
    we assumed that $g^{-1}$ and~$g^*$ are inverses of~$a$. Thus,
    $(g^{-1}g)g^* = eg^* = g^*$, where the second equality follows
    from axiom~\ref{axiom:identity}. Similarly, $g^{-1}(gg^*) =
    g^{-1}e = g^{-1}$. But by axiom~\ref{axiom:associativity},
    $(g^{-1}g)g^* = g^{-1}(gg^*)$. To conclude,
    \begin{displaymath}
      g^* = eg^* = (g^{-1}g)g^* = g^{-1}(gg^*) = g^{-1}e = g^{-1},
    \end{displaymath}
    which contradicts our assumption that $g^{-1}$ and~$g^*$ are
    different.
  \end{proof}}

\ppart Show $\forall (g \in G) (g^{-1})^{-1} = g$

\solution{%
  \begin{proof}[Direct proof]
    Consider an arbitrary $g \in G$. By axiom~\ref{axiom:inverse} we
    know that $g^{-1} \in G$. If we can find some $h \in G$ satisfying
    axiom~\ref{axiom:inverse} where $a$ is instantiated with~$g^{-1}$ and
    $a^{-1}$~is instantiated with~$h$, i.e., some $h \in G$ such that
    $g^{-1}h = hg^{-1} = e$, we know---since we proved above that the
    inverse is unique---that $h$~is the inverse of~$g^{-1}$. However,
    the choice $h = g$ satisfies axiom~\ref{axiom:inverse}. Thus,
    $g$~is the inverse of~$g^{-1}$.
  \end{proof}}

\ppart Show $\forall g,h \in G, (g \cdot h)^{-1} = h^{-1} \cdot g^{-1}$

\solution{%
  \begin{proof}[Direct proof]
    As in the above proof, it suffices to verify that
    axiom~\ref{axiom:inverse} where $a$~is instantiated with~$gh$ and
    $a^{-1}$~is instantiated with~$h^{-1}g^{-1}$ holds. We have
    \begin{displaymath}
      (gh)(h^{-1}g^{-1}) = \bigl((gh)h^{-1}\bigr)g^{-1} =
      \bigl(g(hh^{-1})\bigr)g^{-1} = (ge)g^{-1} = gg^{-1} = e,
    \end{displaymath}
    where the first two equalities follow from
    axiom~\ref{axiom:associativity}, the third and fifth from
    axiom~\ref{axiom:inverse}, and the fourth from
    axiom~\ref{axiom:identity}. Similarly
    \begin{displaymath}
      (h^{-1}g^{-1})(gh) = \bigl((h^{-1}g^{-1})g\bigr)h =
      \bigl(h^{-1}(g^{-1}g)\bigr)h = (h^{-1}e)h = h^{-1}h = e,
    \end{displaymath}
    which completes the proof.
  \end{proof}}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%weighing problem. Appeared several times in previous terms.

\problem  You are given 12 identical looking balls, and told that
one of them is of different weight from the other 11, but you don't 
know in advance whether it is heavier or lighter. Can you
find the ball that is of different weight using only 3 weighings on a balance scale?


\solution{
\medskip
\textbf{Solution:}\\
The answer is Yes.

Step 1. Divide into groups of 4 balls. Place two of these groups
on two pans.

Two possible outcomes: 
\begin{enumerate}
\item Equal. So the 8 balls that were weighed must be of the same weight,
label them N (for ``normal'') and one of the other 4 is of different weight,
call them D.  

  Step 2. Place 3 D balls on one side and 3 N balls on the other side for
the second weighing.
Three possible outcomes again:
\begin{enumerate}
 \item Equal. The remaining D must be the ball of different weight.
 \item DDD side is heavier. So the ball of different weight is among these
three and heavier. Now we can finish in one more weighing using
the following approach: \\
Place a ball on each pan of the balance. There are 3 possible outcomes:
\begin{enumerate}
\item The left pan is heavier. Then the ball in the left pan is the answer.

\item The right pan is heaver. Then the ball in the right pan is the answer.

\item The pans are equal. Then the third ball must be the heavy one.

\end{enumerate}
 \item DDD side is lighter. Similar to previous case.
\end{enumerate}

\item Not Equal.  Call the heavier side balls H and the lighter side balls L.
Then there are 4 H's , 4 L's and 4 N's (the 4 that we didn't weigh are of
the same weight).

  Step 2. Place 3 H's and 1 L on one side and 1 H and 3 N's on the other side
for the second weighing. There are 3 possible outcomes:

\begin{enumerate}
\item Equal. The ball of different weight is among the remaining 3 L's
and is lighter. We can find it in one more weighing.

\item 3 H's , 1 L side is heavier. Then one of the three H's must be
heavier than the rest. We can find it in one more weighing.

\item 3 H's , 1 L side is lighter. Then either the L on this side is
lighter than the rest or the H on the other side is heavier than the rest.
We can compare one of them with an N ball and find the ball of different
weight!

\end{enumerate}

\end{enumerate}

\textbf{Alternative solution:}
\medskip

\textbf{Key:}
\begin{table}[h]
\begin{tabular}{|c|c|}
\hline
R&put ball on right tray \\ \hline
L&put ball on left tray  \\ \hline
N&leave ball out \\ \hline
\end{tabular}
\end{table}

{\bf Assignments on the scale}
\medskip

\begin{table}[h]
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
Balls&         1& 2& 3& 4& 5& 6& 7& 8& 9& 10 &11 &12\\ \hline
Weighing 1&    R &R &R &R &L &L &L &L &N &N &N &N \\  \hline
Weighing 2&    R &R &L &L &L &R &N &N &R &L &N &N \\  \hline
Weighing 3&    R &L &L &R &N &N &L &R &N &R &L &N \\   \hline
\end{tabular}
\end{table}
We observe what happens to the scale at each of the three weighings (balance, leans to the left, leans to the right). For example, if Ball 10 is Heavy, the scale will first balance, then lean to the right, then lean to the left. If Ball 10 is Light, the balance will behave in the ``opposite'' way: it will first balance, then lean to the left and then lean to the right. Notice that in all cases, only ONE column from the above table will match the observed behavior.

\paragraph{Conditions:} 
\begin{enumerate}
\item At each weighing, number of R = number of L (for balance)
\item Each triple (column) should be distinct. Moreover, its ``mirror image'' (L-R) should not be present since we don't know whether the ball is heavier or lighter. 
\end{enumerate}
}                   

\end{problems}
\end{document}

