\documentclass[12pt,twoside]{article}

\def\handouttype{problemset}

\usepackage{psfig}
\usepackage{changebar}
%\newcommand{\cbstart}{\chgbarbegin}
%\newcommand{\cbend}{\chgbarend}

\input{macros-course}

\def\cent{{\not\!\mathrm{c}}}

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

\askaboutsolutions

\renewcommand{\solution}[1]{%
  \ifshowsolutions %
%  \cbstart
  \textbf{Solution.} \par %
  #1
  \mbox{} \\
  \mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
  \raisebox{-0.25\baselineskip}{$\square$}%
  \hspace*{1ex}\ignorespaces\hrulefill%
%  \cbend
  \nopagebreak%
  \else
%  \vspace*{2in}
  \fi}

\newcommand{\problembreak}{%
  \ifshowsolutions %
  \newpage
  \else
  \newpage
  \fi%
}

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

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\tutref}{tut8}
\newcommand{\tutnum}{8}
\newcommand{\tutdate}{March 31, 2000}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\handout{\tutref}{Mini-Quiz \tutnum}{\tutdate}

\begin{enumerate}
\item Write your name:

\bigskip

\item %
  (Rosen, Section 2.2, Problem 3) Suppose that an element happens to
  be among the first four elements in a list of 32 elements (but you
  don't know that).  Would linear search or binary search locate this
  element more rapidly?  Explain why.

  \vspace*{3in}

\end{enumerate}

\newpage
\thispagestyle{empty}

\mbox{}

\setcounter{page}{0}

\newpage
\handout{\tutref}{Tutorial \tutnum~Problems}{\tutdate}

\begin{problems}

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


\problem 

Let $\{0,1\}^n$ be the set of all bit strings of length $n$.

\begin{problemparts}

\ppart

How many functions are there with domain $\{0,1\}^m$ and codomain
$\{0,1\}^n$?


\solution{

There are $2^m$ elements in the domain.  There are $2^n$
elements in the codomain.  For every element in the domain, we thus have
$2^n$ choices for what we can map it to.  Therefore, by the Product Rule,
there are $(2^n)^{2^m}$ possible functions with domain $\{0,1\}^m$ and
codomain $\{0,1\}^n$.}

\ppart

A value $x$ is called a {\em fixed point} of a function $f$ if $f(x) = x$.
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em no} fixed
points?

\solution{
To count all the functions without fixed points, we observe that such a
function could map each element of the domain to any element but itself,
that is, to any one of the remaining $2^n - 1$ elements in the codomain.
There are $2^n$ elements in the domain, so, by Product Rule there are
$(2^n-1)^{2^n}$ such functions with no fixed points.}

\ppart 
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em at least one} 
fixed point?

\solution{
There are $(2^n)^{2^n}$ functions, and $(2^n-1)^{2^n}$ have no
fixed points.  Therefore, the remaining $(2^n)^{2^n} - (2^n-1)^{2^n}$ have
at least one fixed point.}

\ppart
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em exactly one} 
fixed point?

\solution{ Let's fix a particular point for our fixed point.  Now let's
consider where the remaining $2^n - 1$ points can be mapped.  Each one can
be mapped to any spot but itself---thus it can be mapped to exactly $2^n -
1$ possible spots.  So by the Product Rule, there are $(2^n - 1)^{2^n -
1}$ functions with exactly this particular fixed point and no other.  Now
there are $2^n$ possible choices for the particular fixed point, so by the
Sum Rule, the total number of functions with exactly one fixed point is
$2^n(2^n - 1)^{2^n - 1}$.}

\end{problemparts}

\problem

\bparts

\ppart

In lecture we demonstrated how to ``guess'' the fifth card in a poker hand
when a collaborator reveals the other four cards.  Describe a method for
guessing two hidden cards in a hand of nine cards, when your collaborator
reveals the other seven cards.

\solution{There must be $\ceil{9/4} = 3$ cards with the same suit, so our
collaborator chooses to hide two of them and then use the third one as
the first card to be revealed.  So this first revealed card fixes the
suit of the two hidden cards; it will also be used as the origin for
the offset position of the first hidden card.  This first hidden card
will in turn be used as the origin for the offset of the other hidden
card.  There are six cards to code the two offset positions.  These
suffice to code two offsets of size from one to six.  That is, our
collaborator can choose one of the $3! = 6$ orders in which to reveal
the first three cards and thereby tell us the offset position of the
first hidden card.  Our collaborator can then choose the order of the
final three cards to describe the offset position of the second hidden
card from the first.  Note that the first revealed card must be chosen
so that both offsets are less $\leq 6$; since the sum of the offsets
between successive cars ordered in a cycle from Ace to King is 13, it
is not possible for more than one offset between successive cards to
exceed seven, so this is always possible.}

\ppart Show that there is no procedure for ``guessing'' a hidden card
among four when your collaborator reveals three. \hint Compare the number
of hands to the number of revealed three-card sequences.
~
\solution{
There are $\binom{52}{4}$ possible four-card hands.  There are $P(52,3)$
three-card sequences that can ever be revealed.  Since
\[
\frac{\binom{52}{4}}{P(52,3)}=
\frac{52\cdot 51\cdot 50 \cdot 49/4!}{52 \cdot 51 \cdot 50} = 49/24 > 1,
\]
there must, by pigeonholing, be two (actually three) hands for which the
collaborator reveals the same three cards.  Therefore the magician cannot
determine the hidden card, since these hands must have different hidden
cards.}

\eparts

\problem %
Consider a sequence of \textit{distinct} real numbers $a_1, a_2,
\ldots, a_{mn+1}$.  Prove that there exists an increasing subsequence
\[ a_{i_1}<a_{i_2}<\cdots<a_{i_{m+1}}\mathrm{\ with\ 
  }i_1<i_2<\cdots<i_{m+1} \] or a decreasing subsequence \[
a_{j_1}>a_{j_2}>\cdots>a_{j_{n+1}}\mathrm{\ with\ 
  }j_1<j_2<\cdots<j_{n+1} \] or both.

\solution{%
  Assume there is no increasing subsequence of length greater than
  $m$.  Then, $f$ be a function mapping the numbers $a_i$ to the
  length of the longest increasing subsequence of the initial sequence
  of numbers starting from the number $a_i$; that is, $f$ is a map
  from the numbers $a_i$ to $\set{1,\ldots,m}$.

  By the pigeonhole principle, there is some $s$ such that $f(a_i)=s$
  for at least $\ceil{\frac{mn+1}{m}} = n+1$ numbers of the original
  sequence.  Let $a_{j_1},a_{j_2},\ldots,a_{j_{n+1}}$ (with
  $j_1<j_2<\cdots<j_{n+1}$) be such a subsequence of the original
  sequence of $mn+1$ numbers.

  For this subsequence, it is the case that $a_{j_k}>a_{j_{k+1}}$, for
  all $1\leq k\leq n$; otherwise, $f(a_{j_k})\geq s+1$, which
  contradicts our initial assumption that there is no increasing
  subsequence of length greater than $m$.

  So, if $t_i\geq m+1$ for some $i$, then we have such an increasing
  subsequence; otherwise, $a_{j_1},a_{j_2},\ldots,a_{j_{n+1}}$ is a
  decreasing subsequence of the appropriate length.
  %
}

\end{problems}

\end{document}

