\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
%\usepackage{graphicx}
\input{/pub/www/classes/6.042/fall99/inputs/macros-course}
\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}
\newcommand{\depth}{\mbox{depth}}
\newcommand{\height}{\mbox{height}}
\newcommand{\lcm}{\mbox{lcm}}

\begin{document}

\tutprobn{7}{10/1/99}{October 1st, 1999}

\begin{problems}

\problem 
Let $[n]$ denote the set $\{1,2,\ldots,n\}.$


(a) Show that any subset of $[2n]$ with $n+1$ elements
contains two numbers that sum to $2n+1$.  

\solution

Combine the elements of $[2n]$  in pairs as follows
$S= \{(1,2n), (2,2n-1),..., (n,n+1)\}$. 
Note that for each pair $(i,j)$ of elements in $S$
$i+j =2n+1$.
Any subset of $[2n]$ including $n+1$ elements,
must include both elements of a pair for at least one pair in $S$.
Take any such pair, then the sum of its elements is $2n+1$.

(b) Show that any subset of $[4n]$ with $3n+1$ elements
contains four numbers that sum to $8n+2$.  

\solution

Combine the elements of $[4n]$  in pairs  as follows
$S= \{(1,4n), (2,4n-1,),..., (2n,2n+1)\}$. 
Note that $S$ includes $2n$ pairs and
for each pair $(i,j)$ of elements in $S$
$i+j =4n+1$.
Any subset of $[4n]$ including $3n+1$ elements,
must include both elements of at least $n+1$ pairs in $S$.
Take any such pair, then the sum of its elements is $4n+1$.
Take any two such pairs, which include 4 numbers elements from the original
set $[4n]$, and the sum of these 4 numbers is $8n+2$.

(c) State and prove a general theorem along these lines.


\solution

We will prove the following theorem.  The first two statements are 
special cases when $k=1$ and $k=2$.  (Notice that our theorem actually
gives a better bound for $k=2$:  $2n+2$ rather than $3n+1$.)
\thm
For any integer $k\geq 1$, any subset of $[2kn]$ with $kn+k$ elements
contains $2k$ numbers that sum to $2k^2n+k$.
\end{theorem}
\pf
Consider the following listing of the numbers 1 to $2kn$ in a
snake-like order.
\[
\begin{array}{c c c c c c c}
1 & 2 & 3 & \cdots & kn-2 & kn-1 & kn \\
2kn & 2kn-1 & 2kn-2 & \cdots & kn+3 & kn+2 & kn+1
\end{array}
\]
There are $kn$ columns in this table. In each column there are
two elements $(i,2kn-i+1)$. The sum of the elements in
each colum is $2kn+1$. 

Now, any set of 
$kn+k$ numbers from $[2kn]$ must choose both numbers
from at least $k$ columns.

Formally, this follows by repeated applications of the 
pigeonhole principle:  we must have two numbers (pigeons)
that appear in the same column (hole), 
leaving $kn-1$ remaining  columns (holes) for $kn+k-2$ 
remaining numbers (pigeons). 
We can repeat this argument on the remaining columns and numbers 
as long as the numbers outnumber the columns.  Since the difference
between the numbers and the columns decreases by one at each step,
we can repeat for $k$ steps.

Each column sums to $2kn+1$, so the sum over $k$ pairs each appearing
pairwise in the same columns is~$k(2kn+1)$.
\end{proof}




\problem

An integer between 2 and n is prime if and only if either
(a) it is a prime less than $\sqrt{n}$, or
(b) no prime less than $\sqrt{n}$ divides it.

1. Explain why is the above characterization true.

\solution

The reason that conditions (a) and (b) include all
primes less than $n$ is that any number $m<n$ is a prime
if for all $1<d\leq \sqrt{m} <  \sqrt{n}$, $d$ does not divide $m$.

Thus, all prime divisors of composite numbers less than  $n$,
must be less than $\sqrt{n}$, and if a number is not
divisible by all primes less than $\sqrt{n}$ it must itself
be a prime.  However, (b) alone, would include as non-primes also
those primes less than $\sqrt{n}$ ( as they are divisible by themselves)
so we must add them explicitly to the list of primes
with condition (a).


2. 
Use the above characterization 
and 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

Using Inclusion-Exclusion principle, consider the following sets.
$$S_0 = \{\mbox{ primes less than 5 }\} = \{2,3\}$$
$$S_1 = \{\mbox{ numbers less than 25 divisible by 2 }\}$$
$$S_2 = \{\mbox{ numbers less than 25 divisible by 3 }\}$$.

Now, by using inclusion-exclusion, the number of
integers less than 25 (and greater than 1) which 
are divisible by either 2 or 3
are $|S_1 | + |S_2| - |S_1\cup S_2 | = 12 + 8 - 4 = 16$.

So, the number of integers less than 25 (and greater than 1)
which are divisible by niether 2 or 3 are 23-16=7, and 
finally,  the total number of primes less than 25 by the
above characterization is: 
$$|S_0 | + \mbox{ those not divisible by 2 or 3}= 9$$


\problem

In a city with more then one road, prove that there must be at least
two roads A and B s.t. the number of roads that cross with road A is
the same as the number of roads that cross with road~B.

\solution

It's a straightforward application of the pigeonhole principle.  Say
that there are $n$ roads in this city.  For every road X, the number
$c(X)$ of roads that it crosses must be an integer from $0$ to $n-1$.
If no two roads had the same number of crossings, then function $c$
must take every value $0,\ldots,n-1$ exactly once.  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.


\end{problems}
\end{document}

