\documentstyle[12pt,twoside,macpsfig]{article} \input{macros-course} \newenvironment{proposition*}{{\bf Proposition: }\em}{} \newenvironment{Proof}{\proof }{\qed} \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 following oral problems are due in tutorial on Monday, February 7. Some of the problems ask you to ``verify or falisfy'' 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. \medskip \begin{problems} \oproblem Verify or falisify 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 4in {\hrulefill}\cr %\therefore & \hbox{A ham sandwich is better than complete happiness.}\cr \end{array}\] \oproblem Consider the $2\times2$ integer lattice of all points in $\integers\times\integers$. Given any nine points in this lattice, can two of them be selected so that the midpoint of the line between them lies in $\integers\times\integers$? \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 Prove that $\frac{n^7}{7}+\frac{n^3}{3}+\frac{11n}{21}$ is an integer. (\hint Use the polynomial expansion of $(n+1)^7$.) \oproblem Verify or falisfy the following proof that for $x\neq 0$, 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=0$. We shall show that $x^{n+1}=0$. 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 For any integer $n\ge 3$, consider a simple polygon of $n$ vertices drawn in the plane. (A polygon is \defi{simple} if it does not cross itself.) An \defi{$n$-gon} is a polygon with $n$ vertices, A {\em triangulation} of an $n$-gon $P$ is a partition of the interior of $P$ into triangles such that the only vertices of $P$ that lie on the boundary of any triangle in the triangulation are the triangles vertices. \begin{problemparts} \problempart Prove 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 angles of an $n$-gon. Use induction to prove that your formula is correct. \end{problemparts} \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 any constant constant greater than $1$ times~$1$. Assume that the statement is true for $n=k$, that is, that \[\sum_{i=1}^k i \le ck\] for some constant~$c>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 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 all natural numbers. \end{Proof} \oproblem\label{prob:angles} Verify (or find a flaw in) the following proof that there exists an obtuse angle with measure equal to that of a right angle. You may find Figure~\ref{fig:angles} useful. \begin{figure}[t] \centerline{\psfig{figure=figures/fudged.ps,height=2in}} \figcaption{A sketch of the geometric construction in \hbox{Problem~\ref{prob:angles}}.} \label{fig:angles} \end{figure} \begin{proof} Construct a rectangle $abcd$ labeled so that $\overline{ad}$ is a diagonal. Construct $\overline{ae}$ such that $\angle eac$ has small measure. Draw $\overline{ed}$. Construct perpendicular bisectors to $\overline{ed}$ and to $\overline{cd}$. Let $h$ be the intersection of these bisectors. Since the angle $\angle eac$ is small, $h$ will not lie between $\overline{cd}$ and $\overline{ab}$. Construct $\overline{ah}$, $\overline{bh}$, $\overline{eh}$, and $\overline{dh}$. Since the line $\overline{fh}$ is a perpendicular bisect of $\overline{ed}$, $\bigtriangleup ehd$ is 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 the $\bigtriangleup ahb$ is isoceles. Therefore $\overline{ah}$ and $\overline{hb}$ are equal in length and $\angle bah$ is equal in measure to $\angle hba$. With these results, it becomes clear that $\bigtriangleup eah$ and $\bigtriangleup dbh$ are congruent. So $\angle eah$ and $\angle dbh$ have equal measure. Subtracting the (equal) measures of $\angle bah$ and $\angle abh$ respectively yields that the measure of $\angle eab$ equals the measure of $\angle dba$. \end{proof} \oproblem A full binary tree is a binary tree such that any node has either 0 or 2 children. Prove that the number of interior nodes in a full binary tree is one less than the number of leaves. \bigskip The following 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 \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!}$. \begin{problemparts} \problempart Justify the notation by proving that the number of ways to divide $n$ distinct objects into $k$ different sets is ${n \choose k}$. \problempart The binomial coefficients are precisely the numbers appearing in Pascal's triangle. See Figure~\ref{fig:binom}. Prove that ${n \choose k}= {n-1 \choose k-1} + {n-1 \choose k}$ for $n\ge1$ and $0