Useful generalizations, Part II

Very often in mathematics a theorem can be easier to prove if it is viewed as a consequence of a different theorem, which may be far more general than the original.

Our example for this post appeared on the 2014 Collegiate Mathematics Competition, sponsored by the Northeastern Section of the Mathematical Association of America:

A husband and wife invited four married couples to a housewarming party. Just before everyone left, the husband asked each person (including his wife) how many people they had shaken hands with. Their responses were 8, 7, 6, 5, 4, 3, 2, 1, and 0. Given that no one shook hands with his or her own spouse and no pair of people shook hands more than once, determine how many times the husband must have shaken hands with a guest.

In fact this little puzzle is not too difficult, and you may wish to try it for a few minutes before reading further! (Can you do it in your head?)

— Empty space to encourage playing/thinking —

Congratulations! By now you’ve either solved the problem or else realized that it’s not that easy. Either way it’s a win—in both cases the next question is:

Can we make up an analogous question with fewer than four married couples invited to the party? Does the question make sense with just one married couple? With two married couples? With n married couples?

(If you haven’t solved the problem, the one-couple version is a very nice playground, which will hopefully help with the original. If you have solved it, then you may be in store for a better theorem and a different proof).

We don’t know yet whether or not this problem will actually generalize nicely. Nevertheless, for the one-couple version, let’s say the responses to the handshake question are 2, 1, and 0. With only 4 people present at this party, the person shaking 2 hands—not shaking the hand of the 0-handshake person—must shake everyone else’s hand. Hence the 2-handshake and 0-handshake people are married to each other. The 1-handshake person shakes hands with the 2-handshake person and nobody else. Now we have a complete picture of everyone’s handshakes except the husband. Fortunately that’s enough to recover all needed information about the husband, who shakes the hand of one person. His wife also shakes hands with one person.

Now for the two-couple version of the problem: assume the responses to the handshake question are 4, 3, 2, 1 and 0. We could proceed in the same way, forming a complete picture of who must shake everyone else’s hand, starting from the 4-handshake and 0-handshake people, who must be married to each other, etc. But here’s a different tact: once we realize that the 4-handshake and 0-handshake people form a married couple, we remove this couple—induction! Note that this removal necessarily reduces the number of handshakes by 1 for each remaining person. We are in fact reduced to the one-couple version of the problem. This suggests both a general theorem and its proof:

Theorem: Let G be a simple graph with 2n+2 vertices. Assume the degrees of 2n+1 of the vertices are given by the numbers 0, 1, 2, … , 2n. Then the last vertex must have degree n. Moreover, for i=1,2,…,n, the vertex of degree n−i is not adjacent to the vertex of degree n+i, and the two vertices of degree n are not adjacent to each other.

There are a couple of important objections. The first one is that this doesn’t look like the original problem; unless a vertex represents a person and an edge represents a handshake. We’ll address the other objection after the proof.

Proof: Let x be the unknown degree. We wish to prove x=n. We proceed by induction on n, the case n=1 being not too hard (and discussed above). We now assume the result true for n−1. Consider a graph G with 2n+2 vertices as in the hypothesis of the theorem. Delete the vertices of degrees 0 and 2n. This reduces the degrees of each remaining vertex by 1, leaving 2n vertices with degrees:

0, 1, … , 2n−2 and x−1.

By the inductive hypothesis x−1=n−1, the two vertices of degree n−1 are not adjacent to each other, and a vertex of degree n−1+i is not adjacent to the vertex of degree n−1−i (for i=1, 2, … n−1). Replacing the two deleted vertices from G gives the desired result. QED.

Now for the other objection: the hypothesis that no one shook the hand of his or her own spouse seems to have disappeared, suggesting this assumption was not necessary to solving the problem. Yet the conclusion of the theorem includes a description of vertices not adjacent to each other. So our theorem is better—it has a weaker hypothesis and it guarantees that the n-couple version of the problem describes a situation that could actually happen. If we do assume that no one shakes the hand of his or her own spouse, then one can show—by induction on i—that the person who shakes 2n-i hands is married to person who shakes i hands.

So this was much more involved then it had to be. Yet it is satisfying on many levels. We made a small (n=1) toy version of the problem, we provided a generalization and we showed that the hypothesis of the general problem is realizable.

Remarks:

1. The n=3 version of this problem appears in Loren C. Larson’s outstanding book, Problem-Solving Through Problems, in a section entitled, “Draw a Figure.” We chose this complementary, algebraic approach. It’s certainly instructive to compare the two approaches, to see exactly how the use of induction on n gets the same conclusion without explicitly drawing the entire picture.

2. Another written solution (closer to the one in Larson’s book) is available from the Collegiate Mathematics Competition webpage by looking up the practice problems from 2014, question 4.  Many thanks to my colleague Rob Poodiack for bringing my attention to these excellent problems.

3. This problem is perfectly adaptable to many different levels of difficulty and discussion. So it’s a perfect question to consider, even on a lazy summer afternoon. Enjoy!

added

This entry was posted in Uncategorized. Bookmark the permalink.

One Response to Useful generalizations, Part II

  1. jim smith says:

    Similar problem in sec. 6.3, Biggs. Discrete Mathematics, 2nd ed, OUP

Leave a Reply

Your email address will not be published. Required fields are marked *