Index: kdmc.tex =================================================================== RCS file: /a/class/6.042/spring00/repository/final/kdmc.tex,v retrieving revision 1.6 diff -r1.6 kdmc.tex 1,107d0 < %% Note to Reader: The questions in this file are divided into 2 parts: < %% problems that are `READY FOR SUBMISSION' or `STILL IN PROGRESS'. You can < %% grep for the terms in quotes to find the beginning of each section. < < %% I would want to modify each of these problems and reduce the set size < %% by choosing the best ones. < < %% done? < %% * RECURSIVE DEFINITIONS %% < %% * STRUCTURAL INDUCTION %% < %% * WELL-ORDERING %% < %% RELATIONS/POSETS/EQUIVALENCE RELATIONS %% < %% GRAPHS %% < %% STARS AND BARS %% < %% COMBINATIONS WITH REPITION %% < %% BINOMIAL COEFFICIENTS %% < %% INFINITY %% < < < \documentclass[11pt, twoside]{article} < < \usepackage{graphics} < \usepackage{psfig} < < \input{macros-course} < < %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% < % Printing the page layout parameters < < \printlayout < < \askaboutsolutions < < %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% < < < \ifshowsolutions < \newcommand{\reading}[1]{} < % < \newcommand{\handoutlabel}{sol10} < \newcommand{\handouttitle}{Ken Sol} < \newcommand{\handoutdate}{\today} < \newcommand{\collaboration}{} < \newcommand{\titlebar}{\handout{\handoutlabel}{\handouttitle}{\handoutdate}} < % < \else < \newcommand{\reading}[1]{% < % \mbox{}\\ % < \hrule\mbox{} \\ %\bigskip % < #1% < % \mbox{} \\ %\bigskip % < \hrule % < %\vfill\mbox{}\newpage% < } < % < \newcommand{\handoutlabel}{ps10} < \newcommand{\handouttitle}{Ken} < \newcommand{\handoutdate}{\today} < \newcommand{\duedate}{May 2, 2000} < \newcommand{\collaboration}{\collaborationnote} < \newcommand{\titlebar}{% < \handout{\handoutlabel}{\handouttitle}{\handoutdate} < \centerline{{\bf Due Date: \duedate.}} < \vspace*{\baselineskip}} < % < \fi < < < \renewcommand{\solution}[1]{% < \ifshowsolutions % < \medskip < \textbf{Solution.} \par % < #1 < % \mbox{} \\ < % \mbox{}\hrulefill\hspace*{1ex}\ignorespaces% < % \raisebox{-0.25\baselineskip}{$\square$}% < % \hspace*{1ex}\ignorespaces\hrulefill% < % \nopagebreak% < \fi} < < < %\newcommand{\solutionname}{Solution} < %\renewenvironment{solution}[1][\solutionname]{% < % \par < % \normalfont < % \topsep6\p@\@plus6\p@ \trivlist < % \item[\hskip\labelsep\bfseries < % #1\@addpunct{.}]~~\ignorespaces < %}{% < %\mbox{} \\ < %\mbox{}\hrulefill\hspace*{1ex}\ignorespaces% < %\raisebox{-0.25\baselineskip}{$\square$}% < %\hspace*{1ex}\ignorespaces\hrulefill% < %\nopagebreak% < %} < < %\renewcommand{\solution}[1]{% < % %\begin{solution} < % #1 < % %\end{solution} < % } < < %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% < < < \begin{document} < 136c29 < \problem --- > \kproblem 144c37 < \problempart --- > \ppart 147a41 > $\forall $ 150c44 < \problempart --- > \ppart 158c52 < \problempart --- > \ppart 164c58 < \problempart --- > \ppart 173,178c67,69 < $\forall x \in \naturals \forall y \in \naturals xWy \land yWx iff x \in B \land y \in B$. < Let us define sets $M_i = \{ x | x \in \naturals \land x \text{mod} 4 = i\} \forall i \in \{0, 1, 2, 3\}$. < Then we have that $(a_0, 1) \in W iff a_0 \in M_0$. Similarly < $(a_1, 2) \in W iff a_1 \in M_1$, $(a_2, 4) \in W iff a_2 \in M_2$, and < $(a_3, 8) \in W iff a \in M_3$. < {\bf need to finish.} --- > $\forall x \in \naturals \forall y \in \naturals xWy \land yWx iff x \in B \land y \in B$. But there is no such $(x, y)$ pair in $W$. The statement > $\forall x \in \naturals \forall y \in \naturals \not (xWy \land yWx)$, so the > requirement for antisymmetry is vacuously true. 179a71,78 > \problempart > Find $R \composition S$. > \newline > \solution{ > Let us define the set $M_i \subseteq \naturals$ as $\{x | x mod 4 = i\}$. > Then, clearly there are 4 such sets, namely $M_0$, $M_1$, $M_2$, and $M_3$. > Let $(x, y) \in Z = R \composition S iff (x = 0 \land y \in M_1) \or (x = 1 \land y \in M_2) \or \[(x = 2 \or x = 3) \land y \in M_0\]$ > } 287c186 < \problempart Prove by strong induction that these and no other --- > \ppart Prove by strong induction that these and no other 334c233 < \problempart Prove the same thing by well ordering --- > \ppart Prove the same thing by well ordering 446c345 < \problempart --- > \ppart 465c364 < \problempart CLAIM: $\sqrt{2}$ is rational. --- > \ppart CLAIM: $\sqrt{2}$ is rational. 480c379 < \problempart CLAIM: every number can be described in a phrase of less --- > \ppart CLAIM: every number can be described in a phrase of less 510c409 < \problempart Prove that $R$ is a total order. --- > \ppart Prove that $R$ is a total order. 518,519c417,418 < so that $b_1\ldots b_t \not < a_1\ldots a_t$ and hence again < $b_1\ldots b_n\not < a_1\ldots a_m$. Finally for transitivity, suppose that --- > so that $b_1\ldots b_t \not a_1\ldots a_t$ and hence again > $b_1\ldots b_n\not a_1\ldots a_m$. Finally for transitivity, suppose that 538c437 < \problempart Prove that neither $R$ nor $R^{-1}$ is a well-ordering. --- > \ppart Prove that neither $R$ nor $R^{-1}$ is a well-ordering. 572c471 < \problempart --- > \ppart 574c473 < \problempart --- > \ppart 576c475 < \problempart --- > \ppart 795c694 < \problempart Every symmetric, weakly transitive relation is transitive. --- > \ppart Every symmetric, weakly transitive relation is transitive. 805c704 < \problempart Every reflexive, symmetric, weakly transitive relation --- > \ppart Every reflexive, symmetric, weakly transitive relation 823c722 < <<<<<<< kdmc.tex --- > <<<<< \ppart 838c737 < \problempart --- > \ppart 840c739 < \problempart --- > \ppart 842c741 < \problempart --- > \ppart 883c782 < \problempart Draw a 4-cube. --- > \ppart Draw a 4-cube. 891c790 < \problempart In your drawing, highlight a Hamiltonian circuit. --- > \ppart In your drawing, highlight a Hamiltonian circuit. 898c797 < \problempart Use induction on $n$ to prove that an $n$-cube has a --- > \ppart Use induction on $n$ to prove that an $n$-cube has a 1093,1113d991 < < %%%%%%%%%% PROBLEM %%%%%%%%% < % Source: < % Topic: < < %%%%%%%%%% PROBLEM %%%%%%%%% < % Source: < % Topic: < < %%%%%%%%%% PROBLEM %%%%%%%%% < % Source: < % Topic: < < %%%%%%%%%% PROBLEM %%%%%%%%% < % Source: < % Topic: < < %%%%%%%%%% PROBLEM %%%%%%%%% < % Source: < % Topic: <