\documentclass[11pt,twoside]{article}
\usepackage{macros-course-lectures}
\usepackage{graphicx}


\onlystudents

\begin{document}

\lecture{bijections}{Functions, Counting, and the Pigeonhole
Principle}{22 March 2001}

There are many ways of counting the elements in a set.  For example,
last lecture we used recurrences to count the number of computer
science professors in a given year. In the week before, we used
summations to count the number of dollars paid by an annuity.

Another good way to determine the cardinality of a set is to show that
the items it contains can be correlated in some way with the items in
another set whose cardinality is known.  For example, suppose we want
to determine the cardinality of the set of students' watches in the
6.042 classroom.  The set of watches can be correlated with the set of
students; specifically, for each student there is at most one watch.
(At least, let's assume this.)  Now we know something about the
cardinality of the set of students, since there are only 180 people
signed up for 6.042.  So we can conclude that there are at most 180
student's watches in the classroom.

This type of argument is very simple, but also quite powerful.  We
will see how to use such simple arguments to prove results that are
hard to obtain any other way.

\section{Functions}

The formal way that we establish a correlation between two sets is by
special types of functions called surjections, injections, and
bijections.  We will define these terms in a minute, but let's start
slowly and just recall the definition of a function.
\begin{definition}
  A \emph{function} $f \from A \to B$ is a way of relating \emph{every}
  item in a set $A$ with \emph{precisely one} item in a set $B$.  In
  particular, the item $a \in A$ is related to an item in $B$ denoted
  $f(a)$.  The set $A$ is called the \emph{domain} of the function, and
  the set $B$ is called the \emph{range} of the function.
\end{definition}
If the sets $A$ and $B$ are small, then we can describe the function
with a diagram as in Figure~\ref{fig:function}.  These diagrams are
helpful in explaining what a function is and how injections,
surjections, and bijections differ.
\begin{figure}
  \centerline{\includegraphics[height=2.5in]{figures/function}}
  \caption{In each of the three diagrams, $A$ is the set of dots in the
    left column and $B$ is the set of dots in the right column.  The
    left diagram shows a function; every item in set $A$ is mapped to
    precisely one item in set $B$.  The center and right diagrams do
    not depict functions.  In the center diagram, not every item in
    set $A$ is mapped.  In the right diagram, an item in set $A$ is
    mapped to more than one item in set $B$.}
\label{fig:function}
\end{figure}
\begin{definition}
  The \emph{image} of a function $f \from A \to B$ is the set $\{b \mid
  \exists a \ f(a) = b \}$ and is denoted $f(A)$.
\end{definition}

In other words, the image is the set of values in the domain that the
function $f$ actually takes on.  The image is always a subset of the
range.  For example, consider the function $f \from  \reals \to \reals$
defined as follows:
\[
f(x) = \left\{
\begin{array}{ll}
x & \mbox{if $x \geq 0$} \\
-x & \mbox{if $x < 0$}
\end{array}
\right.
\]

This defines the familiar absolute value function $f(x) = |x|$.
Notice that while the domain and range of $f$ are both the set of all
real numbers, the image of $f$ is only the set of non-negative real
numbers.

As another example, consider the ``function'' $f \from \reals \to
\reals$ defined by $f(x) = \sqrt{x}$.  There are two issues here.
First, for $f$ to be a function, we must specify that $\sqrt{x}$
denotes just one of the two square roots of $x$; otherwise, elements
in the domain would not be associated with \emph{precisely one} element
in the range.  For example, $4$ could be associated with both $2$ and
$-2$.  Second, we have not related \emph{every} element in the
domain~$\reals$ with an element in the range~$\reals$.  For example,
$-1$ is an element in the domain not associated with any element in
the range.  For this reason, $f$ is not a function.

\subsection{Surjections, Injections, and Bijections}

Now we'll look at three special types of function.
\begin{definition}
  A function $f \from A \to B$ is a \emph{surjection} if for all $b
  \in B$, there exists an $a \in A$ such that $f(a) = b$.
\end{definition}
In other words, a function $f$ is a surjection if it takes on every
value in its range.  That is, the image of $f$ is the entire range of
$f$.  Figure~\ref{fig:surjection} shows the idea of a surjection with
diagrams.  A surjective function is also sometimes called an
\emph{onto} function.
\begin{figure}
  \centerline{\includegraphics[height=2.5in]{figures/surjection}}
  \caption{The left diagram shows a surjection; every item in set $B$ is
    mapped to by some item in $A$.  The right diagram does not show a
    surjection, because one item is $B$ is missed.}
\label{fig:surjection}
\end{figure}
\begin{definition}
  A function $f \from A \to B$ is an \emph{injection} if for all $a, a'
  \in A$, $(a \neq a') \Rightarrow (f(a) \neq f(a'))$.
\end{definition}
Informally, $f$ is an injection if no two items in $A$ are mapped to
the same item in $B$.  Note that $f$ need not take on every value in
its range; the only restriction is that $f$ cannot take on the same
value twice.  This idea is shown pictorially in
Figure~\ref{fig:injection}.  Injective functions are also called
\emph{one-to-one}.
\begin{figure}
  \centerline{\includegraphics[height=2.5in]{figures/injection}}
  \caption{The left diagram shows an injection; no two items in $A$
    are mapped to the same item in $B$.  The right diagram does not
    show an injection, because two items in $A$ are mapped to the same
    item in $B$.}
\label{fig:injection}
\end{figure}
\begin{definition}
  A function $f \from A \to B$ is a \emph{bijection} if it is both a
  surjection and an injection.
\end{definition}
Bijections are the nicest sort of function because they associate each
element of $A$ with exactly one element of $B$ and vice versa.  This
is shown in Figure~\ref{fig:bijection}.  Sometimes a bijection is
also called a \emph{1-to-1 correspondence} or a \emph{one-to-one and
onto} function.
\begin{figure}
  \centerline{\includegraphics[height=2.5in]{figures/bijection}}
  \caption{The left diagram shows a bijection; each element of $A$ is
    associated with exactly one element of $B$ and vice versa.  The
    center diagram does not show a bijection because an element of $B$
    is not associated with any element of $A$; $f$ is not onto.  The
    right diagram also does not show a bijection.  In this case, the
    reason is that one element of $B$ is associated with two elements
    of $A$; $f$ is not one-to-one.}
\label{fig:bijection}
\end{figure}

\subsection{Examples of Functions}

Define $f \from  \naturals \to \naturals$ by $f(x) = 2x$.  This is a
function, since it maps every number in the domain $\naturals$ to
precisely one number in the range $\naturals$.  The function is
injective (or ``one-to-one'') because no two distinct integers are
mapped to the same value.  This fact is easy to see, but let's prove
it formally:
\begin{fact}
  The function $f$ is one-to-one.
\end{fact}
\begin{proof}
  We must show that for all $x, x' \in \naturals$, $(x \neq x')
  \Rightarrow (f(x) \neq f(x'))$.  We will prove the contrapositive;
  that is, for all $x, x' \in \naturals$, $(f(x) = f(x')) \Rightarrow
  (x = x')$.  For all $x, x' \in \naturals$, we have:
  \begin{eqnarray*}
    f(x) = f(x') & \Rightarrow & 2x = 2x' \\
    & \Rightarrow & x = x'
  \end{eqnarray*}
  The first equality follows by substituting the definition of $f(x)$,
  and the remainder is simplification.
\end{proof}
The function $f$ is not surjective (or ``onto'').  In other words, $f$
does not take on all values in the range $\naturals$.
\begin{fact}
  The function $f$ is not onto.
\end{fact}
\begin{proof}
  The proof is by contradiction. Assume for the purpose of
  contradiction that $f$ is onto. Then there exists an $x \in
  \naturals$ such that $f(x) = 3$. Substituting the definition of $f$
  gives $2x = 3$ or $x = 3/2$.  But this contradicts the assumption
  that $x \in \naturals$.
\end{proof}



\section{Counting}

Injections, surjections, and bijections are useful in counting the
number of items in a set.

Suppose there is an injection from $A$ to $B$.  For example, let $A$
be a set of balls, and let $B$ be a set of boxes.  Then an injection from
$A$ to $B$ is a way of assigning balls to boxes so that no box gets
multiple balls.  If such an assignment exists, then intuitively there
can be no more balls than boxes.  We can state this as a theorem.
\begin{theorem}
  \label{th:injection}
  If $A$ and $B$ are finite sets and $f \from A \to B$ is an
  injection, then $|A| \leq |B|$.
\end{theorem}
\begin{proof}
  Suppose $A$ is the $n$-element set $\{ a_1, a_2, \ldots, a_n \}$.
  Since $f$ maps $A$ to $B$, the set \\ $\{ f(a_1), f(a_2), \ldots
  f(a_n) \}$ is a subset of $B$.  Because $f$ is an injection, all the
  $f(a_i)$ are different and so $B$ also contains at least $n$
  elements.  Therefore, $|A| \leq |B|$.
\end{proof}
The condition in the theorem that sets $A$ and $B$ are finite is
important.  For example, suppose $A = \{ 0, 1, 2, 3, \ldots \}$ and $B
= \{ 0, 2, 4, 6, \ldots \}$.  The function $f \from A \to B$ defined
by $f(x) = 2x$ is an injection.  This would seem to imply that $A$ is
no larger than $B$.  However, in fact $A$ contains all the natural
numbers, but $B$ contains only the even natural numbers!  We will
resolve this apparent paradox in the lecture on countable and
uncountable sets; for today we'll avoid the problem by sticking with
finite sets.

Suppose again that $A$ is a set of balls and $B$ is a set of boxes.
If there is a surjection from $A$ to $B$, then we can assign balls to
boxes so that every box gets at least one ball.  This suggests that
there must be as many balls as there are boxes.
\begin{theorem}
  \label{th:surjection}
  If $A$ and $B$ are finite sets and $f \from A \to B$ is a surjection,
  then $|A| \geq |B|$.
\end{theorem}
\begin{proof}
  Suppose $B$ is the $n$-element set $\{b_1, b_2, \ldots, b_n \}$.
  Since $f$ is a surjection from $A$ to~$B$ there exists, for every
  $b_i \in B$, an $a_i \in A$ such that $f(a_i) = b_i$. Moreover,
  since $f$~is a function, all $a_i$s must be distinct. Thus, the
  set~$A$ contains at least $n$~elements. Therefore, $|A| \geq |B|$.  
\end{proof}
Taken together, these two theorems have an important corollary.
\begin{corollary}
  \label{cor:bijection}
  If $A$ and $B$ are finite sets and $f \from A \to B$ is a bijection,
  then $|A| = |B|$.
\end{corollary}
\begin{proof}
  Theorem~\ref{th:injection} implies that $|A| \leq |B|$.
  Theorem~\ref{th:surjection} implies that $|A| \geq |B|$.  Therefore,
  $|A| = |B|$.
\end{proof}
This corollary is used all the time.  Suppose that we want to know the
cardinality of some set $A$ and already know the cardinality of a set
$B$.  If we can find a bijection between $A$ and $B$, then the
corollary implies that $|A| = |B|$.  This idea is very simple, but
amazingly useful. It also gives a way to define the cardinality of a
finite set formally.
\begin{definition}
  A finite set~$A$ has \emph{cardinality~$n$}, which we denote $|A| =
  n$, if there is a bijection from~$A$ to $\{1, 2, \ldots, n\}$.
\end{definition}



\subsection{Example of Bijection: Subsets of a Set}

Here is an example of a counting problem that can be solved by finding
a bijection.  Suppose we have a set with $n$ elements; how many
subsets are there?

The following definition lets us restate this as a question about the
cardinality of a set.
\begin{definition}
  The \emph{power set} of a set $\mathcal{U}$, often denoted
  $2^{\mathcal{U}}$, is the set of subsets of $\mathcal{U}$:
  \[
  2^{\mathcal{U}} = \{ S \mid S \subseteq \mathcal{U} \}
  \]
\end{definition}
For example, if $\mathcal{U} = \{ u_1, u_2 \}$, then $2^{\mathcal{U}} = \{ \{
u_1 \}, \{ u_2 \}, \{ u_1, u_2 \}, \emptyset \}$.  In this case,
$\mathcal{U}$ has four subsets and, equivalently, the power set $2^{\cal
  U}$ has four elements.

Our problem, therefore, is to determine the cardinality of the power
set of an $n$-element set.  Our method will be to establish a
bijection between the power set and the set of all $n$-bit binary
strings.  Since there are $2^n$ such binary strings,
Corollary~\ref{cor:bijection} will imply that the power set has
cardinality $2^n$.  (We could formally prove that the number of
$n$-bit binary strings is $2^n$ using induction, but this is
practically an axiom for computer science.)  The details are given in
the following theorem and proof.
\begin{theorem}
  Let $\mathcal{U} = \{ u_1, u_2, \ldots, u_n \}$.  Then $|2^{\mathcal{U}}| =
  2^n$.
\end{theorem}
\begin{proof}
  We will establish a bijection from $2^{\mathcal{U}}$ to the set of all
  $n$-bit binary strings, $B_n = \{ b_1 b_2 \ldots b_n \mid b_i \in \{
  0, 1 \} \}$.  This is sufficient to prove the theorem; since $|B^n|
  = 2^n$, Corollary~\ref{cor:bijection} will imply that $|2^{\mathcal{U}}|
  = 2^n$.
  
  Let $f \from 2^{\mathcal{U}} \to B_n$ be the function defined by $f(S) =
  b_1 b_2 \ldots b_n$ where:
  \[
  b_i = \begin{cases}
    1 & \mbox{if $u_i \in S$} \\
    0 & \mbox{if $u_i \not\in S$}
  \end{cases}
  \]
  (This is a digression from the proof to give some intuition about
  the bijection $f$.  As an example, if $\mathcal{U} = \{ u_1, u_2 \}$,
  then the values of $f$ are as shown below.
  \begin{eqnarray*}
    f(\{ u_1, u_2 \}) & = & 11 \\
    f(\{ u_1 \}) & = & 10 \\
    f(\{ u_2 \}) & = & 01 \\
    f(\emptyset) & = & 00
  \end{eqnarray*}
  In this example, $f$ is certainly a bijection; every subset is matched
  with a unique binary string and vice-versa.  To complete the theorem,
  we must show that $f$ is a bijection in general.)
  
  To prove that $f$ is a bijection, we must show $f$ is a one-to-one
  and onto function.  First, $f$ is a well-defined function, since
  every element of the domain $2^{\mathcal{U}}$ is mapped to an element of
  the range $B_n$.
  
  Next, we must show that $f$ is one-to-one.  In other words, for all
  $S, S' \in 2^{\mathcal{U}}$, if $S \neq S'$, then $f(S) \neq f(S')$.  We
  will prove the contrapositive; that is, for all $S, S' \in 2^{\cal
    U}$, if $f(S) = f(S') = b_1 b_2 \ldots b_n$, then $S = S'$.  This
  is true because $u_i \in S \Leftrightarrow b_i = 1 \Leftrightarrow
  u_i \in S'$.  Every element in $S$ is also in $S'$ and vice-versa.
  
  Finally, we must show that $f$ is onto; that is, for all $b_1 b_2
  \ldots b_n \in B$, there exists an $S \in 2^{\mathcal{U}}$ such that
  $f(S) = b_1 b_2 \ldots b_n$.  To prove this, we can construct such
  an $S$ explicitly: $S = \{ u_i \mid b_i = 1 \}$.  Then $f(S) = b_1
  b_2 \ldots b_n$ as desired.
\end{proof}
This is a simple example of the use of bijection to find the
cardinality of a set; we'll see examples later that are more
interesting.  In more complicated problems, finding a bijection can
require considerable ingenuity.



\subsection{Counting numbers of functions}

The ideas involved in counting the number of subsets of a set can be
generalized to help in counting the number of functions from one set
to another:

\paragraph{Question:} How many different functions are there from
finite set~$A$ to finite set~$B$?

\begin{example}
  $|A| = 3$, $|B| = 2$.
  \forlecture{Draw all the possibilities. 8 of them.}
\end{example}
\begin{theorem}
  If $A$ and $B$ are finite sets, with $|A| = n$ and $|B| = m$, then
  the cardinality of the set of functions from $A$ to~$B$ is~$m^n$.
\end{theorem}
\begin{proof}
  Use bijection from $\{f \from A \to B\}$ to $\{\mbox{length~$n$
    strings of symbols from~$B$}\}$. The mapping is $f \mapsto
    f(a_1)f(a_2)\cdots f(a_n)$, i.e., the $i$th position in the string
    corresponding to~$f$ is equal to~$f(a_i)$.
  
  \forlecture{Example: The first function above is encoded by $111$,
    second by $121$, \ldots, last is $222$.}
  
  Prove that the mapping is injective (one-to-one) by contradiction.
  Assume that $f \mapsto s_f$ and $g \mapsto s_g$ where $f \neq g$ and
  $s_f = s_g$. That $f \neq g$ implies that there exists an $a \in A$
  such that $f(a) \neq g(a)$. But that implies that the corresponding
  positions in~$s_f$ and~$s_g$ must be different, which is a
  contradiction.
  
  Prove that the mapping is surjective (onto), i.e., that every string
  encodes some function. Fix an arbitrary length~$n$ string of symbols
  from~$B$, call this string~$s$. Denote the $i$th position in this
  string by $s[i]$. Now define a function~$f$ by the mapping $a_i
  \mapsto s[i]$, i.e., $f(a_1) = s[1], f(a_2) = s[2], \ldots, f(a_n) =
  s[n]$. This defines a function from $A$ to~$B$.
\end{proof}



\section{The Pigeonhole Principle}

The theorem about injections, Theorem~\ref{th:injection}, has another
important corollary:
\begin{corollary}
  \label{cor:pigeon}
  Let $A$ and $B$ be finite sets.  If $|A| > |B|$ and $f \from A \to
  B$, then there exist distinct elements $a$ and $a'$ in $A$ such that
  $f(a) = f(a')$.
\end{corollary}
\begin{proof}
  The contrapositive of Theorem~\ref{th:injection} is that if $|A| >
  |B|$, then $f$ is not an injection.  The corollary then follows from
  the definition of an injection.
\end{proof}
This corollary is a very famous result known as the Pigeonhole
Principle.  The name derives from the following, more colorful
statement of the corollary:

\paragraph{Pigeonhole Principle:} If $n + 1$ pigeons are put into $n$
holes, then at least one hole contains two or more pigeons.
\begin{proof}
  Let $A$ be the set of ``pigeons'', let $B$ be the set of ``holes'',
  and let the function $f \from A \to B$ define the assignment of
  pigeons to holes.  Since $|A| > |B|$, Corollary~\ref{cor:pigeon}
  implies that there exist two distinct pigeons assigned to the same
  hole.
\end{proof}
As a trivial application of the Pigeonhole Principle, suppose that
there are three people in a room.  The pigeonhole principle implies
that two have the same gender.  In this case, the ``pigeons'' are the
three people and the ``pigeonholes'' are the two possible genders,
male and female.  Since there are more pigeons than holes, two pigeons
must be in the same pigeonhole; that is, two people must have the same
gender.
\begin{theorem}
  In New York (City) there live at least two people with the same
  number of hairs.
\end{theorem}
\begin{proof}[Proof (found on the web)]
  I ran experiments with members of my family. My teenage son secured
  himself the highest marks sporting, in my estimate, about 900 hairs
  per square inch.  Even assuming a pathological case of a 6 feet
  (two-sided) fellow 50 inch across, covered with hair head, neck,
  shoulders and so on down to the toes, the fellow would have
  somewhere in the vicinity of 7,000,000 hairs which is probably a
  very gross over-estimate to start with. The Hammond's World Atlas I
  purchased some 15 years ago, estimates the population of the New
  York City between 7,500,000 and 9,000,000. The assertion therefore
  follows from the pigeonhole principle.
\end{proof}
The pigeonhole principle seems too obvious to be really useful, but
the next two examples show how it gives short proofs of results that
are difficult to obtain by other means.



\subsection{Pigeonhole Principle Example: A Final Exam Question}

A problem on an old final exam was to prove the following claim:
\begin{claim*}
  In every set of 1000 integers, there are two integers $x$ and $y$
  such that $573 \mid (x-y)$.
\end{claim*}
At first glance, this looks very hard!  Those 1000 numbers could be
anything!  Since there are no less than 1000 integer-valued variables
here, even our old standby, induction, seems hopeless.  Surprisingly,
however, there is a short proof using the Pigeonhole Principle.

To apply the Pigeonhole Principle, we must identify two things:
pigeons and holes.  Furthermore, to prove anything with the Pigeonhole
Principle, we must have more pigeons than holes.  Since there are only
two numbers mentioned in this problem, a natural thing to try is 1000
pigeons and 573 holes.

Under this interpretation, a pigeon is an integer, but what is a hole?
Ideally, the existence of two pigeons and in the same hole should be
equivalent to the existence of two numbers $x$ and $y$ such that $573
\mid (x-y)$.  This suggests numbering the holes $0, 1, \ldots 572$ and
putting in hole $n$ all integers congruent to $n$ modulo 573.  Now we
can construct a proof:
\begin{proof}
  Let $S$ be a set of 1000 integers.  Let $M = \{ 0, 1, \ldots 572
  \}$.  Let $f \from S \to M$ be the function defined by $f(n) = n
  \bmod 573$.  Since $|S| > |M|$, Corollary~\ref{cor:pigeon} implies
  that there exist distinct elements $x$ and $y$ in $S$ such that
  $f(x) = f(y)$.  This means $(x \bmod 573) = (y \bmod 573)$ and so
  $573 \mid (x-y)$.
\end{proof}
Really there was nothing special about the numbers 1000 and 573 other
than the fact that $1000 > 573$.  We could have made a stronger claim:
if $n > m$, then in every set of $n$ integers, there are two integers
$x$ and $y$ such that $m \mid (x-y)$.

\subsection{Pigeonhole Principle Example: Weighing Balls}

In the first tutorial you were given the following problem.  There are
12 balls of which 11 have the same weight and one has a different
weight.  With three weighings on a balance scale, you must identify
the odd ball and determine whether it is heavier or lighter than the
rest.  (A balance scale has a left pan and a right pan.  In a weighing
you put some balls in each pan.  The scale then reveals whether the
left pan is heavier, the right pan is heavier, or the two are equal.)

The problem is solvable using a tricky algorithm represented by a
ternary tree as shown in Figure~\ref{fig:weighing}.  Each internal
node in the tree represents a weighing such as, ``put balls 1, 3, and
5 on one side and 2, 8, and 10 on the other side''.  Each leaf node
represents a result such as, ``the 11th ball is heavier than the
rest''.  A run of the algorithm corresponds to a path from the root to
a leaf.  At each internal node, we perform the weighing associated
with the node.  Based on the result, we descend to one of the three
children.  When we reach a leaf, we output the indicated result.
\begin{figure}
  \centerline{\includegraphics[height=2.0in]{figures/weighing}}
  \caption{A strategy for the weighing problem can be represented by a
    ternary tree.  Each internal node represents a weighing.  Each
    leaf node represents a result.  A run of the algorithm corresponds
    to a path from the root to a leaf.  At each internal node, we
    perform the weighing associated with the node and descend to a
    child based on the result.  At a leaf, we output the indicated
    result.}
  \label{fig:weighing}
\end{figure}

Suppose that we wanted to solve the same problem with more balls, but
still with only three weighings.  The case with 13 balls is
complicated and we'll put it off a bit.  However, if there
are 14 balls, then we can prove that no solution exists.  This would
seem to require an elaborate case analysis to rule out every possible
strategy.  Actually, we can use the Pigeonhole Principle to give a
short proof that no weighing strategy exists for 14 balls.
\begin{theorem}
  The weighing problem can not be solved with 14 balls and 3 weighings.
\end{theorem}
\begin{proof}
  The pigeons are the possible situations.  Since any one of the 14
  balls could be the odd one and the odd ball could be either heavier
  or lighter than the rest, there are 28 possible situations and so 28
  pigeons.  The holes are the 27 leaves of the depth-3 ternary tree
  used to represent the weighing strategy.  Since there are more
  pigeons than holes, the Pigeonhole Principle implies that some hole
  must have two pigeons; that is, some leaf is not associated with a
  unique situation.  Therefore, for every weighing strategy, there is
  some pair of situations that the strategy cannot distinguish.  In at
  least one of these situations, the strategy must give the wrong
  answer.
\end{proof}
What if we had four weighings---could we identify the odd ball from
among~41?  In this case, there are $2 \cdot 41 = 82$ possible
situations or pigeons.  Every strategy can be represented by a depth-4
ternary tree with $3^4 = 81$ leaves or pigeonholes.  Once again, the
Pigeonhole Principle implies that in every weighing strategy, some
leaf of the tree must be associated with two or more situations.  The
strategy cannot distinguish these situations and so must sometimes
give the wrong answer.

In general, if there are $n$~balls, we can compute a lower bound on
the number of weighings necessary.  In this case, there are
$2n$~possible situations.  If there are $w$~weighings, then every
strategy can be represented by a ternary tree with $3^w$ leaves.  For
a correct weighing strategy to exist, there must be as many leaves as
situations.  That is, we must have $3 ^ w \geq 2n$ or, equivalently,
$W \geq \log_3 2n$.

Now we can address the tricky case of 13 balls and 3 weighings.  In
this case, we can not use the Pigeonhole Principle directly to prove
that there is no solution, because there are 26 situations and a
depth-3 tree has 27 leaves.  There may be a solution!  But note that
just because our Pigeonhole Principle argument does not rule out a
weighing strategy, does not imply that a such a strategy exists!  In
fact, a closer analysis shows that there is no solution.
\begin{theorem}
  The weighing problem can not be solved with 13 balls and 3
  weighings.
\end{theorem}
To prove the claim, we must do some of the hairy case analysis that
the Pigeonhole Principle lets us circumvent in the case of 14 balls.
Nevertheless, appeals to the Pigeonhole Principle do greatly simplify
the proof.
\begin{proof}
  Let $n$ be the number of balls placed in each pan of the balance
  scale on the first weighing.  Since there are 13 balls, $n$ could be
  1, 2, 3, 4, 5, or 6.  We can actually reduce these 6 cases to just
  two.
  
  (To gather some intuition, first consider $n = 1$. Then there are
  11~balls that were not used in the first weighing. If the first
  weighing came out equal, we have 22~possibilities left, but only two
  more weighings to use. But two weighings can only distinguish
  9~cases. Then consider $n = 6$. Suppose that the right pan was
  heavier in the first weighing. That leaves 12~possibilities, either
  one of the left balls are light or one of the right balls are heavy.
  Again, we only have two weighings left. Now we just extend the above
  ideas to cover all~$n$.)
  
  In the first case, suppose that $n \leq 4$.  This means that at
  least 5 balls are not used in the first weighing.  As a result,
  there are at least 10 situations in which the scale will be balanced
  on the first weighing.  (The odd ball could be any of the unweighed
  balls, and it could be either heavy or light.)  By the Pigeonhole
  Principle, we can not distinguish between these 10 or more cases
  with only two additional weighings.
  
  In the second case, suppose that $n \geq 5$.  Now there are $2n \geq
  10$ situations in which the right pan is heavier: $n$ when the odd
  ball is heavy and in the right pan and $n$ more when the odd ball is
  light and in the left pan.  Again, by the Pigeonhole Principle, we
  can not distinguish these 10 or more cases with only two weighings.
\end{proof}

\subsection{20 Questions and Binary Search}

Here is a game.  I think of an animal.  You can ask me 20 questions
that take a yes/no answer such as, ``Is the animal bigger than a
breadbox?''  To win the game, you must ask a question like, ``Is the
animal a walrus?'' or ``Is the animal a zebra?'' and receive a
``yes'' answer.  In effect, you have 19 questions to determine which
animal I am thinking of, and then you must use 1 question to confirm
your guess.

Suppose that I know a million animals.  Can you always determine
which animal I am thinking of?  Any questioning strategy you use can
be represented by a depth-19 binary tree as shown in
Figure~\ref{fig:animal}.  As in the weighing problem, each internal
node in the tree represents a question, and each leaf represents a
final guess at my animal.  A depth-19 binary tree can have at most
$2^{19} = 524,288$ leaves, and I can use any of a million animals.  By
the pigeonhole principle, at least two animals must be associated with
some leaf in the tree; this implies that you can not always determine
which animal I am thinking of with only 19 questions.
\begin{figure}
  \centerline{\includegraphics[height=2.0in]{figures/animal}}
  \caption{A strategy for the animal game can be represented by a depth-19
    binary tree.  Each internal node represents a yes/no question such
    as, ``Does the animal have fur?''  Each leaf node represents a
    final guess.  A run of the algorithm corresponds to a path from
    the root to a leaf.}
  \label{fig:animal}
\end{figure}
More generally, if I know $n$~animals, then $\lceil \log_2 n \rceil$
questions are necessary to always identify the one I'm thinking of; a
binary tree of lower depth must have fewer than $n$~leaves, and so
some animals can not be distinguished.

A similar argument applies to the binary search algorithm.  In a
binary search, we are looking for a particular item in a \emph{sorted}
list.  We begin by comparing the middle element in the list to the
item we are looking for.  If our item precedes the middle element,
then we continue the search recursively in the first half of the list.
Similarly, if our item follows the middle element, then we search
recursively in the second half of the list.  For example, binary
search could be applied to the animal game.  You could sort the list
of a million animals, pick out the middle one, and begin with a
question like, ``Does the animal alphabetically precede marmot?''  Not
surprisingly, given the similarity between the animal game and binary
search, a Pigeonhole Principle argument shows that binary search
requires $\Omega(\log n)$ steps to find an item in an $n$-element list
in the worst case.

(There is a small difference between the animal game and a binary
search.  A ``yes'' in the animal game corresponds to ``less than'' in
a binary search comparison, and a ``no'' corresponds to ``greater
than'' (or vice versa).  However, in a binary search, a comparison may
return ``equal'' and this has no analogue in the animal game.  This
extra possibility reduces the time required for a binary search, but
only by a constant factor.)

\subsection{Example: Subsets of a List of Numbers}

Show that any given $10$ distinct positive numbers less than $100$,
that two completely different subsets sum to the same quantity.

The numbers all vary between $1$ and $99$.  Therefore the maximum sum
of any $10$ chosen numbers is $90 + 91 + 92 + \ldots 99 = 945$.  The
number of different subsets of the $10$ numbers is $2^{10} - 1$
(excluding the null set) $= 1023$. We have $1023$ pigeons and $945$
holes. Using the pigeonhole principle, we can argue that two different
subsets map to the same sum.  If these subsets have a common number or
numbers, we can always remove the common numbers to produce two
completely different subsets that sum to the same quantity.

\end{document}


\documentclass[11pt,twoside]{article}
\usepackage{macros-course-lectures}
\usepackage{graphics}
\usepackage[pdflatex]{graphicx}

%\usepackage{amsmath}

\newcommand{\cuberoot}[1]{\sqrt[\leftroot{2}\uproot{4}3]{#1}}

\begin{document}

\lecture{notes13}{Functions, Counting, and the Pigeonhole
Principle}{22 March 2001}


\section{Self Study: Functions}

\subsection{Basic definitions}

\begin{definition*}
  A \emph{function} $f \from A \to B$ is a way of relating every element
  of $A$ to exactly one element of $B$.
\end{definition*}

If $a \in A$, write $f(a)$ for the corresponding element of $B$. \\
\\
$A =$ \emph{domain}, $B =$ \emph{range}. \\
\\
More formally, a function $f \from A \to B$ is a binary relation from
$A$ to $B$ such that, for every $a \in A$, there is exactly one $b \in
B$ such that $(a,b) \in f$. \\
\\
Example: \\
Draw a function (not onto). \\
\\
Example: \\
Draw a non-function (two values for some particular domain element). \\
\\
Example: \\
In the matching algorithm, at any particular point in time, 
each boy had a current girl he was pursuing. \\
Function from boys to girls, giving current girl. \\
Inverse is not a function. \\
\\
And some examples from continuous math. \\
In each case, $f \from  \reals \to \reals$. \\
\\
Example: \\
$f(x) = x^2 + 3x + 2$ \\
\\
Example: \\
$f(x) = |x|$ (define as $x$ if $x \geq 0$, $-x$ if $x < 0$. \\
\\
Example: \\
$f(x) = \sqrt{x}$ not a function. \\
Not uniquely defined. \\
Even if I mean the positive square root, still not a function: \\
Not defined everywhere on $\reals$. \\
\\
Example: \\
$f(x) =$ cube root of $x$ is a function.\\

\begin{definition*}
  The \emph{image} of a function $f \from A \to B$ is the set $\{b \mid
  \exists\; a \ f(a) = b \}$ and is denoted $f(A)$.
\end{definition*}

Values actually taken on, subset of range.\\ 
\\
Example: \\
First example above, image = ...\\
\\
Example: \\
$f(x) = x^2 + 3x + 2$.\\
Draw graph.\\
Min point is $(- \frac{3}{2}, - \frac{1}{4})$.\\
Image = $[- \frac{1}{4}, \infty)$.\\
\\
Example: \\
Absolute value.\\
Image = nonnegative reals.\\
\\
Example: \\
Cube root.\\
Image = reals.

\subsection{Special kinds of functions}

Classification relevant for counting: \\
surjective, injective, bijective \\

\begin{definition*}
Surjective (``onto'') \\
Image = range.\\
$\forall\; b \in B, \exists\; a \in A (f(a) = b)$.\\
\end{definition*}

Examples: \\
Diagrams, surjective and not surjective.\\
\\
Example: \\
At end of matching algorithm, current girl function is surjective.\\
\\
Example: \\
Cube root is surjective, as a function $: \reals \to \reals$.\\ 
\\
Example: \\
Absolute value not surjective as function $: \reals \to \reals$.\\ 
But could regard as function $: \reals \to \reals^{\geq 0}$, then surjective.\\
Depends on what's defined as the range.\\

\begin{definition*}
  Injective (``one-to-one'') \\ $\forall\; a, a' \in A, a \neq a'
  \Rightarrow f(a) \neq f(a')$ \\ 
\end{definition*}

Examples: \\
Diagrams, injective and not injective.\\
\\
Example: \\
Cube root injective.\\
\\
Example: \\
Absolute value not injective.\\

\begin{definition*}
Bijective = surjective + injective.\\
AKA one-to-one correspondence.\\
\end{definition*}

Examples: \\
Diagrams \\
Cube root

\subsection{Proving that functions are surjective and injective}

Example: \\
$f \from  \reals \to \reals$, $f(x) = \cuberoot{x}$ \\
\\
To prove injective, can show contrapositive:
\begin{tabbing}
XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXX\= \kill
Prove: $f$ is injective, that is, $a \neq a' \Rightarrow \cuberoot{a}
\neq \cuberoot{a'}$. \\
1. $\cuberoot{a} = \cuberoot{a'} \Rightarrow a = a'$. \\
\> 1. Assume $\cuberoot{a} = \cuberoot{a'}$. \\
\> 2. $(\cuberoot{a})^3 = (\cuberoot{a'})^3$. 
   \> \> \> Algebra (cube both sides) \\
\> 3. $a = a'$
   \> \> \> Algebra \\
\> 4. QED
   \> \> \> Implication \\
2. QED
\> \> \> \> Contrapositive
\end{tabbing}
To prove surjective, can fix any element of the range and show how to
construct a corresponding element of the domain. \\
(That's enough, because of EG and UG.)
\begin{tabbing}
XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXX\= \kill
Prove: $f$ is surjective, that is, $\forall\; b \in \reals, \exists\; a \in \reals
(\cuberoot{a} = b)$. \\
1. Fix $b \in \reals$. \\
2. Define $a = b^3$. \\
3. $\cuberoot{a} = b$ \\
4. QED
\> \> \> \> EG, UG
\end{tabbing}
Example: \\
$f \from  \nats \to \nats$, $f(n) = n^2$. \\
\\
Show injective, this time using a direct proof \from 
\begin{tabbing}
XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXX\= \kill
Prove: $f$ is injective, that is, $n \neq n' \Rightarrow n^2 \neq
(n')^2$. \\
1. Assume $n \neq n'$. \\
2. $n > n'$ or $n' > n$ 
\> \> \> \> Basic property of $\nats$. \\
3. If $n > n'$ then $n^2 > (n')^2$. 
\> \> \> \> Algebra. \\
4. If $n < n'$ then $n^2 < (n')^2$. 
\> \> \> \> Algebra. \\
5. $n^2 \neq (n')^2$.
\> \> \> \> Cases, 3. and 4. \\
6. QED
\> \> \> \> Implication, 1. and 5.
\end{tabbing}

Not surjective.\\
Show this by exhibiting a particular value that has nothing mapping to
it (go over the quantifier manipulation):
\begin{tabbing}
XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXX\= \kill
Prove: $f$ is not surjective, that is, %
$\neg (\forall\; b \in B, \exists\; a \in \nats, a^2 = b)$ \\ 

1. $\exists\; b \in \nats, \forall\; a \in \nats, a^2 \neq b$. \\
\> 1. $\forall\; a \in \nats [a^2 \neq 3]$. \\
\> \> 1. Fix $a \in \nats$. \\
\> \> 2. $a^2 \neq 3$ \\
\> \> \> 1. Assume $a^2 = 3$. \\
\> \> \> 2. $a$ is not rational. 
         \> Proofs earlier in term. \\
\> \> \> 3. $a \notin \nats$. \\
\> \> \> 4. QED
         \> Contradiction, 1.1.1 vs. 1.1.2.3 \\
\> \> 3. QED
      \> \> UG \\
\> 2. QED 
   \> \> \> EG \\
2. QED
\> \> \> \> Quantifier manipulation
\end{tabbing}

\section{Self Study: Using Functions for Determining Cardinalities}

\begin{theorem}
\label{th:injection}
Suppose $A$ and $B$ are finite sets, $f \from A \to B$. 
\begin{enumerate}
\item
If $f$ is an injection then $|A| \leq |B|$.
\item
If $f$ is a surjection then $|A| \geq |B|$.
\item
If $f$ is a bijection then $|A| = |B|$.
\end{enumerate}
\end{theorem}

\begin{proof}
\begin{enumerate}
\item
Prove by letting $n$ be the number of elements in $A$, and finding $n$
distinct elements of $B$.
\begin{tabbing}
XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXX\= \kill
Prove: $|A| \leq |B|$ \\
1. Define $n \in \nats$, $n = |A|$. \\
   Define $A = \{ a_1, a_2, \ldots, a_n \}$. \\
2. $\forall\; i \in \set{1, \ldots, n}, f(a_i) \in B$ 
\> \> \> \> Definition of function. \\
3. All the $f(a_i)$ are distinct. 
\> \> \> \> Injectivity. \\
4. $|B| \geq n$
\> \> \> \> By 2. and 3. \\
5. QED 
\> \> \> \> Algebra, 1. and 4.
\end{tabbing}

Finiteness assumption used in step 1.\\
Funny situations can arise if sets aren't finite: \\
\\
Consider $f \from  \nats \to$ perfect squares, given by $f(n) = n^2$.\\
$f$ is injective (no 2 have same square).\\ 
But $A$ has all the elements of $B$, and many more.\\
\\
Suggests that $A$ is strictly larger than $B$.\\
Apparent paradox will be resolved in an upcoming lecture on infinite sets.

\item
Prove by letting $n$ be the number of elements in $B$, and finding $n$
distinct elements of $A$.
\begin{tabbing}
XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXX\= \kill
Prove: $|A| \geq |B|$ \\
1. Define $n \in \nats$, $n = |B|$. \\
   Define $B = \{ b_1, b_2, \ldots, b_n \}$. \\
2. $\forall\; b_i \in B, \exists\; a_i \in A, f(a_i) = b_i$ 
\> \> \> \> Surjectivity. \\
3. $\forall\; b_i \in B$, choose $a_i \in A$ such that $f(a_i) = b_i$ 
\> \> \> \> EI \\
4. All the $a_i$ are distinct. 
\> \> \> \> Definition of function. \\
5. $|A| \geq n$
\> \> \> \> By 3. and 4. \\
6. QED 
\> \> \> \> Algebra, 1. and 5.
\end{tabbing}

\item
Could go through the same kind of proofs, but don't have to: \\
Consequence of first two parts of the theorem.
\end{enumerate}
\end{proof}

\subsection{Example: Counting subsets of a finite set}

A counting problem that can be solved by finding a bijection.\\

\begin{definition*}  
The \emph{power set} of a set $A$, denoted by $\power(A)$,
is the set of all subsets of $A$,
that is, $\{ S \mid S \subseteq A \}$.\\
\end{definition*}

Also written sometimes as $2^A$.\\
Looks strange, but we'll see why.\\ 
\\
Example: $A = \{ a_1, a_2, a_3 \}$.\\
$\power(A) = \{ \emptyset, \{ a_1 \}, \{ a_2 \}, \{ a_3 \}, 
\{ a_1, a_2 \}, \{ a_1, a_3 \}, \{ a_2, a_3 \}, \{ a_1, a_2, a_3 \}, \}$.\\
\\
8 elements.

\begin{theorem}
If $A$ is a finite set with $|A| = n$,
then $|\power(A)| = 2^n$.\\ 
\end{theorem}

\begin{proof}
Use bijection to a set we already know has size $2^n$: \\
the set $B$ of $n$-bit binary strings, $B = \{ b_1 b_2 \ldots b_n \mid b_i \in \{
0, 1 \} \}$.\\ 
Then Theorem...will imply $|\power(A)| = 2^n$.\\
\\
Defining bijection $f \from  2^{A} \to B$: \\
\\
Write $A = \{ a_1, a_2, \ldots a_n \}$.\\
\\
Let $f(C)$, where $C \subseteq A$, be the string $b_1 b_2 \ldots b_n$,
where $b_i = 1$ if and only if $a_i \in C$.\\
Use bit $i$ to encode membership of element $a_i$.\\
\\
Examples: \\
Above, if $C = \{ a_1, a_3 \}$, then $f(C) = 101$.\\
If $C = \emptyset$ then $f(C) = 000$.\\
\\
$f$ is a well-defined function~---~it's possible to encode every set in
this way.\\
Claim $f$ is a bijection.\\
Must prove injective and surjective.\\

\noindent Injective:
\begin{tabbing}
XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXX\= \kill
Prove: $f$ is injective, that is, if $C \neq C'$ then $f(C) \neq
f(C')$. \\
1. Assume $C \neq C'$. \\
2. $\exists\; a \in C - C'$ or $\exists\; a \in C' - C$. \\
3. If $\exists\; a \in C - C'$ then $f(C) \neq f(C')$. \\
\> 1. Assume $\exists\; a \in C - C'$. \\
\> 2. Fix $a \in C - C'$. \\.
\> 3. Bit $i$ of $f(C) = 1$. \\
\> \> Bit $i$ of $f(C') = 0$. 
      \> \> Definition of $f$. \\
\> 4. $f(C) \neq f(C')$. \\
\> 5. QED 
   \> \> \> Implication. \\
4. If $\exists\; a \in C' - C$ then $f(C) \neq f(C')$. 
\> \> \> \> Analogous. \\
5. $f(C) \neq f(C')$
\> \> \> \> Cases, 3. and 4. \\
6. QED 
\> \> \> \> Implication. 
\end{tabbing}

\noindent Surjective:
\begin{tabbing}
XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXX\= \kill
Prove: $f$ is surjective, that is, for every length $n$ bit string
$b_1 b_2 \ldots b_n$, \\
$\exists\; C \subseteq A$, such that %
$f(C) = b_1 b_2 \ldots b_n$. \\
1. Fix $b_1 b_2 \ldots b_n$. \\
2. Choose $C = \{ a_i | b_i = 1 \}$. \\
3. $f(C) = b_1 b_2 \ldots b_n$ \\
4. QED
\> \> \> \> EG, UG
\end{tabbing}

\end{proof}

Exercise: Show $\power(A) = 2^n$ another way, by induction on $n$,
without using bijections.

\subsection{Counting numbers of functions}

The ideas involved in counting the number of subsets of a set can be
generalized to help in counting the number of functions from one set
to another: \\
\\
Question: \\
How many different functions are there from finite set $A$ to finite
set $B$? \\
Say $|A| = n$, $|B| = m$.\\
\\
Example: \\
$|A| = 3$, $|B| = 2$.\\
\\
Draw all the possibilities.\\
8 of them.

\begin{theorem}
If $A$ and $B$ are finite sets, with $|A| = n$ and $|B| = m$, then the
cardinality of the set of functions from $A$ to $B$ is $m^n$.
\end{theorem}

\begin{proof}
Use bijection to $M$, the set of length $n$ strings of symbols from
the alphabet $\{ 1, \ldots, m \}$.\\
Use position $i$ to encode the value of $f(i)$.\\
\\
Example: \\
The first function above is encoded by $111$ \\
Second by $121$.\\
Etc.\\
Last is $222$.\\
\\
Prove bijection: \\
\\
Injective: \\
Same rep means same function.\\
Prove by contrapositive, showing different function means different
rep.\\
LTTR.\\
\\
Surjective: \\
Every string encodes some function.\\
LTTR.
\end{proof}

Exercise: \\
What if we wanted to count the number of injective functions from $A$
to $B$? \\
Requires $|B| \geq |A|$, by Theorem...\\
\\
Again, can see this using a bijection with a set of length $n$
strings, but now it's not all the length $n$ strings, but only those
where \emph{no number is repeated}.\\
\\
How many? \\
$m (m-1) (m-2) \cdots (m-n+1)$.\\
\\
Needs $m \geq n$ to make sense.\\
\\
Return to this later.\\
\\
Exercise: \\
Number of surjective functions? \\
Needs $m \leq n$, by Theorem.\\
\\
Bijection with strings of length $n$ in which every element appears at
least once.\\
\\
Will have to come back to this later...(try it).

\section{The Pigeonhole Principle}

\subsection{The theorem}

\begin{theorem}
If $n$ pigeons are put into $m$ holes, $n > m$, then at least one hole
contains two or more pigeons.
\end{theorem}

Actually this isn't really about pigeons and holes.\\
Restate in terms of functions:

\begin{theorem}
\label{cor:pigeon}
Let $A$ and $B$ be finite sets, $|A| > |B|$.\\
If $f \from  A \to B$ 
then there exist distinct elements $a$ and $a'$ in $A$ such that $f(a)
= f(a')$.
\end{theorem}

Why this says the same thing: \\
$A$: pigeons \\
$B$: holes \\
$f$: says where each pigeon gets put

\begin{proof}
In other words, says if $|A| > |B|$ then $f$ is not injective.\\
Follows immediately from Theorem, contrapositive.
\end{proof}

Example: \\
32 people, exist $2$ born on same day of month (1-31).\\
Pigeons: the 32 people \\
Holes:  The 31 days.\\
Rule for putting pigeons in holes: Birth date

\subsection{Example: Divisibility}

Theorem: In every set of 1000 integers, there exist two, $x$ and $y$,
such that $x-y$ is divisible by 699.\\
\\
Seems hard.\\
\\
Use Pigeonhole: \\
Try 1000 pigeons and 699 holes: \\
Pigeons:  the 1000 integers \\
Holes: ? \\
Rule: ? \\
\\
We would like to arrange things so that $x$ and $y$ in same hole
implies that $699$ divides $x-y$.\\ 
How? \\
\\
Holes: numbers $0,1,\ldots,698$ \\
\\
Rule: Integer $x$ goes into hole $r$ if $r$ is the remainder when $x$
is divided by 699.\\
\\
Pigeonhole principles says some two integers $x$ and $y$ must have the
same remainder mod 699.\\
$x \bmod 699 = y \bmod 699$.\\ 
$699$ divides $x - y$.\\ 
\\
Works for any $m, n$, $m < n$, not just 699 and 1000.\\

\subsection{Example: Weighing Balls}

Given 12 balls, know that 11 are same weight and one is different.\\
May be heavier or lighter.\\
Want to discover which is the odd ball, and if it's heavy or light.\\
\\
Do by weighings of a balance scale.\\
Can do in 3 weighings.\\
\\
Can solve by algorithm, represent with tree: \\
(Draw part, go over.)

\begin{figure}
\centerline{\includegraphics[height=2.0in]{figures/weighing}}
\caption{A strategy for the weighing problem can be represented by a
  ternary tree.  Each internal node represents a weighing.  Each leaf
  node represents a result.  A run of the algorithm corresponds to a
  path from the root to a leaf.  At each internal node, we perform the
  weighing associated with the node and descend to a child based on
  the result.  At a leaf, we output the indicated result.}
\label{fig:weighing}
\end{figure}

Example: \\
Prove impossible to solve with 14 balls, 3 weighings.\\
\\
Pigeons: \\
Possible initial situations: 1L, 2L, .\\.. 14L, 1H, 2H, ...14H \\
28 situations \\
\\
3 comparisons yields height 3 tree, with 3 children for each internal
node.\\
\\
27 leaves.\\
\\
Holes: \\
The 27 leaves \\
\\
Rule: \\
Map each initial situation to the leaf it reaches.\\
\\
Pigeonhole principle says exist two initial situations leading to the
same leaf.\\
But leaf has only one decision.\\
So the two situations give the same answer, wrong in at least one
case.\\
\\
Example: \\
5 weighings, 122 balls \\
Yields 244 situations, 243 leaves, same problem, impossible.\\
\\
Example: \\
5 weighings, 121 balls \\
Yields 242 situations, 253 leaves, so ??? \\
\\
Well, Pigeonhole doesn't rule this out, but it also doesn't tell us
it's possible.\\
For that, we'd have to construct an algorithm.\\
LTTR \\
\\
For here, consider easier case: \\
\\
Example: 3 weighings, 13 balls \\
26 situations, 27 leaves, so Pigeonhole doesn't say impossible.\\
\\
But it turns out there's still no algorithm.\\
Reasons involve more detailed analysis: \\
Proof by casees, based on first weighing.\\
\\
First weighing can put some number $n = 1, 2, 3, 4, 5, 6$ on each pan.\\
\\
$n=1$: \\
11 balls not used.\\
If first weighing comes out equal,
leaves 22 possible situations.\\
But only 2 weighings (9 leaves, could distinguish at most 9 situations).\\
\\
$n=2, 3, 4$: \\
Same argument.\\
$n = 4$ leaves 5 balls unused, 10 situations.\\
\\
$n=6$: \\
If unbalanced, have 12 situations left (one of 6 L or one of other 6 H).\\
Too many.\\
\\
$n = 5$: \\
Same argument.\\
\\
%[[[5 weighings, 121 balls impossible.\\
%Cases based on first weighing.\\ If at most 40 on each pan, and =, have
%41 balls left, 82 situations, but only 81 remaining leaves.\\
% If at least 41 on each pan, and come out unequal, then again at
% least 82 remaining situations.\\

\subsection{Binary search}

Random (living) person in the world is chosen randomly, by game
server.\\
Players ask yes/no questions to discover who it is.\\
Fewest questions wins.\\
HM questions needed? \\
\\
Model game as a tree (draw) \\
\\
Max number of questions is max length path in tree.\\
Need each person alone at some leaf.\\
\\
Binary, so need height at least $\lceil log_2(N) \rceil$, where $N$ is number
of people (about 6 billion?).\\
About 32 questions? \\
\\
Is this sufficient? \\
Yes.\\
Unlike in weighing example, where questions were of a constrained
form, here we can ask anything we like.\\
E.g., order everyone in the world alphabetically, or some other way.\\
Ask if in first half or second, split in half repeatedly.\\
Boring questions, but does work in $\lceil log_2(N) \rceil$.\\
\\
Leads to binary search algorithm to find an element in a sorted list,
w.r.t. a total order.\\
Compare with middle element, and let result tell whether to proceed to
look (recursively) in the top or bottom piece.\\
Uses $\lceil log_2(N) \rceil$ comparisons.\\
\\
Can also show that this is approximately optimal (fudge factor because
of the = case).\\

\subsection{Example: Subsets of a List of Numbers}

Show that any given $10$ distinct positive numbers less than $100$, that two completely
different subsets sum to the same quantity.

The numbers all vary between $1$ and $99$.  Therefore the maximum sum
of any $10$ chosen numbers is $90 + 91 + 92 + \ldots 99 = 945$. 
The number of different subsets of the $10$ numbers is $2^{10} - 1$ (excluding
the null set) $= 1023$. We have $1023$ pigeons and $945$ holes. Using the
pigeonhole principle, we can argue that two different subsets map to the same
sum.  If these subsets have a common number or numbers, we can always remove the
common numbers to produce two completely different subsets that sum to the
same quantity.


\end{document}


