\problemdata                                                             
        {set of n+1 - two divide each other} % latex-friendly label for the prob.
        {Pigeonhole} % The topic(s) of the problem content.  
        {Proofs from THE BOOK} % Source (if known)                                          
        {S01 Tutorial 7, 4} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
\begin{problemparts}

  \problempart %
  Let $A$ be any set of $n+1$ numbers from the set $\set{1, 2, \ldots,
    2 n}$.  Prove that there are always two numbers in $A$ such that
  one divides the other.

  \solution{%
    Ref. ``Proofs from THE BOOK''.

    We use the pigeonhole principle as follows: Let any number of $A$,
    $a$, be represented in the form $a = 2^k m$, where $m$ is an odd
    number between $1$ and $2n-1$.  Since there are $n+1$ numbers in
    $A$k but only $n$ different odd parts, there must be two numbers
    in $A$ with the same odd part.  Hence, one is a multiple of the
    other.
    %
    }

  \problempart %
  Let $A$ be any set of $n$ numbers from the set $\set{1, 2, \ldots, 2
    n}$.  Prove that there are \textbf{not} always two numbers in $A$
  such that one divides the other.

  \solution{%
    Ref. ``Proofs from THE BOOK''.

    Consider the set $A = \set{n+1, n+2, \ldots, 2n}$.  In this case,
    the smallest number $n+1$ could not possibly divide the others
    because it can not divide even the largest number $2n$ (unless $2n
    = n+1$, which is only true for $n = 1$), since $2(n+1) > 2n$.  It
    follows, that none of the numbers can divide any of the other
    numbers.
    %
    }

\end{problemparts}

\end{problem}
                                 