% Quiz 1, CSCE 235, spring 2007
% 2 February 2007

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=6truein \vsize=9truein
\pdfhorigin=1.25truein \pdfvorigin=1truein

\headline={\hfil}
\footline={\hfil}

% Pilfered from an example on page 106 of the TeXbook
\def\qed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}

\noindent\hskip3.25truein{\bf NAME:} [Solutions]

\medskip

\centerline{CSCE~235 Quiz~1 (Solutions)}
\centerline{February~2, 2007}

\bigskip

\noindent Determine whether each of the following proofs is a direct proof, a
proof by contraposition, or a proof by contradiction.

\bigskip

\noindent\llap{1.\enspace}%
{\bf Proposition.} If $n$ is an integer and $n^3+5$ is odd, then $n$ is even.

\smallskip

\noindent{\bf Proof.} Suppose that $n$ is odd. Then there exists an integer~$k$
such that $n=2k+1$. So
$$n^3+5=(2k+1)^3+5=(8k^3+12k^2+6k+1)+5=8k^3+12k^2+6k+6=2(4k^3+6k^2+3k+3).$$
Taking $\ell=4k^3+6k^2+3k+3$, which is an integer, we see that $n^3+5=2\ell$,
so $n^3+5$ is even. Therefore, if $n^3+5$ is odd, then $n$ is even. \qed

\bigskip

\noindent{\bf Solution.} Let $p$ be the statement ``$n^3+5$ is odd'' and let
$q$ be the statement ``$n$ is even''. We are asked to prove that $p\to q$ is
true for all integers~$n$. In this proof, we first suppose that $n$ is odd
(that~is, we suppose $\lnot q$ is true), and then we reason by rules of
inference to conclude that $n^3+5$ must be even (that~is, $\lnot p$ must be
true). So we have proved $\lnot q\to\lnot p$, which is the
${\it contrapositive\/}$ of the statement we are asked to prove. Therefore,
this is a {\bf proof by contraposition}.

\bigskip

\noindent\llap{2.\enspace}%
{\bf Proposition.} There is no smallest positive rational number.

\smallskip

\noindent{\bf Proof.} Assume that there is a smallest positive rational number;
call it~$r$. Since $r$ is rational, we may write it as $r=p/q$ for some
integers $p$ and~$q$. Now consider the number~$r/2=p/(2q)$. Since $r$ is
positive, $r/2$~is positive, and $r/2$ is smaller than~$r$. Moreover, since $q$
is an integer, $2q$~is an integer. Thus $r/2$ is rational. This contradicts our
assumption that $r$ is the smallest positive rational number; therefore, we
conclude that there is no smallest positive rational number. \qed

\bigskip

\noindent{\bf Solution.} Here we are not asked to prove a statement of the form
$p\to q$; rather, we are asked to prove that some object does not exist, so
this is a ``nonexistence'' proof. Since there is no implication ($p\to q$) in
the statement of the proposition we are asked to prove, it does not make sense
to use a proof by contraposition, because contrapositives exist only for
implications.

In this proof we begin by assuming that the proposition is false. We then use
logical reasoning to produce a {\it contradiction\/}: namely, if there is a
smallest positive rational number~$r$, then there is a number smaller than~$r$
which is both positive and rational, so $r$ is not the smallest positive
rational number. Since this proof supposes the proposition is false and then
reaches a contradiction, it is a {\bf proof by contradiction}.

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent\llap{3.\enspace}%
{\bf Proposition.} Every odd integer is the difference of two perfect squares.
[Recall that a {\it perfect square}, commonly called just a {\it square}, is an
integer~$m$ with the property that there exists an integer~$k$ such that
$m=k^2$.]

\smallskip

\noindent{\bf Proof.} Let $x$ be an odd integer. Then $x=2k+1$ for some
integer~$k$. So
$$(k+1)^2-k^2=(k^2+2k+1)-k^2=2k+1=x.$$
Hence $x$ is the difference of two perfect squares, namely, $(k+1)^2$
and~$k^2$. \qed

\bigskip

\noindent{\bf Solution.} This proposition is equivalent to the statement ``If
$x$ is an odd integer, then $x$ is the difference of two perfect squares.''
Letting $p$ be the statement ''$x$~is an odd integer'' and $q$~be the statement
``$x$~is the difference of two perfect squares'', we see that we are trying to
prove the statement $p\to q$. In the proof, we begin by supposing that $x$ is
an odd integer (that~is, we suppose that $p$ is true), and through logical
reasoning we arrive at the conclusion that $x$ must be the difference of two
perfect squares (that~is, $q$~must be true). Since we began by assuming the
premises of the proposition are true and found that this implied the conclusion
of the proposition is true, this is a {\bf direct proof}.

\bigskip

\noindent\llap{4.\enspace}%
{\bf Proposition.} If ten balls are chosen from a box containing only red
balls, yellow balls, and green balls, then at least four of the chosen balls
are of the same color.

\smallskip

\noindent{\bf Proof.} Suppose that ten balls are chosen from the box and that
no four of the chosen balls are of the same color. Then the chosen balls must
include no more than three balls of any one color. Since there are only three
colors, the number of chosen balls can be no greater than $3\times3=9$. But ten
balls were chosen. Hence at least four of the chosen balls are of the same
color. \qed

\bigskip

\noindent{\bf Solution.} Let $p$ be the statement ``ten balls are chosen from
the box'' and $q$ be the statement ''at least four of the chosen balls are of
the same color''. We are asked to prove $p\to q$.

Notice that in this proof we begin by supposing that ten balls are chosen from
the box (that~is, that $p$ is true) and that no four of the chosen balls are of
the same color (that~is, that $\lnot q$ is true). We then reason logically to
conclude that at most nine balls were chosen from the box (so that $\lnot p$ is
true). This means that we have $p\land\lnot p$, which is a
{\it contradiction\/}. In other words, we began by supposing that the premises
of the proposition are true and that the conclusion is false, and we arrived at
a contradiction. So this is a {\bf proof by contradiction}. This proof shows
that $(p\land\lnot q)\to(p\land\lnot p)$.

This proof could very easily be rewritten to be a proof by contraposition. If
we remove the assumption at the beginning of the proof that ten balls are
chosen from the box, so that our only assumption is that no four of the chosen
balls are of the same color, we can still logically deduce that no more than
nine balls were chosen from the box. In this case, the proof shows that
$\lnot q\to\lnot p$, which is the contrapositive of the original statement.
Many proofs by contradiction can be slightly simplified in a similar way (by
removing unnecessary assumptions) to produce a proof by contraposition. Often
the resulting proof is considered a simpler and more elegant proof than the
original proof by contradiction, but this is just a matter of mathematical
taste and does not affect the validity of the proof.

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

\bye