\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\input{/pub/www/classes/6.042/fall99/inputs/macros-course}

%\newcommand{\solution}[1]{}
\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}

\newcommand{\kth}{\ensuremath{^\mathit{\textit{\tiny th}}}}

\begin{document}
\psol{3}{October 1, 1999}

\begin{problems}

\problem \textbf{Countable and Uncountable Sets}

{\bf (a)} Do \S 1.7, Exercise 32 (a,b,d) from the Rosen textbook.

\solution{(a) This is countable. The integers in the set are
$\pm 1,\pm 2, \pm 4, \pm 5, \pm 7$, and so on. We can list these
numbers in the order $1, -1, 2, -2, 4, -4, 5, -5, 7, -7,\ldots$, thereby
establishing the desired correspondence. In other words, the correspondence
is given by $1 \leftrightarrow 1, 2 \leftrightarrow -1, 3 \leftrightarrow 2,
4 \leftrightarrow -2, 5 \leftrightarrow 4, 6 \leftrightarrow -4$, and so on.  

%Since $S$ is a subset of a countable set, namely,
%$\naturals$, $S$ is countable.  Here's an explicit bijection $f: S
%\rightarrow N$:
%
%\hspace{6mm}
%if $x > 0, f(x) = 2 ( \abs x - \abs {\lfloor \frac{x}{3} \rfloor})-1 $
%
%\hspace{6mm}
%if $x < 0, f(x) = 2 ( \abs x - \abs {\lfloor \frac{x}{3} \rfloor}) $

(b) This is similar to part (a); we can simply list the elements of the set in
order of increasing absolute value, l;isting each positive term before its
corrsponding negative:\\ 
$5, -5, 10, -10, 15, -15, 20, -20, 25, -25, 30, -30, 
40, -40, 45, -45, 50, -50,\ldots$.

%Let $S$ denote the set of numbers divisible by 5 but not by 7.
%There is a bijection $f: S \rightarrow N$.
%
%\hspace{6mm}
%if $x > 0, f(x) = \frac{ 2 ( \abs x - \abs {\lfloor \frac{x}{7} \rfloor})-1}{5} $
%
%\hspace{6mm}
%if $x < 0, f(x) = \frac{ 2 ( \abs x - \abs {\lfloor
%\frac{x}{7} \rfloor})} {5} $

(d) The set is not countable. We can prove by the same diagonalization 
argument that was used to prove that the set of all reals is uncountable
in Example 17, \S 1.7 of Rosen. All we need to do is choose
$d_i=1$ when $d_{ii}=9$ and choose $d_i=9$ when $d_{ii}=1$ or $d_{ii}=$blank
(if the decimal expansion is finite).}

%Not countable, with a similar argument to that for all the real
%numbers between 0 and 1 in \S 1.7.}
%
{\bf (b)} Show that the set of all functions from $\naturals$ to
$\{0,1\}$ is uncountable.

\iffalse GIVEN IN HANDOUT 16:
Hence, conclude that the set of all subsets 
of $\naturals$ is uncountable.
\fi


\solution{Rework the proof of uncountability of the reals in base 2.
Then, referring to example 17 in \S 1.7, note that we can define the
$i^{\textit{\tiny th}}$ function $f_i$ as $f_i(j)=d_{ij}$, which puts
the functions from $\naturals$ to $\{0,1\}$ in one-to-one correlation
with the real numbers; thus, this set of functions is uncountable.\\
If we take a function $f_i$ to be the characteristic
function of a subset $S_i\subseteq\naturals$ (i.e., $f(x)=1\iff x\in
S$), then the set of subsets of the natural numbers is in one-to-one
correspondence with the set of functions from $\naturals$ to $\{0,1\}$
and is therefore also uncountable.}

{\bf (c)} Show that the set of all finite strings constructed from 0's and 1's
is countable.

\solution{There are a finite number, namely, $2^m$, bit strings of length
$m$. The set of all bit strings is the union of the bit strings of length $m$
over $m=0,1,2,\ldots$. Since the union of a countable number of countable
sets is countable, there are a countable number of bit strings.}

%
%We can consider an integer in big-endian binary format,
%in which case there always exists an integer $i=1b_{n-1}b_{n-2}\cdots
%b_0$ that maps to the bit string bit $1b_{n-1}b_{n-2}\cdots b_0$.
%Clearly, if we can also add the strings $0b_{n-1}b_{n-2}\cdots
%b_0$ for every integer $i$, then we will have covered all bit
%strings.  We can therefore make our map
%\begin{center}
%\begin{tabular}{rcl}
%$1b_{n-1}b_{n-2}\cdots b_{1}1$ & $\mapsto$ &
%$1b_{n-1}b_{n-2}\cdots b_{1}$ \\
%$1b_{n-1}b_{n-2}\cdots b_{1}0$ & $\mapsto$ &
%$0b_{n-1}b_{n-2}\cdots b_{1}$ \\
%\end{tabular}
%\end{center}
%Note that we are excluding $0$ from our domain; if you like, you can
%add $1$ to $x$ before looking at the binary representation.}

\ppart \textbf{Counting}

{\bf (a)} Do \S 4.1, Exercise 20 from the Rosen textbook.

\solution{
\begin{enumerate}
\item[(a)] 1000.
\item[(b)] 4500.
\item[(c)] $9\cdot 9\cdot 8\cdot 7=4536$.  Note that the first digit
doesn't have 10 choices, since it cannot be $0$.
\item[(d)] 3000 are divisible by 3, so it follows that 6000 are not.
\item[(e)] 1800 are divisible by 5 and 1286 are divisible by 7.  There 
are 257 numbers divisible by both 5 and 7 (i.e., divisible by 35).
So, by inclusion/exclusion, the answer is $1800+1286-257=2829$.
\item[(f)] $9000-2829=6171$.
\item[(g)] 1800 divisible by 5 and 257 divisible by both, so
$1800-257=1543$ divisible by 5 but not 7.
\item[(h)] 257, as above.
\end{enumerate}
}

{\bf (b)} Do \S 4.1, Exercise 52 from the Rosen textbook.

\solution{There are $2^n$ lines (assignments) in the truth table for a
formula with $n$ variables, since each of the variables can take on
one of two values.  For a given truth assignment to the $n$ variables,
the proposition can be either true or false; hence, there are
$2^{2^n}$ possibilities.}

\iffalse
\ppart \textbf{Induction and Counting}

Do \S 4.1, Exercise 54 from the Rosen textbook.

\solution{We want to show that a procedure consisting of $M$ tasks
can be done in $n_1n_2\cdots n_M$ ways if the $i\kth$ task can be done
in $n_i$ ways.  The product rule stated in the text is the base case,
$M=2$.  Assume the induction hypothesis for $M=m$ and prove it for
$M=m+1$.  Then, to do the procedure we have to do each of the first
$m$ tasks, which by the IH can be done in $n_1n_2\cdots n_m$ ways, and
then do the $(m+1)\kth$ task, so there are $(n_1n_2\cdots n_m)n_{m+1}$
ways.}
\fi

\ppart \textbf{Pigeonhole Principle}

{\bf (a)} Do \S 4.2, Exercise 10 from the Rosen textbook.

\solution{The midpoint of the segment whose endpoints are $(a,b)$ and
$(c,d)$ is $\left(\frac{a+c}{2},\frac{b+d}{2}\right)$.  Clearly the
coordinates of these fractions will be integers as well if and only if
$a$ and $c$ share parity (both odd or even) and $b$ and $d$ also share
parity.  Thus, there are four possible pairs of parities: (odd,odd),
(odd,even), (even,odd), (even,even).  Since we are given five points,
the pigeonhole principle guarantees that at least two of them will
have the same pair of parities; therefore, the midpoint of the line
segment joining those two points will have integral coordinates.}

{\bf (b)} Do \S 4.2, Exercise 30 from the Rosen textbook.

\solution{At a party with $n$ people, there are $n$ possibilities
for the number of ``other people'' a person can know ($0$ through
$n-1$), so we cannot apply the pigeonhole principle directly; however,
note that there cannot exist a party in which some person (say, Lars)
knows no one and another (say, Kirk) knows all $n-1$ other people,
because ``know'' is a symmetric relation: if Kirk knows Lars, then
Lars knows Kirk, contradicting the assumption that Lars knows no one.
Thus, there are in reality only $n-1$ possiblities, whereupon we can
apply the pigeonhole principle.}

{\bf (c)} Do \S 4 Supplementary Exercises, Exercise 10 from the Rosen textbook.

\solution{Using the generalised pigeonhole principle, we see that we
need $5\times 12+1 = 61$ people.}

{\bf (d)} Do \S 4 Supplementary Exercises, Exercise 16 from the Rosen textbook.

\solution{Partition the set of numbers from $1$ to $2n$ into the $n$
pigeonholes $\{1,2\},\{3,4\},\ldots,\{2n-1,2n\}$. If we have $n+1$ numbers
from this set (the pigeons), then two of them must be in the same hole.
This means that among our collection are two consecutive numbers. Clearly
consecutive numbers are relatively prime (since every common divisor must
divide their difference, 1).}

\ppart \textbf{Inclusion-Exclusion Principle}

\noindent

There are 49 students in a class at MIT who either understand mathematical 
equations, exercise regularly, or love school. Of these:

\noindent
20 students understand mathematical equations.

\noindent
20 students exercise regularly.

\noindent
26 students love school.

\noindent
36 students understand mathematical equations or exercise regularly.

\noindent
38 students understand mathematical equations or love school.

\noindent
40 students exercise regularly or love school.

\vspace{1mm}

\noindent
How many students understand mathematical equations AND exercise
regularly AND love school?

\solution{
Let $A$ denote the set of students who understand mathematical
equations, $B$ denote the set of students who exercise
regularly, and $C$ denote the set of students who love school.
Then we are given that $ | A\cup B\cup C | = 49$, 
$| A |=20$, $| B |=20$, $| C |=26$, 
$| A\cup B |=36$, $| A\cup C |=38$, and $| B\cup C |=40$.
\begin{eqnarray*}
| A\cap B\cap C | & = & 
      | A\cap B | +| C | - | (A\cap B)\cup C |\\
& = & | A | + | B | - | A\cup B | + | C | 
      - | (A\cup C) \cap (B\cup C) |\\
& = & | A | + | B | - | A\cup B | + | C | 
      - | (A\cup C) | - | (B\cup C) | + | (A\cup B \cup C) |\\
& = & 20 + 20 - 36 + 26 - 38 - 40 + 49\\
& = & 1
\end{eqnarray*}
In line 1 we apply inclusion-exclusion, in line 2 we apply inclusion-exclusion
and distributive laws, and in line 3 we apply inclusion-exclusion.
}

\problem  \textbf{Defining Bijections}  %F97 H19-Pset7

Let $F$ be the set of all functions $f: \reals \rightarrow
\{0,1\}$.  Show that there is a bijection from P(${\reals}$) to $F$.

\solution{
Let $\phi\colon P(\reals)\to F$ be the function mapping any set 
$A\subseteq \reals$ to the function $\phi_A$ defined as follows:
\[\phi_A(x)=\left\{\begin{array}{ll}
 1 & \mbox{if $x\in A$} \\
 0 & \mbox{otherwise}
 \end{array}\right.\]
We prove that $\phi$ is a bijection, i.e., 
it is injective and surjective.
\begin{itemize}
 \item Injective: Let $A$ and $B$ be two subsets of $\reals$
  such that $A\neq B$. $A$ and $B$ cannot be both empty, so
  assume without loss of generality 
  that there exists some $x$ such that $x\in A$ but $x\not\in B$.
  We have $\phi_A(x)=1\neq 0 = \phi_B(x)$. Therefore 
  $\phi_A\neq \phi_B$ and $\phi$ is injective.
 \item Surjective: Let $f$ be a function from $\reals$
  to $\{0,1\}$. We want to show that $f=\phi_A$ for some $A$.
  Define the set $A=\{x\in \reals \mid f(x)=1\}$.
  We have $\phi_A(x) = f(x)$ for all $x\in \reals$.
  Therefore $\phi_A = f$ and $\phi$ is surjective.
\end{itemize}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \textbf{Countability}  %F97 H19-Pset7

A real number is {\em algebraic} if it is the root of a
polynomial with rational number coefficients.  Algebraic numbers form
an important part in the study of (what else) modern algebra.  A
number that is not algebraic is called {\em transcendental}.

\bparts

\ppart Prove that for any particular $d$, the set of degree $d$
polynomials with rational coefficients is countable.

\solution{
Let $P_d$ be the set of degree $d$ polynomials with rational 
coefficients.
The function 
\[f\colon (q_0,q_1,\ldots, q_d)\mapsto q_0x^d+q_1x^{d-1}+\cdots+q_d\]
is a surjection from $(\rationals - \{0\}) \times \rationals^d$ 
to $P_d$.
Since the set $(\rationals - \{0\}) \times \rationals^d$ is countable 
(the Cartesian product of finitely many countable sets is countable),
then also the set $P_d$ is countable.}

\ppart Prove that the set of all roots of degree $d$ polynomials with
rational coefficients is countable (you may use the fact that a degree
$d$ polynomial has at most $d$ roots).

\solution{
Since each degree $d$ polynomial has at most $d$ roots we can give a 
surjection from $P_d\times\{1,\ldots, d\}$ to the set of all 
roots of degree $d$ polynomials with rational coefficients.
For example we can define $f(p(x),i) = x_i$,
where $x_1,\ldots, x_d$ are the roots of $p(x)$
(if $p(x)$ has less then $d$ roots, just repeat the last 
one many times).}

\ppart Prove that the set of algebraic numbers (which is just the
union of the sets in the previous part) is countable.

\solution{
The set of algebraic numbers is the union of the sets 
of the roots of polynomials with rational coefficients
of degree $d$, for all $d$.
This is a countable union of countable sets,
which we know it is countable.
}

\ppart Conclude that there is a transcendental number.

\solution{
If there were no transcendental numbers, all numbers would be 
algebraic, i.e., the set of algebraic numbers equals $\reals$.
But this is not possible because the reals are not countable.
}

\eparts

\end{problems}

\end{document}
