\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{\onetwo}[1]{\set{1,2,\dots,#1}}

\begin{document}

\tutn{7}{10/1/99}{October 1, 1999}

\begin{problems}

\problem

In a city with more then one road, prove that there must be at least two
roads which are crossed by the same number of other roads.

\solution{
A straightforward application of the pigeonhole principle.  Say that there
are $n$ roads in this city.  Since no road can cross itself, the number of
roads which cross any given road must be an integer from $0$ to $n-1$.  If
no two roads had the same number of crossings, then for every one of these
$n$ numbers, there must be some road crossed that number of times.  But
that would mean that some road crosses $0$, i.e., no roads, while some
road crosses $n-1$, i.e., all the other roads.  This is a contradiction.}

\problem

We observe that an integer strictly between 1 and n is prime if and only if either
\begin{enumerate}
\item\label{a} it is a prime less than $\sqrt{n}$, or
\item\label{b} no prime less than $\sqrt{n}$ divides it.

\end{enumerate}

\bparts

\ppart Explain why is the above observation true.

\solution{
Let $m$ be the integer strictly between 1 and $n$.

If Condition~\ref{a} holds then $m$ is a prime, trivially.

Condition~\ref{b} also implies that $m$ is prime.  To prove this, suppose
$m$ is not prime; then it must be the product of two natural numbers $>
1$.  Since their product equals $m < n$, both factors can't be $\geq
\sqrt{n}$.  Whichever of the factors is $< \sqrt{n}$ must also have a
prime divisor (possibly itself) which is $< \sqrt{n}$, and this small
prime is a divisor of $m$, contradicting Condition~\ref{b}.

Conversely, if $m$ is prime, Condition~\ref{a} immediately holds when $m <
\sqrt{n}$ and Condition~\ref{b} immediately holds otherwise.}

\ppart Use the observation above along with the Inclusion-Exclusion
Principle to compute the number of primes less than $n=25$.  (You may know
other methods that will answer this question faster, but if we replaced 25
by 1,000,000, this method would win.)

\solution{
Consider the following sets:
\begin{eqnarray*}
S_0 & ::= & \set{\mbox{primes less than } \sqrt{25}} = \set{2,3},\\
S_1 & ::= & \set{\mbox{even numbers strictly between 1 and 25}},\\
S_2 & ::= & \set{\mbox{numbers divisible by 3 strictly between 1 and 25}}.
\end{eqnarray*}
There are $\ceil{23/2} = 12$ numbers in $S_1$, $\ceil{23/3} = 8$ numbers
in $S_2$, and $\ceil{23/(2 \cdot 3)} = 4$ numbers in $S_1 \cap S_2$.
Now, by Inclusion-Exclusion, the number of integers strictly between 1 and
25 which are divisible by either 2 \emph{or} 3 is
\[
\card{S_1 \cup S_2} = \card{S_1} + \card{S_2} - \card{S_1\cap S_2} = 12
+ 8 - 4 = 16.
\]

Now according to the observation above, the primes less than 25 are the
numbers strictly between 1 and 25 which are not in $S_1 \cup S_2$
along with the primes in $S_0$.
So, the number of primes is
\[
\card{S_0} + (\card{\set{2,3,\dots,24}} - \card{S_1 \cup S_2}) = 2 + (23-16) = 9.
\]
}
\eparts


\problem 
Let $n$ be a positive integer.

\bparts

\ppart Show that any subset of $\onetwo{2n}$ with $n+1$ elements
contains two numbers that sum to $2n+1$.  

\solution{
Combine the elements of $\onetwo{2n}$ in pairs as follows
\[\mbox{holes}::= \set{(1,2n), (2,2n-1),..., (n,n+1)}.
\]
Note that every number in $\onetwo{2n}$ appears in exactly one hole, and the
sum of the numbers in each of the $n$ holes is $2n+1$.  Now consider any
subset, $\mbox{pigeons} \subseteq \onetwo{2n}$ of size at least $n+1$.
Assign each pigeon to the hole in which it appears.  Since there are more
pigeons than holes, at least two pigeons $i,j$ with $i < j$ must share a
hole.  That is, $(i,j)$ is a hole, so $i$ and $j$ are two pigeons whose
sum is $2n+1$.}

\ppart Show that any subset of $\onetwo{4n}$ with $3n+1$ elements
contains four numbers that sum to $8n+2$.  

\solution{
As in the solution of the previous part, combine the elements of
$\onetwo{4n}$ in pairs as follows:
\[
\mbox{holes}::= \set{(1,4n), (2,4n-1,),..., (2n,2n+1)}.
\]
Note that every number in $\onetwo{4n}$ appears in exactly one hole, and the
sum of the numbers in each of the $2n$ holes is $4n+1$.  Now consider any
subset, $\mbox{pigeons} \subseteq \onetwo{4n}$ of size at least $3n+1$.
Assign each pigeon to the hole in which it appears.  Since there are $n+1$ more
pigeons than holes, and at most two pigeons appear in any hole, there must
be $n+1 \geq 2$ holes fully occupied by two pigeons.  Take the four
elements in two of the fully occupied holes.  Since the sum of the two in
each hole is $4n+1$, the sum of the four is $8n+2$.}

\ppart State and prove a general theorem along these lines.

\solution{
We will prove the following:
\begin{theorem*}
For all positive integers $n,k$, every subset of $\onetwo{2kn}$ with
$kn+k$ elements contains $2k$ numbers that sum to $2k^2n+k$.
\end{theorem*}

The results of the two previous parts of this problem are special cases of
this theorem for $k=1,2$.  In fact, for $k=2$, the theorem actually gives
a better bound: $2n+2$ rather than $3n+1$.

\pf
As in the solution of the previous part, combine the elements of
$\onetwo{2kn}$ in pairs as follows:
\[
\mbox{holes}::= \set{(1,2kn), (2,2kn-1,),..., (kn,kn+1)}.
\]
Note that every number in $\onetwo{2kn}$ appears in exactly one hole, and the
sum of the numbers in each of the $kn$ holes is $2kn+1$.  Now consider any
subset, $\mbox{pigeons} \subseteq \onetwo{2kn}$ of size at least $kn+k$.
Assign each pigeon to the hole in which it appears.  Since there are $k$ more
pigeons than holes, and at most two pigeons appear in any hole, there must
be $k$ holes fully occupied by two pigeons.  Take the $2k$
elements in $k$ of the fully occupied holes.  Since the sum of the two in
each hole is $2kn+1$, the sum of the $k$ is $k(2nk+1)$.
\end{proof}
}

\eparts


\end{problems}
\end{document}

