\documentclass[12pt,twoside]{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\graphicspath{{../problemRepository/figs/}}
\usepackage{amsmath}
\usepackage{psfig}  
\input{../handouts/macros-course}
\newcommand{\cross}{\times}
\newcommand{\eqdef}{\mathbin{::=}}



%\def\cent{{\not\!\mathrm{c}}}
\renewcommand{\implies}{\longrightarrow}
\renewcommand{\labelenumi}{\arabic{enumi})}  
\setlength{\itemsep}{0cm}

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

\begin{document}
\handout{tut9}{Mini-Quiz 9}{April 13, 2001}
\begin{enumerate}
\item Your name:
\item What is the date and time of Spring 2001 6.042 Quiz 2?
\end{enumerate}
\newpage
\thispagestyle{empty}
\mbox{}
\setcounter{page}{0}
\newpage
\handout{tut9}{Tutorial 9 Problems}{April 13, 2001}
\begin{problems}

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

\problem 
\bparts
\ppart How many increasing sequences are there of $k$ numbers from the range
$(1 \dots n)$?

\solution{
Since every subset of the range gives a unique increasing sequence, the problem
is equivalent to simply selecting $k$ numbers from $n$: $\binom{n}{k}$.
} 

\ppart How many increasing subsequences of any length are there that take
numbers from $(1 \dots n)$? 

\solution{
Using our solution to the previous part, this is the sum of all binomial
coefficients for $n$:
\[\sum_{k=0}^n \binom{n}{k} = 2^n.\]
}

\eparts

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

\problem % source: Knuth, Concrete Mathematics, Chapter 7.

How many ways are there to completely cover a $2 \cross n$ rectangle with 
(indistinguishable) $2 \cross 1$ dominoes? 

\solution{
Let $T(n)$ be the number of tilings for a $2 \cross n$ rectangle.  Clearly,
$T(0) = T(1) = 1$ .  There are two possibilities for tiling the left edge of
the rectangle --- we put either a vertical domino or two horizontal dominoes
there.  If we choose a vertical one, the remaining $2 \cross (n-1)$ rectangle
can be covered in $T(n-1)$ ways.  If we choose two horizontals, the rectangle
can be completed in $T(n-2)$ ways.  Thus, $T(n) = T(n-1) + T(n-2)$.  This is
just the Fibonacci sequence shifted up one place:
\[T(n) = F_{n+1}\ \mathrm{for}\ n \geq 0.\]
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem %\emph{Stars and Bars.}  S99 Q2
The \emph{king positioning} in an arrangement of a deck of 52 playing
cards is the sequence of numerical positions in the deck, from one to 52,
of the four successive kings.  For example, the king positioning
$(1,2,3,4)$ means all the kings come at the beginning of the deck.  The
king positioning $(1,18,35,52)$ describes the situation in which the kings
are spaced uniformly---with exactly 16 cards between successive kings.

Your answer to each of the following questions may be an arithmetic
expression involving factorials and/or multinomial coefficients.

\bparts
\ppart How many king positionings are there?

\solution{$\binom{52}{4}$.}


\ppart How many king positionings are there in which \emph{no two kings
are adjacent}?

\solution{
Think of kings as bars and the remaining 48 cards as stars.
Place one star between each two adjacent kings (bars).  This requires
three stars and leaves 45 stars that can be placed anywhere; there are
$\binom{45+4}{4}$ ways to do this.}


\ppart Of the $52!$ possible arrangements of the deck, how many have no
two kings adjacent?

\solution{
Now in each of the previous patterns of stars and bars, the kings can be
permuted in $4!$ ways and the remaining cards can be permuted in $48!$
ways, so the total number of desired arrangements is
\[\binom{45+4}{4} 48!\, 4! = 49!\, 48!/45! = 48!\, P(49,4).\]

\iffalse
The form of the RHS suggests that there is another way to do this count,
but I haven't had time to figure what it is.
\fi

}

\eparts

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

\problem % source: Knuth, Concrete Mathematics, Chapter 7.

We will use generating functions to determine how many ways there are to use
pennies, nickels, dimes, quarters, and half-dollars to give $n$ cents change.

\bparts
\ppart Write the sequence $P_n$ for the number of ways to use only pennies to
change $n$ cents.  Write the generating function for that sequence.

\solution{
Since there is only one way to change any given amount with only pennies the 
sequence is $P_n = <1, 1, 1, 1, \ldots>$.  The generating function for the 
sequence is $P = 1 + x + x^2 + x^3 + \ldots = \frac{1}{1-x}$.
}

\ppart Write the sequence $N_n$ for the number of ways to use only nickels to
change $n$ cents.  Write the generating function for that sequence.

\solution{
There is no way to change amounts that are not multiples of five with only
nickels.  There is exactly one way to change amounts that are multiples of five
with only nickels.  So the  sequence is $N_n = <1, 0, 0, 0, 0, 1, 0, 0, 0, 0,
1, \ldots>$.  The generating function for the  
sequence is $N = 1 + x^5 + x^{10} + x^{15} + \ldots = \frac{1}{1-x^5}$.
}

\ppart Write the generating function for the number of ways to use only nickels
and pennies to change $n$ cents.  

\solution{
Since P and N are ordinary generating functions for the number of ways to
choose items from disjoint sets, we can apply Rule 5.1 from Lecture 16 and
simply multiply the two generating functions from the previous parts to find a
generating function for the number of way to choose objects from the union of
the sets.  $N \cdot P = \frac{1}{(1-x)(1-x^5)}$. 
}

\ppart Write the generating function for the number of ways to use
pennies, nickels, dimes, quarters, and half-dollars to give $n$ cents change.

\solution{
Generalizing our method gives;
$C = \frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})(1-x^{50})}$.
}

\ppart How do you use this function to find out how many ways are there to
change 50 cents? 

\solution{
The answer is the coefficient to $x^50$ of the $C$ polynomial.
(It happens to be 50.)
}
\solution{

}

\eparts

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

%%%%%%% Problem %%%%%%%%
% source: spring99 ps8
% topic: infinity, incomputable functions

\problem In this problem we will prove the remarkable fact that
there exist mathematical functions that computers, no matter how powerful,
simply cannot compute.  We will do this through countability arguments.
\bparts
\ppart 

Show that the set of finite length binary strings is countable.

\solution{
Let $B_n$ denote the set of binary strings of length $n$.
This set has exactly $2^n$ elements.  Therefore the set of finite
length binary strings $B=\bigcup_{n\in\naturals}B_n$ is a union of
countable number of finite sets.  We know from Lecture 17 that such
union is countable.

Namely, one can easily list all elements of $B$ by first listing the
elements of $B_1$, then the elements of $B_2$, then the elements of
$B_3$, etc,.  We can do this since each set $B_i$ has a finite number
of elements.


{\bf Alternative Solution:} 
Some students noticed that finite length binary strings can be thought
of as natural numbers represented base $2$.  Therefore, an injective mapping
from finite length binary strings to natural numbers can be constructed as
follows:
\[
f(b_0b_1b_2...b_n)= 2^{n+1}+(b_0+b_12+b_22^2+...+b_n2^n)
\]
i.e. we map a string of bits to a natural number that it represents
in binary, except that we add $2^{n+1}$ term to make sure that bit
strings of different length get mapped to a different natural number
(Otherwise strings $0010$, $010$, $10$ would all map to the same number).
You can check that $f$ is an injection from $B$ to $\naturals$ and hence
$B$ is countable.  

You can also easily modify $f$ to be a bijection if instead of adding
$2^{n+1}$ term to the right side, you add $2^{n+1}-1$.  }


\ppart 

From your answer to the previous part, 
what can you conclude about the countability of the set of all
computer programs?  

\solution{
Since every computer program can be represented as a finite string of
bits (e.g. machine language code), it follows that the set of all
computer programs is countable.

Namely, the mapping which represents computer programs as finite
strings of bits is an injection.  Hence there is a surjection from the
set of finite strings of bits to the set of computer programs.  From
(a) we know that there is a surjection from the set of natural numbers
to the set of finite strings of bits.  By transitivity of surjective
mapping, there is a surjection between natural numbers and computer
programs.  Hence the set of all computer programs is countable.  }


\ppart 
Show that the set of {\em infinite} length binary strings is uncountable.

\solution{
We construct a bijection from the set $B'$ of infinite length binary
strings to the power set of the natural numbers $P(\naturals)$.  Since
$P(\naturals)$ is uncountable, it will then follow that $B'$ is
uncountable.

We need to associate a subset of the naturals with each infinite
length binary string.  Let $b=b_0 b_1 b_2 b_3\ldots \in{B'}$ be an
infinite length binary string (here each $b_i \in \{0,1\}$).  We
associate with this string the set $f(b) = S = \{ i \ | \ b_i = 1 \}$.
That is, we include $i$ in $S=f(b)$ if and only if the $i$-th bit
position (from the left) of $b$ is 1.  Such mapping
$f:B'\rightarrow{P(\naturals)}$ is a bijection: It is an injection
because if two infinite length binary strings are different, then
clearly they map to different subsets.  Furthermore, it is a
surjection because for every subset $S\in P(\naturals)$, there is a
binary string $b$ s.t. $f(b)=S$, namely $b=b_0b_1b_2b_3\ldots$ where
$b_i$ is defined as $0$ if $i\not\in{S}$ and $1$ if $i\in{S}$.

{\bf Alternative Solution:} 
One can also show that the set $B'$ is uncountable directly by a
diagonalization argument.

Assume $B'$ is countable and let $b^{(1)},b^{(2)},b^{(3)},b^{(4)},...$
be a list of all elements of $B'$.  By diagonalization, we will
construct an element $b=b_0b_1b_2b_3...\in{B'}$ s.t. $b\neq b^{(i)}$
for all $i\in\naturals$ as follows: $j$-th bit of $b$ is defined as
the opposite of the $j$-th bit of string $b^{(j)}$.  Obviously, so
defined $b$ is not equal to any $b^{(i)}$ from the list because for
every $i$, the $i$-th bit of $b^{(i)}$ is different than the $i$-th
bit of $b$.  Therefore, the list $b^{(1)},b^{(2)},b^{(3)},b^{(4)},...$
is {\it not} a list of all elements in $B'$, and thus the assumption
that $B'$ is countable leads to a contradiction.  

}

\ppart 
A function is a {\em decision function} if it maps finite length bit
strings into the range $\{0,1\}$.  
% In other words, the function assigns a single bit 
% to every finite length bit string.  
Let $F$ be the set consisting of {\em all possible} decision
functions.  Show that set $F$ is uncountable.

\solution{
From part (a), we know that there is a bijection from the set of
all finite length bit strings to the set of natural numbers (because
the set of all finite length bit strings was infinite and countable),
hence we can think of decision functions as mapping natural numbers to
the range $\{0,1\}$, i.e. to single bits.

It is easy to see a bijection between a set of such mappings and a
power set of the natural numbers.  Namely, we associate with a
decision function $f$ a set $S=\{i\in\naturals\mbox{ s.t. }f(i)=1\}$.
Clearly, this is an injection and a surjection.  Therefore, since the
power set of the set of natural numbers is uncountable then so is the
set of decision functions.

{\bf Alternative Solution:} 
We can give a bijection between the set of all decision functions and
the set of all infinite length bit strings, which by part (c), implies
that the set of decision functions is uncountable.  Let $f$ be a
decision function.  We map $f$ to an infinite length string as
follows.  We set bit $i$ of the string to be $f(i)$.  That is, our
infinite length bit string will be $f(1) f(2) f(3) \ldots $.  Now,
observe that this mapping is a bijection.  In particular, suppose we
have two different decision functions $f$ and $g$.  Since they are
different, they must give a different output on some particular input.
Suppose that this particular input is the number $j$.  That is,
$f(j)\neq g(j)$.  Then, the corresponding infinite length binary
strings will differ in the $j-th$ position.  This shows that the
function is injective.  Now, if we have an infinite length bit string
$b_0 b_1 b_2
\ldots$, then a decision function $f$ defined as
$f(0) = b_0, f(1) = b_1, f(2) = b_2, \ldots$, will be mapped to that
string.  Therefore, the mapping function is surjective.  Since it's
both injective and surjective, it is also bijective.

{\bf Alternative Solution 2:} 
Some students gave a diagonalization argument for why $F$ is
uncountable: Assume otherwise and let $\{f_1,f_2,f_3,...\}$ be the
list of all elements of $F$.  From part (a) we know that $B$, the set
of all finite length binary strings is countable, so there must exist
a bijection $g:B\rightarrow\naturals$.  Now, define a decision
function $f:B\rightarrow\{0,1\}$ as follows:
\[
f(s)=\mbox{ the opposite of }f_{g(s)}(s)
\]
Then $f$ is different from all $f_i$'s because for all
$i\in\naturals$, $h$ differs from $f_i$ on string $s=g^{-1}(i)$.


{\bf Alternative Solution 3:} 
One can also argue, as some students did, that $F$ is uncountable by
showing the bijection between $F$ and the set, $P(B)$, of all subsets of
$B$.  The bijection associates with $f\in{F}$ a set of strings $b \in B$
s.t. $f(b)=1$.  Then, since by part (a) there is a bijection between $B$
and $\naturals$, there must be a bijection between $P(B)$ and
$P(\naturals)$.  By transitivity of bijective relation between sets, there
is a bijection then between $F$ and $P(\naturals)$.  Hence $F$ is
uncountable.

}


\ppart 

A function is computable if there is a computer program that computes
it.  From your answers to the previous parts, prove that there is a
decision function that is not computable.
% STAS: repetitions...
% That is, there is no computer program that computes it.  

(Hint: compare your answer from the second part to the the answer you
just got from the previous part)

\solution{
Since there are only countably many computer programs,
but uncountably many decision functions, there can be no surjection
from the set of computer programs to the set of decision functions (In
fact, this means that there is {\it more} decision functions than
computer programs).  In particular, if we associate a computer program
to a decision function which this program is computing\footnote{If a
program is not computing any decision function, associate it with a
trivial decision function $f(b)=0$, for all finite bit strings $b$.},
this association is not a surjection either.  Therefore there must be
some decision function which is not computed by any computer program.}

\eparts                          

\end{problems}
\end{document}

















