Give Me a Hand

Comments by Professor Miller and Rebecca Silva

Problem stated below:

“A professor and their spouse are at a party. At the party there are four more couples (overall five couples).

 During the party couples shake hands with the following rules:

1. One does not shake hands with oneself.
2. One does not shake his/her spouse’s hand.

At the end of the party the professor asked all the other guests at the party (including their spouse) how many different people they shook hands with. Each person tells him a different answer (meaning, if one person said “five”, no one else said “five”). 

With how many people did the professor shake hands?”

First Thoughts: 

The first thing we want to ask ourselves after reading this problem is what we can infer from the information given. Seeing as (a) one does not shake hands with oneself and (b) one does not shake hands with his/her spouse, we can find the total number of handshakes possible. Because one cannot shake their spouse’s hand, each person is left with a maximum of eight other people to shake hands with. The possibilities are 0, 1, 2, 3, 4, 5, 6, 7, and 8 handshakes, giving a total of nine distinct answers. Since there are nine people excluding the professor, we can infer that the number of hands the professor shakes will be the same number as one other person at the party.

——————————————————————————————————————- 

At Second Glance:

This problem is simpler when we look at what would happen with two couples, three couples, and then four. If we see a pattern it will be easier figure out what happens in the case of five couples.

Let’s start with two couples…

For the purpose of understanding the problem, let us say you are the professor. The maximum number of handshakes possible is two because there are only two other people when you take away yourself and your spouse. The possible number of handshakes are 0, 1, and 2. Let us label the other two at the party besides you and your spouse as person A and person a, the spouse of person A. Uppercase letters will denote women and lowercase letters will denote men. Denoting people like this is an important step in solving a problem. Notation can help us keep track of who is who and what each person has done, making the problem easier to handle. Notation may seem trivial, but it makes the process of solving a problem and discussing it smoother.

The possibilities for each person at the party are shown in the chart below.

After eliminating the options of shaking your own hand and shaking your spouse’s hand, each person is left with two options. But, we know that of your spouse, person A, and person a, only one person shakes two hands, one shakes one hand, and one shakes zero hands. If your spouse shakes two hands, then A and a would have both shaken one hand so there would be no one left to shake zero hands. Therefore, we know that either A or a will shake two hands. Without loss of generality, let us say A shakes two hands (the professor and spouse). Now the spouse has shaken one hand and person a has shaken zero so we are done. Below, we can see that the professor shakes one hand.

 

 ——————————————————————————————————————-

Third Thoughts:

After showing what happens with only two couples, we can take away an important lesson. We must count the handshakes as a reciprocal act. This means that when someone shakes your hand, not only does that person’s number of handshakes increase by one but yours does as well. With this idea, we know that no one can shake the person’s hand who gives zero handshakes.

Let’s keep going and see what happens with three couples…

We now add person B and her spouse, person b. We know from the scenario with two couples, that your spouse does not shake the maximum number of hands because if so, no one would be left to shake zero hands. Without loss of generality we can say A shakes four hands, meaning she shakes everyone except your spouse’s hand. Now person a is the one person who can shake zero hands. The people left are your spouse, person B, and person b. If your spouse shakes three hands, they would shake hands with person A, person B, and person b. This does not work because both person B and person b would have shaken two hands, and no one would be left to shake only one hand. Without loss of generality we can say person b shakes three hands. He cannot shake hands with his spouse (B), and cannot shake hands with the person who shakes zero hands (a). This leaves you (the professor), your spouse, and person A. Now everyone except the professor has shaken a distinct number of hands.

We are starting to see patterns. For example, the person who shakes the maximum number of hands possible has a spouse who shakes zero hands. This makes sense because in order to reach the maximum number, the person shaking the maximum number of hands must shake everyone’s hand except their spouse’s, leaving the spouse as the only person who can shake zero hands. We are also seeing that every couple has the same total number of handshakes. The person who shakes one less than the maximum number of hands has a spouse who shakes one hand and the person who shakes two less than the maximum number of hands has a spouse who shakes two hands. This becomes further evident as we go through our strategy for five couples. But before looking ahead, try solving the problem for four couples.

 

——————————————————————————————————————- 

Fourth Thoughts: Scenario with five couples:

Now we will discuss how to approach the problem with five couples. The person who shakes the maximum number of hands (8) must shake everyone else’s hand except for their spouse’s, which leaves their spouse as the person available to shake zero hands. Now think about the person with the second largest possible number of handshakes, 7. This person cannot shake their spouse’s hand and cannot shake the hand of the person who shakes zero hands. After eliminating those two people, there are only seven hands left to shake so that person must shake them all. These seven people have now each received two handshakes. This leaves only one person to shake one hand: the spouse of the person who shakes seven hands. Next, we look at the person that must shake six hands. This person shakes every hand except their spouse’s, the hand of the person who shakes one hand and the hand of the person who shakes zero hands. The six people that receive this handshake now have a total of three handshakes, which means the person who shakes only two hands must be the spouse of the person who shakes six hands. We continue this process with the person who shakes five hands, leading us to identify their spouse as the person who shakes three hands. Then we are left only with the person who shakes four hands and we see that it must be your spouse. Below, the diagram is completed for two couples (A,a and B,b) and you should complete it for the last 3 couples.

——————————————————————————————————————-

Final Thoughts

We have solved this problem by beginning with simpler cases. Simpler cases not only help us see the answer but also provide us with confidence to tackle the larger problem. Starting with two couples does not seem so bad, and then adding one couple at a time is not too intimidating. By starting with simpler cases we were also able to notice patterns such as the constant number of total handshakes per couple. This symmetry is special because it helps us find the general solution to the problem. We know that every couple’s total will add to the same number, and therefore because the maximum number of handshakes is even, there must be one couple where both people shake the same number of hands (maximum possible handshakes/2 or (n—2)/2 where n is the number of couples). The only couple for which this could be true is the professor and the professor’s spouse because the professor is the only person allowed to shake the same number of hands as another person. After making the general solution (n—2)/2, we can try adding more couples and check our answer. Here, we are using a mathematical process called induction by finding what happens with smaller cases and concluding that the same happens with larger cases.

So, to explicitly recap, here are good items we saw.

1. Power of good notation (using capital and lowercase letters, having the capital be women and the lowercase men); makes it easier to refer to.
2. Draw pictures.
3. Do smaller cases first to build intuition; don’t be afraid to do a lot of cases.
4. Try to generalize: build on success from smaller cases.