\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. \medskip \begin{problems} \oproblem The following argument purports to prove that if $a$ and $b$ are two equal real numbers, then $a=0$. Is the proof correct? If you claim the proof to be incorrect, then you should be prepared to show precisely where the argument goes astray. If, on the other hand, you agree with the proof, you should be prepared to justify it in tutorial. \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 Is the following syllogism valid? \[ \begin{array}{ll} &\hbox{Nothing is better than complete happiness.}\cr &\hbox{A ham sandwich is better than nothing.}\cr &\hbox to 3in {\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) this argument that here exist two irrational numbers, $a$ and $b$, such that $a^b$ is rational. \begin{Proof} Recall that $\sqrt{2}$ is irrational. Suppose $\sqrt{2}^{\sqrt{2}}$ is rational, then let $a=\sqrt{2}$ and $b=\sqrt{2}$ and the proof is finished. However, suppose $\sqrt{2}^{\sqrt{2}}$ is irrational. Then let $a=\sqrt{2}^{\sqrt{2}}$ and let $b=\sqrt{2}$. Thus $a^b=\left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}}=2$. \end{Proof} \oproblem Prove that $\frac{n^7}{7}+\frac{n^3}{3}+\frac{11n}{21}$ is an integer. Hint: $(n+1)^7=$. \oproblem Find the flaw in the following proof: Proposition. $\forall x \not= 0, x^n = 1.$ \proof Basis step. Since $x \not= 0$, $x^0 = 1$.\\ Induction step.\\ Induction hypothesis: $\forall 0 \leq m \leq k, x^m = 1.$\\ To show: $x^{k+1} = 1.$\\ By the induction hypothesis $x^k = x^{k-1} = 1.$ Hence \[x^{k+1} = \frac{x^kx^k}{x^{k-1}} = \frac{1\times 1}{1} = 1 \qed\] \oproblem For any integer $n\ge3$, an {\em $n$-gon} (not necessarily convex) is defined to be an $n-sided$ figure in the plane with $n$ vertices $v_1,v_2,\ldots,v_n$. The sides are required to be connected. That is, for any two vertices $v_i$ and $v_j$ there must be a path between them which lies solely along the sides of the figure. A {\em triangulation} of an $n$-gon $\cal N$ is a collection $\cal C$ of 3-element subsets of $v_1,\ldots,v_n$. Each such 3-set must define a triangle lying inside $\cal N$. The union of all triangles in $\cal C$ must equal $\cal N$. Finally, any two triangles in $\cal C$ may intersect (if at all) only in an edge or a point. \begin{problemparts} \problempart Prove that any triangulation of an $n$-gon is comprised of exactly $n-2$ triangles. \problempart Generalize the fact the sum of the angles of a triangle is $\pi$, to a formula for the sum of the angles of an $n$-gon. \end{problemparts} \oproblem Verify (or falsify) the claim that $\sum_{i=1}^n i$ is less than or equal to some constant times $n$. \begin{Proof} The proof is by induction on $n$. If $n=1$ then the formula evaluates to $1$ which can be bounded above by a constant times $1$. Assume the theorem for some $n=k$, in other words, $\sum_{i=1}^k i \le ck$ for some constant $c$. Thus \[ \sum_{i=1}^{k+1} i \le ck + (k+1) \le (c+1)(k+1)\quad . \] But $c+1$ is still a constant, so for $n=k+1$, $\sum_{i=1}^{n} i$ is also bounded above by a constant times $n$. \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} \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 }$ are defined by (pick a defn (factorials, pascal's triang., binom thm). If $0\le j < k \le \floor{n/2}$, then ${n\choose j}<{n\choose k}$. Prove this. \wproblem Consider the set $\cal C$ of ordered triples $(r,S,A)$ where $r$ in a positive integer, $S$ is a set of ordered pairs of elements of $A$, and $A=\bigcup_{(s_1,s_2)\in S} \{s_1,s_2\}$. If we picture the elements of $A$ as labels for points, and the set $S$ as describing arrows between points, we could draw $(6,\{(6,4),(6,7),(7,8),(7,3)\})$ as in %% insert figure!!. We define a subset, the {\em finite rooted binary trees}, of $\cal C$ as follows. $(r,\emptyset)$ is a finite rooted binary tree. Let $(r,S,A)$ be a finite rooted binary tree, and $v$ a positive integer not in $A$. Then $(v,S\cup\{(v,r)\})$ is a finite rooted binary tree. Let $(r,S,A)$ and $(t,U,B)$ be finite rooted binary trees, and $v$ a positive integer not in $A\cup B$. If $A\cap B = \emptyset$, then $(v,S\cup U\cup\{(v,r),(v,t)\})$ is a finite rooted binary tree. Prove that a finite rooted binary tree $(r,S,A)$ has no cycles. Namely, there is no sequence $(v_0,v_1),(v_1,v_2),(v_2,v_3),\ldots,(v_{n-1},v_n),(v_n,v_0)$ such that $(v_n.v_0)\in S$ and for all $0\le i l_k\}$. Caveat: (if this doesn't make sense, you're not in danger) You may recognize the above to be a proof that the sign of a permutation is well defined. Thus, if your proof uses determinants, you must define the determinant of a matrix without using signs of permutations. \wproblem We can try to define the greatest common denominator function on two positive integers as follows. \[ {\rm gcd}(r,s) = \left\{ \begin{array}{ll} s&\mbox{if $r=0$}\cr {\rm gcd}({\rm min}(r,s),{\rm max}(r,s)-{\rm min}(r,s))&\mbox{otherwise} \end{array} \right. \] Does the following argument prove that the function ${\rm gcd}()$ actually computes (defines) the greatest common denominatro of two positive integers? We wish to calculate the greatest common denominator of $r$ and $s$. If $r=0$ then ${\rm gcd}()$ returns the right value. Otherwise, we take the positive difference of the two numbers and the minimum of the two numbers and compute their greatest common denominator. Certainly anything that divided both numbers divides both the smaller one and the difference. Further, anything that divides both the smaller and the difference also divides the sum of these two, which is the larger of the numbers we started with. So by induction the function returns the correct answer. \wproblem Let $abc$ and $a' b' c'$ be two triangles in three-space perspective from a point $v$. That is the lines $a a'$, $b b'$, and $c c'$ all meet at $v$. Further, suppose there is a point $C$ where the lines $a b$ and $a' b'$ meet; there is a point $B$ where $a c$ and $a' c'$ meet, and there is a point $A$ where $b c$ and $b' c'$ meet. This situation is diagrammed in Figure (insert figure!). Verify (or find a flaw in) the following proof that $A$, $B$, and $C$ all lie on the same line. \proof The $\bigtriangleup abc$ lies in a unique plane $P$. Similarly the $\bigtriangleup a' b' c'$ lies in a unique plane $Q$. The point $A$ lies in the plane of each triangle, and likewise so do $B$ and $C$. Thus $A$, $B$, and $C$ all lie in $P\cap Q$ which (since it is the intersection of two planes in three space) must be a line. \qed \end{problems} \end{document}