\problemdata                                                             
        {Consecutive Integers} % latex-friendly label for the prob.
        {Pigeonhole Principle} % The topic(s) of the problem content.  
        {The Theory of numbers by Niven..., page 208} % Source (if known)
	{S01 Quiz 2, 4} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
Let \emph{S} be any set of $2n+1$ integers selected from $1, 2,
\dots, 3n$.
\begin{problemparts}

\problempart Prove that there must be three consecutive integers that are
in the set \emph{S}.

\solution{ 
Let the $n$ successive triples of consecutive integers
$(1,2,3),(4,5,6),(7,8,9) \dots (3n-2,3n-1,3n)$ be the holes.  Assign each
pigeon to the hole in which it occurs.  Since there are more than twice as
many pigeons as holes, three pigeons must occupy one hole, say
$(k,k+1,k+2)$.  These are three consecutive pigeons.}

%\vspace*{3.5in}
\problempart Show that among any set of $2n+1$ integers selected from
$1, 2, \dots, 3n$, there must be two that are relatively prime and one of
these two is divisible by three.

\solution{ 
Of any three consecutive integers $(k,k+1,k+2)$, one must be divisible by
three.  Say it is either $k$ or $k+1$.  Now there are no common divisors of
$k$ and $k+1$, because if $k+1$ was divided by any divisor of $k$ there
would be a remainder of 1.  So in this case, $k$ and $k+1$ are the desired
two relatively prime pigeons, and one of them is divisible by three.  If
neither $k$ nor $k+1$ is divisible by three, then $k+2$ must be divisible
by three, so in this case, by the same reasoning, $k+1$ and $k+2$ will be
the desired two pigeons.

\paragraph{Comments:}
\begin{itemize}
\item Many people didn't realize that they needed to use the generalized pigeonhole principle in this problem, and thought that, since you have $2n+1$ holes, you must somehow figure out what the $2n$ pigeons are. 
\item Others didn't know how to apply the generalized pigeonhole principle: If you have $n$ holes and $n+1$ pigeons, there must be at least one hole with 2 pigeons. If you have $n$ holes and $2n+1$ pigeons, you will have at least one hole with $3$ pigeons. In general, if you have $H$ holes and $P$ pigeons, you're guaranteed to have at least one hole with $\lceil \frac{P}{H}\rceil$ pigeons. In this problem, you needed to argue that 3 pigeons would end up in the same hole, which would imply that there are 3 consecutive numbers. So, since you have $2n+1$ pigeons, you needed to figure out what the $n$ holes were.
\item Several people resorted to some kind of ``proof by example'', bypassing a pigeonhole argument altogether. That is, they argued something like: ``the only way you can avoid having 3 consecutive numbers is by leaving out every third number, like this: $\fbox{12}~3~\fbox{45}~6~\fbox{78}~9 \ldots n$''. Such proofs are not acceptable because they do not consider possible alternatives. If you want to claim that this is the only way you can do it, you have to \emph{prove} it first. Proofs ``by intimidation'' or ``by emphatic assertion'' are not accepted in this class. You'll need to wait until you start producing published papers before you start using those.
\item Several others tried to correlate this problem to some of the pigeonhole problems we've seen in the problem sets and tutorials, and defined the holes as the numbers modulo 3, or wrote each number as $a\cdot 3^b$ and tried to derive something from there. These techniques did not work here, since the problem was asking for something completely different.
\item In part (b), many failed to realize that the results from part (a) could be used in part (b). Moreover, many did not notice that the question was asking for two numbers that are relatively prime and one of \emph{those two} is a multiple of 3. So they went on to prove these two things independently (that is, prove the existence of two relatively prime numbers, and then prove the existence of a multiple of 3). 
\item Pigeons is not spelled ``pidgeons'', despite the fact that the second spelling has received the majority vote of the students.

\end{itemize}
}


\end{problemparts}
\end{problem}                                 