Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was given the following math puzzle which (I thought) has an interesting solution.

A mathematician and her husband attended a party with $n-1$ other couples. As is normal at parties, handshaking took place. Of course, no one shook their own hand or the hand of the person they came with. And not everyone shook everyone else's hand. But when the mathematician asked the other $2n-1$ people present how many different people's hands they had shaken they all gave a different answer from $0$ to $2n-2$. Question (this is NOT a trick!): How many different people's hands did the mathematician's husband shake?

Can anyone come up with a graph theory solution that uses an induction proof?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

Let $P_k$ be the person who shook $k$ hands. $P_{2n-2}$ shook hands with everyone but his or her partner, so $P_0$ must have been the partner. Set them aside, leaving $P_1,\dots,P_{2n-3}$ and the mathematician. Each of these remaining people shook hands with $P_{2n-2}$, so within the group that remains each shook one hand fewer: $P_k$ shook $k-1$ hands for $k=1,\dots,2n-3$. By the same reasoning (or by induction) $P_1$ and $P_{2n-3}$ must be a couple. In general we must have $P_k$ and $P_{2n-2-k}$ forming a couple for $k=0,\dots,n-2$. In particular, $P_{n-2}$ and $P_n$ are a couple. This leaves $P_{n-1}$ to be the mathematician’s husband: he shook $n-1$ hands.

In graph-theoretic terms we have a graph $G_n$ with vertices $v_k$ for $k=0,\dots,2n-2$ such that $\deg v_k=k$, and we have an additional vertex $v$ corresponding to the mathematician. The graph is simple (no loops or multiple edges), and it is known that the vertices can be partitioned into $n$ pairs whose members are not adjacent. We wish to show that $v$ is paired with $v_{n-1}$. This is clearly the case when $n=1$, so assume that $n>1$.

Vertex $c_{2n-2}$ is adjacent to every vertex but itself and the one paired with it, so every vertex but the one paired with it has positive degree; thus, $\{v_0,v_{2n-2}\}$ must form a pair. Remove $v_0$, $v_{2n-2}$, and all adjacent edges, and you have a graph $G_{n-1}$ on $2(n-1)$ vertices with mutatis mutandis the same properties. By the obvious induction hypothesis vertex $v$ is paired with the vertex of degree $n-2$ in $G_{n-1}$, which is $v_{n-1}$ in $G_n$, as desired.

share|improve this answer
    
This is the symmetry version of the solution to this question. Doesn't really use induction but a beautiful proof nonetheless! (Isaacs gave me this problem by the way). –  Eugene May 26 '12 at 3:46
    
@Eugene: That was mostly just to get a solution down. I’ve expanded it to make it more explicitly graph-theoretic and to cast the solution explicitly as an induction. –  Brian M. Scott May 26 '12 at 3:55
    
This can easily be converted into an induction proof. Let $Q_k$ be the proposition $H_k=P_{k-1} $ when there are $k $ couples present. The base case, $Q_1 $ is trivial. Suppose we have $Q_r $ and we want to establish $Q_{r+1} $ - take out the couple $P_0$ & $P_{2n-2} $ and remove their handshakes as Brian explains. You then have a case of $Q_r $ which is already established, and putting the extreme couple back in adds one handshake to the husband and $H_{k+1} = P_k$ –  Mark Bennet May 26 '12 at 4:00
2  
@Mark: The graph-theoretic version is an induction proof as I’ve written it: it needs no conversion. –  Brian M. Scott May 26 '12 at 4:18
    
I wrote the comment as you were making the edit ... –  Mark Bennet May 26 '12 at 19:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.