\documentclass[12pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsfonts}
\usepackage{geometry}
\usepackage{hyperref}
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=5.00.0.2570}
%TCIDATA{}
%TCIDATA{Created=Tuesday, September 21, 2004 06:51:08}
%TCIDATA{LastRevised=Sunday, January 08, 2006 14:35:57}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{CSTFile=40 LaTeX article.cst}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\input{tcilatex}
\geometry{left=0.6in,right=0.5in,top=0.4in,bottom=0.5in}
\begin{document}
\begin{center}
{\Large Puzzle 5 - SOLUTION}
\end{center}
\bigskip
\begin{problem}
Mr and Mrs Brown are having a party. They invited three other married
couples, so there are eight people present. When greeting each other, some
people shake hands with some people. Of course, nobody shakes hands with
his/her spouse. \ When Mr Brown asks the other seven people: "How many
people did you shake hands with?", he receives seven different answers. How
many people did Mrs. Brown shake hands with?
\end{problem}
\bigskip
\begin{solution}
Mr. Brown receives $7$ different answers. First we need to figure out what
those answers were. What is the highest possible number among the answers?
Suppose I am the one who shook hands with everyone I could. There are $8$
people, I won't shake my own hand, and I won't shake hands with my spouse,
so that leaves $6$ hand shakes for me.
What is the lowest possible number among the answers? Clearly $0$. Now we
know that the answers were $7$ different numbers between 0 and 6. Those
numbers \ can only be $0$, $1$, $2$, $3$, $4$, $5$, and $6$. Let us
represent the 4 married couples on the picture below.\FRAME{dtbpF}{1.638in}{%
1.1268in}{0pt}{}{}{picture1.bmp}{\special{language "Scientific Word";type
"GRAPHIC";maintain-aspect-ratio TRUE;display "USEDEF";valid_file "F";width
1.638in;height 1.1268in;depth 0pt;original-width 0.9331in;original-height
0.6339in;cropleft "0";croptop "1";cropright "1";cropbottom "0";filename
'picture1.bmp';file-properties "XNPEU";}}
By symmetry, we may arbitrarily pick the person with $6$ handshakes. We
denote the number of handshakes by a little number. \ Let us represent the
handshakes with lines. Now our picture looks like this:\FRAME{dtbpF}{1.5022in%
}{1.0343in}{0pt}{}{}{picture2.bmp}{\special{language "Scientific Word";type
"GRAPHIC";maintain-aspect-ratio TRUE;display "USEDEF";valid_file "F";width
1.5022in;height 1.0343in;depth 0pt;original-width 0.9331in;original-height
0.6339in;cropleft "0";croptop "1";cropright "1";cropbottom "0";filename
'picture2.bmp';file-properties "XNPEU";}}
Can you see it? Our choice of the person with $6$ handshakes determines the
identity of the one with $0$ handshakes: they have to be married! So now our
picture is:\FRAME{dtbpF}{1.5653in}{1.0776in}{0pt}{}{}{picture3.bmp}{\special%
{language "Scientific Word";type "GRAPHIC";maintain-aspect-ratio
TRUE;display "USEDEF";valid_file "F";width 1.5653in;height 1.0776in;depth
0pt;original-width 0.9331in;original-height 0.6339in;cropleft "0";croptop
"1";cropright "1";cropbottom "0";filename 'picture3.bmp';file-properties
"XNPEU";}}
This is the main idea; we only need to apply it again and again. Let us pick
the person with $5$ hand shakes. Now the picture is:\FRAME{dtbpF}{1.5082in}{%
1.1147in}{0pt}{}{}{picture4.bmp}{\special{language "Scientific Word";type
"GRAPHIC";maintain-aspect-ratio TRUE;display "USEDEF";valid_file "F";width
1.5082in;height 1.1147in;depth 0pt;original-width 1.4797in;original-height
1.0871in;cropleft "0";croptop "1";cropright "1";cropbottom "0";filename
'picture4.bmp';file-properties "XNPEU";}}
Now we see that the person with $5$ hand shakes and the person with $1$ hand
shake has to be married. And so on, we play this game until we find that the
married couples are:
$6$ and $0$,
$5$ and $1,$
$4$ and $2$.
The only number that was not paired up, is $3$. This means that the person
who said s/he shook hands with three people, is someone whose spouse was not
asked. Mr. Brown did not ask \ himself, so his number is missing. So Mrs.
Brown MUST\ BE the one with $3$ hand shakes. Thus, Mrs. Brown shook hands
with $3$ people.
\end{solution}
\end{document}