\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

\newcommand{\rem}{\textup{ rem }}

\begin{document} 
\inclassproblems{11, Mon.}

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

\begin{problem}
For each part below, write a couple sentences describing a bijection
between the two sets mentioned.  The existence of such a bijection
proves that the two sets are the same size.

{\em Everyone in your group should write out complete answers---
you'll all benefit from the practice!}

\bparts

\ppart Describe a bijection between the set of $30$-bit sequences with
10 zeros and 20 ones and paths from $(0, 0)$ to $(10, 20)$ consisting
of right-steps (which increment the first coordinate) and up-steps
(which increment the second coordinate).

\solution[\vspace{1.25in}]{Map the 30-bit sequence $b_1 b_2 \ldots
b_{30}$ to a path where the $i$-th step is right if $b_i = 0$ and up
if $b_i = 1$.}

\ppart Find a bijection between the set of $n$-bit sequences and the
set of all subsets of $\set{x_1, x_2, \ldots, x_n}$.

\solution[\vspace{1.25in}]{Map the $n$-bit sequence $b_1 b_2 \ldots
b_n$ to a subset that contains $x_i$ if and only if $b_i = 1$.}

\ppart Mr. and Mrs. Grumperson have collected 13 identical pieces of
coal as Christmas presents for their beloved children, Lucy and Spud.
Describe a bijection between the set of all ways of distributing the
13 coal pieces to the two children and the set of 14-bit sequences
with exactly 1 one.

\solution[\newpage]{Map a distribution in which Lucy get $l$ pieces
and Spud gets $s$ pieces to a 14-bit sequence with $l$ zeros, a one,
and then $s$ zeros.}

\ppart On Christmas Eve, Mr. and Mrs. Grumperson remember that they
have a third child, little Bottlecap, locked in the attic.  Describe a
bijection between the set of all ways of distributing the 13 coal
pieces to the three children and the set of 15-bit sequences with
exactly 2 ones.

\solution[\vspace{1.25in}]{Map a distribution in which Lucy gets $l$
pieces, Spud gets $s$ pieces, and Bottlecap gets $b$ pieces to a
15-bit sequence with $l$ zeros, a one, $s$ zeros, a one, and $b$
zeros.}

\ppart On reflection, Mr. and Mrs. Grumperson decide that each of
their three children should receive {\em at least two} pieces of coal
for Christmas.  Describe a bijection between the set of all ways of
distributing the 13 coal pieces to the three Grumperson children given
these constraints and the set of 9-bit sequences with exactly 2 ones.

\solution[\vspace{1.25in}]{Map a distribution in which Lucy gets $l
\geq 2$ pieces, Spud gets $s \geq 2$ pieces, and Bottlecap gets $b
\geq pieces$ to a 9-bit sequence with exactly $l - 2$ zeros, a one, $s
- 2$ zeros, a one, and $b - 2$ zeros.}

\ppart Describe a bijection between the set of 110-bit sequences with
exactly 10 ones and solutions over the natural numbers to the
equation:

\begin{eqnarray*}
x_1 + x_2 + \ldots + x_{10} & \leq & 100
\end{eqnarray*}

\solution[\vspace{1.25in}]{Let $x_1$ be the number of zeros before the
first 1, $x_2$, be the number of zeros between the first and second 1,
etc.  Note that zeros after the tenth 1 do not contribute to the value
of any of the variables $x_1, \ldots, x_{10}$; this allows us to count
solutions to the inequality ($\leq 100$) rather than the equality ($=
100$).}

\ppart Describe a bijection between solutions to the inequality in the
preceding problem part and weakly increasing sequences of the form:

\[
0, y_1, y_2, y_3, y_4, y_5, y_6, y_7, y_8, y_9, y_{10}, 100
\]

\solution{Let $y_i = x_1 + \ldots + x_i$ for each $i$ from 1 to 10.}

\eparts

\end{problem}

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

\instatements{\newpage}

\begin{problem}
Solve the following problems using the pigeonhole principle.  For each
problem, try to identify the {\em pigeons}, the {\em pigeonholes}, and
a {\em rule} assigning each pigeon to a pigeonhole.

\bparts

\ppart In a room of 500 people, there exist two who share a birthday.

\solution[\vspace{2.5in}]{The pigeons are the 500 people.  The
pigeonholes are 366 possible birthdays.  Map each person to his or her
own birthday.  Since there 500 people and 366 birthdays, some two
people must have the same birthday by the Pigeonhole Principle.}

\ppart Every MIT ID number starts with a 9 (we think).  Suppose that
each of the 75 students in 6.042 sums the nine digits of his or her ID
number.  Must two people arrive at the same sum?

\solution[\vspace{2.5in}]{Yes.  The students are the pigeons, the
possible sums are the pigeonholes, and we map each student to the sum
of the digits in his or her MIT ID number.  Every sum is in the range
from $9 + 8 \cdot 0 = 9$ to $9 + 8 \cdot 9 = 81$, which means that
there are 73 pigeonholes.  Since there are more pigeons than
pigeonholes, there must be two piegons in the same pigeonhole; in
other words, there must be two students with the same sum.}

\ppart In every set of 100 integers, there exist two whose difference
is a multiple of 37.

\solution{The pigeons are the 100 integers.  The pigeonholes are the
numbers 0 to 36.  Map integer $k$ to $k \rem 37$.  Since there are 100
pigeons and only 37 pigeonholes, two pigeons must go in the same
pigeonhole.  This means $k_1 \rem 37 = k_2 \rem 37$, which implies
that $k_1 - k_2$ is a multiple of 37.
}

\eparts

\end{problem}

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

\instatements{\newpage}

\begin{problem} \textbf{(challenge)}  Notice that a set consisting of
powers-of-two has distinct subset sums.  For example, every subset of:

\[
\set{1, 2, 4, 8, 16, 32, 64}
\]

has a distinct sum.  Based on this example, a natural conjecture is
that the largest number in a set of $n$ positive integers with distinct
subset sums must be at least $2^{n-1}$.

\bparts

\ppart (do-able) Prove that this conjecture is {\em false}.

\solution[\vspace{3in}]{
One counterexample is:

\[
\set{3, 5, 6, 7}
\]
}

\ppart (research problem) How small can you make the largest number in
an $n$-element set with distinct subset sums?

\solution{
The best known bounds are:

\[
\frac{2^n}{4 \sqrt{n}} \leq \text{largest \#} \leq 0.22002 \cdot 2^n
\]

where the upper bound holds for all sufficiently large $n$.  In 1931,
Erd\"{o}s conjectured that the largest number must be at least $c
\cdot 2^n$ for some $c$ and offered \$500 for a proof or disproof.
Neither has yet been found.}

\eparts

\end{problem}

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

\end{document}
