\documentstyle[12pt]{article}
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}
\newcommand{\mod}{ \mbox { mod }}

\begin{document}

{\bf Tutorial 2 solutions. }

\date{}
 
\begin{enumerate}
\item {\em Handshakes. } I recently went to a party with my spouse; there were 11 other
married couples there.  A lot of handshaking happened (but of course
no one shook hands with their spouse).  At the end, it turned out that
for every $k$ from $0$ to $22$, someone other than me had shaken hands
with exactly $k$ people.  How many people did I shake hands with?
Prove your answer.

Note that there are 24 people (12 couples)in this case.

We will prove the following for a set of $n$ couples:
\begin{theorem}
Suppose at a party for $n$ couples (total) it turns out that
someone other than me has shaken $k$ hands for every $k$ from $0$ to $2n-2$. 
Then I must have shaken $n-1$ hands.
\end{theorem}

{\em Proof.}
By induction on $n$.

I.H. $P(n)$ : At an $n$ couple party, if someone other than me shakes $k$ 
hands 
for every $k$ from $0$ to $2n-2$ then I must have shaken $n-1$ hands.

Base: $n=1$. There are no other couples. My wife has shaken $0$ hands
(can't shake with me). I have shaken $0$ hands ($=n-1$). (some party!)

I.H. Assume $P(n-1)$ is true. To prove $P(n)$, 
consider a party with $n$ couples. 

Someone has shaken $2n-2$ hands, i.e., with everyone in the room
except themselves and their spouse. Therefore everyone else but this
couple has shaken hands at least once. So the one who hasn't shaken hands
at all must be this person's spouse. $2n-2$ is paired with $0$. 
Consider the subparty of the remaining $n-1$ couples. I must be in this
group since there cannot be two people who shook hands $2n-2$ times or $0$
times. Consider the
number of times this group of people has shaken hands among themselves,
i.e., not counting handshakes with the $2n-2, 0$ couple. Then the 
number of handshakes I see is every number between $0$ and $2n-4$. This 
is because this group of people has original handshake counts of $1,2,3,\ldots,
2n-3$. Since everyone shakes the $2n-2$
person's hand once, we are left with handshake counts of $0,1,\ldots,2n-4$. 
This
is exactly the premise of $P(n-1)$. So by the I.H. I must have shaken
$n-2$ hands within this group. Adding the one handshake with
the $2n-2, 0$ couple, I must have shaken a total of $n-1$ hands.
\qed

For $n=12$, the answer is that I shook 11 hands.
 
\item {\em Geometric mean vs Arithmetic mean. }  Show that for any real numbers $x_1,x_2,\ldots,x_n$,
$$(x_1x_2\ldots x_n)^{\frac{1}{n}} \leq \left( x_1 + x_2 + \ldots + x_n \over n \right) $$ 
\end{enumerate}

By strong induction on n.

          Notation: $ AM(x_1\ldots x_n) = \frac{x_1+..+x_n}{n}$
   
   Ind. Hyp.   $(x_1x_2\ldots x_n) \leq  (AM(x_1,..,x_n) )^n$               
   
   Base case. $n=1$:  $x_1 \leq x_1$.

   $ n=2$:    $4x_1x_2  \leq (x_1+x_2)^2$

           or  $0 \leq (x_1-x_2)^2$   which is true.


   Ind step. Assume $P(1) \wedge P(2) \wedge \ldots \wedge P(n-1)$ is true
to prove $P(n)$.We will prove $P(n)$ separately for odd values of $n$ and 
even values of $n$.

 \begin{enumerate}        
    \item $n$ is even.

         Then,
$$ (x_1x_2\ldots x_n) = (x_1x_2\ldots x_{n/2})(x_{n/2 +1}x_{n/2+2}\ldots x_{n})$$
$$ \leq  AM(x_1..x_{n/2})^{\frac{n}{2}} AM(x_{n/2 +1}..x_{n})^{\frac{n}{2}}$$
Using $P(\frac{n}{2})$,
$$ \leq  [AM(x_1..x_{n/2}) AM(x_{n/2 +1}..x_{n})]^\frac{n}{2} $$
$$ \leq [(AM(x_1..x_{n/2})+ AM(x_{n/2 +1}..x_{n}))/2]^n $$                      
(from $P(2)$) 
 $$\leq [AM(x_1..x_{n})]^n$$

       
    \item  $n$ is odd.  Then we show that 

          $$P(\frac{n+1}{2}) \rightarrow P(n+1) \rightarrow P(n)$$.
    
         Assume $n \geq 2$. Then $\frac{n+1}{2} < n$ and hence
we can assume from the I.H. that $P(\frac{n+1}{2})$ is true.
The proof of the first implication is then identical to earlier case.

          To show $P(n+1) \rightarrow P(n)$,

        Start with P(n+1).  
Let $x_{n+1} = {x_1 + x_2 +\ldots + x_n \over n}$. This implies 
$x_{n+1} = {x_1+\ldots +x_{n+1} \over n+1}$. Which means that
$AM(x_1,\ldots,x_n) = AM(x_1,\ldots,x_{n+1})$ for this choice of $x_{n+1}$.
         
        Then $P(n+1)$ is
         $$x_1x_2\ldots x_nx_{n+1} \leq AM(x_1,\ldots,x_{n+1})^{n+1}$$
Dividing both sides by $x_{n+1}$ we have:
         $$x_1x_2\ldots x_n \leq  AM(x_1, \ldots x_{n+1})^n$$
                  $$= AM(x_1, \ldots x_n)^n$$

\end{enumerate}
\end{document}
