Prove using induction on the number of couples n that for ea

Prove, using induction on the number of couples n, that for each band shake party with n couples, the sum of the number of handshakes of each person and their spouse is 2n = 2. Don\'t be afraid to use the results from a, b, and c to use as justification in your argument for this part. How many hands does the host shake? What about the spouse of the host? Use your result from d to justify.

Solution

Solution:

(d.)

The person and spouse each shook exactly n-1 hands.

Part 1: The case n=1.

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.

(e). The host Shake (n-1) hand shakes. and

The spouse also shake (n-1) hand shakes.