Before proceeding with the solution, let's first consider the

Principle of Mathematical Induction.

Let P be a property of positive integers which satisfies the

- following two conditions
(1) P(1) is true. (2) Whenever P(k-1) is true for an integer k>1, it follows

that P(k) is also true.

Then P(n) is true for every positive integer n.

Proof:

Suppose not. Then the set of counterexamples

C = {k in Z+ : P(k) is false}

is a nonempty subset of the positive integers. Therefore C must have a smallest element s. Because of (1), s cannot be 1. But then s-1 is also a positive integer and P(s-1) must be true, because of the assumption that s is the smallest integer where P fails. Thus, P(s-1) is true, but P(s) is false, which contradicts condition (2), QED.

Now we are ready for the answer to the problem.

Answer: The host and hostess each shook exactly n-1 hands.

First proof, using mathematical induction.

Part 1. The case n = 1.

In this case there are no guests at the party -- only the host and hostess, for a total of 2n = 2 people. We are to show that they each shook n-1 = 0 hands. This follows from the assumption that spouses are already acquainted and do not shake hands.

Part 2. The case n = k.

We are to assume that the stated answer is correct for the case n=k-1. In other words, we assume it is already known that if there are 2*(k-1) people at the party and the host finds that all the handshake totals (excluding his own) are different, then it follows that the host and hostess each shook k-2 hands. Our task is to prove that the corresponding result also holds for the case n=k, namely, that the host and hostess each shook k-1 hands.

We are given that no two of the 2k-1 people at the party, excluding the host, have the same number of handshakes. This can be so only if every number from 0 through 2k-2 is accounted for, since it is known that no one shakes more than 2k-2 hands.

Let A be the person with 2k-2 handshakes, and let B be the person with 0 handshakes. Then obviously A did not shake hands with B, since B shook hands with no one. On the other hand, A must have shaken hands with everyone at the party except A and A's spouse. Therefore, B must be A's spouse. Moreover, since A and B are both in the group of 2k-1, it follows that A and B are not the host and hostess.

Imagine the situation if A and B had not been invited to the party. Each of the 2k-2 people remaining at the party would have had a handshake total decreased by one (since they all shook hands with A and none with B), and the number of handshakes therefore would have ranged from 0 to 2*(k-1)-2 = 2k-4, with no duplicates. Applying the induction hypothesis for the case n=k-1, we conclude that the host and hostess would each have shaken exactly k-2 hands at the reduced party. Restoring A and B to the party, we get one additional handshake for the host and one for the hostess, making a total of k-1 for each. This is what was needed to complete the induction.

Second proof, based on the the diagram given below

As before, we let A be the person who shook 2n-2 hands, and let B be the person who shook 0 hands. As before, we conclude that A must be the spouse of B. Since A and B are both in the circle of 2n-1, they can't be the host and hostess.

Now let C be the person who shook 2n-3 hands, and let D be the person who shook 1 hand. C and D are immediately below A and B in the circular diagram.

(A) 2n-2 0 (B)

(C) 2n-3 1 (D)

2n-4 2 2n-5 3 . .

. .

. .

n n-2

n-1

(There are 2n-1 on the circle.)

Clearly, D must have shaken hands with A and no one else. C must have shaken hands with everyone except B, C, and C's spouse. Therefore, D must be C's spouse, and C and D can't be the host and hostess. In the same way, we continue down the diagram, row by row, and find a married couple at each level until we reach n-1 at the bottom of the circle. All married couples who are in the circle are already accounted for, and the only people left are the host and hostess. Each person with more than n-1 handshakes has shaken hands with everyone except those at the same level or higher from the opposite side of the circle. Each person with fewer than n-1 handshakes has shaken hands with no one except those at a higher level on the opposite side. The host and hostess each shook hands with all those on the left side of the circle, and with no one on the right side, for a total of n-1 handshakes each.

Dave Seaman ags@seaman.cc.purdue.edu