% 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:}

\medskip

\centerline{CSCE~235 Quiz~1}
\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

\vfill

\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

\vfill

\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

\vfill

\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

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

\bye