\documentstyle[12pt,twoside,macpsfig]{article}
\input{macros-course}

\begin{document}

\handout{ps1}{Problem Set 1}{February 1, 1994}
\pset{1}
{\bf Reading:\ }Maurer \& Ralston: Section 0.7, Chapter 2, Sections 7.1--3,
and Sections 7.5-7.6.

\medskip

The problems are divided into oral problems (prefix~``{\bf O}'') and
written problems (prefix~``{\bf W}'').

The oral problems are due in tutorial on Monday, February 7.  Some of
the problems ask you to ``verify or falsify'' a proof.  For these
problems, you must either justify the correctness of each step of the
proof, or else locate and explain the error.  It is not sufficient to
merely show that an incorrect proof is indeed wrong.  You must explain
where the bug is.

The written problems are due at the beginning of class on Tuesday,
February 8.  Remember to write up each problem on a separate page or
pages, with your name on each sheet.  Read
Handout~\ref{course-information} for the policy on problem sets.

\medskip


\medskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem Verify or falsify the following proof that if $a$ and $b$
are two equal real numbers, then $a=0$.
\begin{Proof}
\begin{eqnarray*}
a&=&b \\
a^2&=&ab \\
a^2-b^2&=&ab-b^2 \\
(a-b)(a+b)&=&(a-b)b \\
a+b&=&b \\
a&=&0 
\end{eqnarray*}
\end{Proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \oproblem
% Verify or falsify the following syllogism.
% \[
% \begin{array}{ll}
% &\hbox{Nothing is better than complete happiness.}\cr
% &\hbox{A ham sandwich is better than nothing.}\cr
% &\hbox to 3.8in {\hrulefill}\cr
% %\therefore
%  & 
% \hbox{A ham sandwich is better than complete happiness.}\cr
% \end{array}\]
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\oproblem Verify or falsify the following proof that there exist two
irrational numbers $a$ and $b$ such that $a^b$ is rational.
\begin{Proof}
Recall that $\sqrt{2}$ is irrational.  Suppose that
$\paren{\sqrt{2}}^{\sqrt{2}}$ is rational.  Then, let $a=\sqrt{2}$,
let $b=\sqrt{2}$, and the proof is finished.  Suppose, however, that
$\paren{\sqrt{2}}^{\sqrt{2}}$ is irrational.  Then, let
$a=\paren{\sqrt{2}}^{\sqrt{2}}$ and let $b=\sqrt{2}$.  Thus, we have
$a^b=\paren{\sqrt{2}^{\sqrt{2}}}^{\sqrt{2}}=
\paren{\sqrt{2}}^{\sqrt{2}\cdot\sqrt{2}} = \paren{\sqrt{2}}^2 = 2$,
which is rational, and we're done.
\end{Proof}

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

\oproblem Verify or falsify the following proof that for
all real $x\neq 0$, and all natural numbers $n$, we
have $x^n=1$.
\begin{Proof}
We use induction on~$n$.  For the base step, observe that if $x \neq
0$, we have $x^0 = 1$.  We now assume that for all $k\leq n$, we have $x^k=1$.
We shall show that $x^{n+1}=1$.  By the induction hypothesis, we have
$x^n = x^{n-1} = 1$.  Hence, it follows that 
\begin{eqnarray*}
x^{n+1} & = & \frac{x^nx^n}{x^{n-1}}\\
& = &\frac{1\times 1}{1}\\
& = & 1\ . 
\end{eqnarray*}
\end{Proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem Verify or falsify the following proof that $\sum_{i=1}^n i$
is less than or equal to some positive constant times~$n$.
\begin{Proof}
The proof is by induction on $n$. 

If $n=1$, then the summation evaluates to $1$, which can be bounded
above by $c$ times~$1$, where $c$ is any constant greater than or
equal to~$1$.

Assume that the statement is true for $n=k$, that is, that
\[\sum_{i=1}^k i \le ck\] for some constant~$c\geq 1$.  Adding $k+1$ to both 
sides, we obtain
\begin{eqnarray*}
\sum_{i=1}^{k+1} i & \le & ck + (k+1)\\
& \le & (c+1)(k+1)\ .
\end{eqnarray*}
Since $c$ is a constant greater than or equal to 1, so is~$c+1$.  For
$n=k+1$, therefore, the sum $\sum_{i=1}^{n} i$ is also bounded above
by a constant times~$n$.  Consequently, by induction this property
holds for every natural number $n\geq 1$.
\end{Proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem\label{prob:angles} Verify or falsify the following proof
that there exists an obtuse angle with measure equal to that of a
right angle.  

\begin{figure}[t]
\centerline{\psfig{figure=figures/fudged.ps,height=2in}}
\figcaption{A sketch of the geometric construction in
    \hbox{\ref{prob:angles}}.}
\label{fig:angles}
\end{figure}

\begin{Proof}
Construct a rectangle $abcd$ as shown in Figure~\ref{fig:angles}.
Construct $\overline{ae}$ such that $\overline{ae}$ is the same length
as $\overline{ac}$ and such that $\angle eac$ has small measure.  Draw
$\overline{ed}$.  Now, construct perpendicular bisectors to
$\overline{ed}$ and to $\overline{cd}$, and let $h$ be their point of
intersection.  Construct $\overline{ah}$, $\overline{bh}$,
$\overline{eh}$, and $\overline{dh}$.

Since the line $\overline{fh}$ is a perpendicular bisector of
$\overline{ed}$, the triangle $\bigtriangleup ehd$ must be isoceles,
and hence the lengths of $\overline{eh}$ and $\overline{hd}$ are
equal.  Similarly, since $abcd$ is a rectangle, $\overline{gh}$ is a
perpendicular bisector of $\overline{ab}$, so $\bigtriangleup ahb$ is
isoceles.  Therefore, $\overline{ah}$ and $\overline{hb}$ are equal in
length, and $\angle bah$ is equal in measure to $\angle hba$.

Since the corresponding sides of $\bigtriangleup eah$ and
$\bigtriangleup dbh$ have the same lengths, it follows that the two
triangles are congruent.  Consequently, $\angle eah$ and $\angle dbh$
have equal measure.  Subtracting the (equal) measures of $\angle bah$
and $\angle abh$, respectively, we find that the measure of $\angle
eab$ equals the measure of $\angle dba$.  Thus, an obtuse angle has
the same measure as a right angle.
\end{Proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem Consider the three-dimensional integer lattice of all points
in $\integers\times\integers\times\integers$.  Show that for any nine
points in this lattice, there exist two points of the nine such that
the midpoint of the straight line connecting them is also a lattice
point.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem Prove that for any natural number $n$,
\[\frac{n^7}{7}+\frac{n^3}{3}+\frac{11n}{21}\] is
an integer.  (\hint Use the polynomial expansion of $(n+1)^7$.)


\oproblem You are given an unlimited supply of 4-cent stamps and
7-cent stamps.  Obviously, with these two denominations, you cannot
make certain amounts of postage, such as 10 cents.  Prove,
nevertheless, that for some $n_0>0$, every amount $n$ of postage such
that $n\geq n_0$ can be made up from 4- and 7-cent stamps.  What is
the minimum value for $n_0$ such that this theorem holds?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem For any integer $n\ge 3$, consider a simple, not
necessarily convex, polygon of $n$
vertices drawn in the plane.  (A polygon is \defi{simple} if it does
not cross itself.)  An \defi{\boldmath $n$-gon} is a polygon with $n$
vertices.  A \defi{triangulation} of an $n$-gon $P$ is a partition of
the interior of $P$ into triangles such that the vertices of any such
triangle are vertices of $P$.

\begin{problemparts}

\problempart Use induction to show that any triangulation of an
$n$-gon is comprised of exactly $n-2$ triangles.

\problempart Using the fact the sum of the interior angles of a
triangle is $\pi$, give a formula for the sum of the interior angles
of an $n$-gon.  Prove that your formula is correct.

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \oproblem A full binary tree is a binary tree such that any node has
% either 0 or 2 children.  Prove that the number of internal nodes in a
% full binary tree is one less than the number of leaves.

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


\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\wproblem Recall that the binomial coefficients ${ n \choose k }$
(``read $n$ choose $k$'') are defined on the natural numbers by \[{n
\choose k}={n! \over (n-k)!\; k!}\ .\] The binomial coefficients are
precisely the numbers appearing in Pascal's triangle, which is shown
in Figure~\ref{fig:binom}.  In each row of Pascal's triangle, the
first and last entries are~$1$.  Any other entry is the sum of the two
entries above it.


\begin{figure}[h]
\centerline{\psfig{figure=figures/Pascal-triangle.ps,height=2in}}
\figcaption{The first eight rows of Pascal's triangle.}
\label{fig:binom}
\end{figure}

\begin{problemparts}

\problempart Justify the reading of the notation ${n \choose k}$
by using induction to prove that ${n \choose k}$ is
the number of ways to choose $k$ objects from a set of
$n$ distinct objects.

\problempart Prove that \[{n \choose k}= {n-1 \choose k-1} + {n-1
\choose k}\] for $n\ge1$ and $0<k<n$.  Argue that the $k$th entry in
row $n$ of Pascal's triangle is ${n \choose k}$, if rows and entries
are labeled suitably.

\problempart Prove that each row of Pascal's triangle increases until
the middle and then decreases.

\problempart Give an inductive proof that \[(x+y)^n=\sum_{k=0}^n {n
\choose k} x^k y^{n-k}\ .\] Use this fact to show that the sum of the
entries in the $n$th row of Pascal's triangle is $2^n$.  Similarly,
prove that the sum of the even-numbered entries minus the sum of the
odd-numbered entries is 0 in any but the top row of Pascal's triangle.

% \problempart Although the diagonals of Pascal's triangle are infinite,
% one can take partial sums along them.  The partial sum of the first
% $n$ entries of the $m$th diagonal is ${n+m \choose m+1}$. State
% this formally and prove it.  \note{Needs clarification.}

\problempart Consider taking the sum of all numbers in the
``off-diagonals'' of Pascal's triangle as shown in
Figure~\ref{fig:pascal-fib}.  What sequence do they form?  State your
answer formally, and prove it.


\begin{figure}[t]
\centerline{\psfig{figure=figures/Pascal-fib.ps,height=2in}}
\figcaption{The ``off-diagonals'' of Pascal's triangle.}
\label{fig:pascal-fib}
\end{figure}


\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\wproblem

Consider a simple polygon drawn with vertices on the integer
$\integers\times\integers$ lattices, as is shown in
Figure~\ref{fig:picks}.  Let $I$ be the total number of lattice points
in the interior of the polygon, and let $B$ be the total number of
lattice points on the boundary.  Prove that the area $A$ of the
polygon is $A = I + B/2 - 1$.  (\hint The proof will take you several
steps.)

\begin{figure}[h]
\centerline{\psfig{figure=figures/picks.ps,height=2in}}
\figcaption{A simple polygon in the lattice $\integers\times\integers$,
with 15 lattice points in its interior, 10 lattice points on its
boundary and area 19.}
\label{fig:picks}
\end{figure}



\end{problems}


\end{document}


