\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$.  

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 (pigesons)
that appear in the same column (hole), 
leaving $kn-1$ remaining  columns (holes) for $kn+k-2$ 
remaining numbers (pigesons). 
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
Explain why an integer between 2 and 100 is prime if and only if either
(a) it is a prime less than 10, or
(b) no prime less than 10 divides it.

Now use the Inclusion-Exclusion Principle to compute the number
of primes less than 100.
(You may know other methods that will answer this question faster,
but if we replaced 100 by 1,000,000, this method would win.)

\solution

First of all the reason that conditions (a) and (b) include all
primes between 2 and 100 is that any number $n$ is a prime
if for all $1<d\leq \sqrt{n}$, $d$ does not divide n.

Thus, all prime divisors of composite numbers less than a 100,
must be less than $\sqrt{100}=10. Or, said differently,
if no prime less than 10 divides a
number less than a 100, then it must be prime. Of course, this
precluded the primes less than 10 (as they are divisible by themselves)
so we must add them explicitly with condition (a).

Using Inclusion-Exclusion principle, consider the following sets.
$S_0 = \{\mbox{ primes greater than 2 and less than 10}\} = \{2,3,5,7\}$,
$S_1 = \{\mbox{ numbers less than 100 divisible by 2 }\}$,
$S_2 = \{\mbox{ numbers less than 100 divisible by 3 }\}$,
$S_3 = \{\mbox{ numbers less than 100 divisible by 5 }\}$,
$S_4 = \{\mbox{ numbers less than 100 divisible by 7 }\}$.

\end{problems}
\end{document}


\end{problems}

\end{document}
