\problemdata      
        {?} % latex-friendly label for the prob.
        {Counting} % The topic(s) of the problem content.
        {new problem from Zhang Lizhao at Dept of Math Oct 22, 2001; revised by ARM 10/24/01} % Source (if known)
        {F01, PS9} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).

\begin{problem}
There are $n$ students attending their first 6.042 tutorial.  The
TA starts things off by asking everybody to shake hands with everybody
else in the tutorial, including herself.  The TA makes a peculiar
observation: the number of boy-boy handshakes, plus the number of
girl-girl handshakes, happens to equal the number of boy-girl handshakes.
She also also notices that $n+1$ is a perfect square.  Having thoroughly
mastered the 6.042 curriculum, she realizes that $n+1$ must be a perfect
square whenever the numbers of boy-boy, girl-girl, and boy-girl handshakes
are related in this way.  Explain how the TA could have reached this
conclusion.

\solution{Let $b$ be the number of boys, and $g$ the number of girls
(including the TA), so $b+g=n+1$.  The condition says
\begin{align*}
\binom{b}{2} + \binom{g}{2}& = bg, & \text{so}\\
b(b-1) + g(g-1)& = 2bg\\
b^2 -b +g^2 -g& = 2bg\\
b^2 -2bg +g^2& = b+g\\
(b-g)^2& = n+1.
\end{align*}
So indeed, $n+1$ is a perfect square.
} 

\end{problem}
