Safe Handshaking Puzzle
The general case of the Super Glove Puzzle
A group of friendly men and women Mensa members assemble for an evening of scintillating conversation, snack foods, mathematical research, and safe traditional handshaking.
There's quite a bit of variation in the structure of the various Mensa activities. These range all of the way from the talk-and-eat format to its polar opposite, eat-and-talk.
The refreshments at this particular event include chocolate, soft drinks, potato chips, and Larry's famous bean dip. And did I say chocolate?
Unfortunately, medical research suggests that handshaking can transmit rhinoviruses. And none of the participants wants to miss a day of work because of the common cold. They want to minimize this risk, by wearing disposable surgical gloves. And they're keen on saving money by purchasing the absolute minimum number of gloves.
Note. The men all fancy themselves to be Klingons, and they prefer to place their right fists over their hearts, and yell, "Kaplah!" when they meet each other. In contrast, the women curtsy when they meet each other. In both cases, there is no physical contact (and hopefully no sneezing or coughing). The polite handshakes are reserved for male-female introductions and greetings.
There are f women and m men. What is the minimum number of gloves needed for a safe group handshaking session, involving all possible one-on-one, male-female handshakes of the participants?
Believe it or not, the general case is one of the great unsolved mathematical puzzles of all time. However solutions for specific values of f and m can be calculated, as we'll see in the next section.
At one time, there was much discussion about a variation of the Glove Puzzle in the old Soviet Union.
The rules of the game permitted a person to wear more than one glove at a time, in order to minimize wasteful use of disposable gloves. Without this twist, the puzzle would have had a trivial general solution.
There's an upper bound to the f by m case: f + m - 1. With the exception of the last man, each participant brings his or her own glove, and that glove stays with the person for the entire evening. Each glove is used in combination with at least one another glove, such that one surface is always clean until the very last round.
One more caveat: This puzzle involves super-gloves. They are arbitrarily thin, and super-strong at the same time.
Hey maths teachers, if you're really serious about capturing the mathematical imaginations of your students, this is how to do it!
And even if you're not a maths teacher, you can make the Glove Puzzle into an entertaining party game. A stack of 3X5 cards acts as a proxy for the glove supply, with each card representing an individual glove. Whenever there's a virtual handshake, the participants write their initials on the appropriate sides of the cards. In some cases, it may be necessary to paperclip two or three cards together.
Two teams--each having f women and m men--compete to see who can use the fewest gloves, without taking unnecessary risks of rhinoviral infection, or--Heaven forbid--influenza.
As we'll soon see, it'll be necessary to turn some of the gloves inside-out. And for that delicate maneuver, deft use of two pairs of electrician's pliers will be necessary to avoid contamination of the clean sides of the gloves. In between uses, the pliers are briefly dipped in a hydrogen peroxide disinfectant solution.
Surprising as this may sound, it is possible to combine serious mathematics or serious science with humor. Hence the Ig Nobel Prizes. LINK.
The 3 by 3 case
The 3 women are A, B and C. The 3 men are X, Y and Z. Each super-glove is labeled with a "K" and a subscript. Here are logistics of the 9 possible handshakes.
1. X puts on glove K1. A puts on glove K2. X shakes A's hand. And he continues to wear K1.
2. B puts on glove K3. X shakes B's hand.
3. C puts on glove K4. X shakes C's hand.
Scorecard for the Round 1: 4 half-clean gloves.
K1 has X's germs on the inside.
K2 has A's germs on the inside.
K3 has B's germs on the inside.
K4 has C's germs on the inside.
4. Y shakes A's hand. A removes her glove (K2), and carefully turns it inside-out. Y puts on K2. X removes K1. Remember that the outside of K1 is clean. Then Y puts on K1, over his inner glove (K2). Again, the clean side of K1 faces outward.
5. Then Y shakes B's hand. (He's wearing K1 and K2; and she's wearing K3.)
6. Then Y shakes C's hand (He's still wearing K1 and K2; and she's wearing K4).
Y is now wearing 2 gloves (K2 on the inside, and K1 on the outside). Y carefully turns K1 inside-out, and gives it to Z. Then Y throws away the inner glove (K2).
Scorecard for the Round 2:
The inner surface of K1 is clean, and the outer surface has X's germs.
K2 is in the trash.
K3 has B's germs on the inside.
K4 has C's germs on the inside.
7. Without wearing a glove, Z shakes C's hand.
8. Without wearing a glove, Z shakes B's hand.
Z carefully turns K3 inside-out, and keeps that as an inner glove. Then he adds the one given to him by Y (K1) as an outer glove, with the clean side facing out.
9. Then Z shakes A's hand.
Larry's (unproven) Conjecture:
The minimum number of gloves necessary for safe handshaking is always f + m - 2.
Hat-tip to mathematician extraordinaire Mamikon Mnatsakanian for bringing the origin version of this puzzle to my attention.
A note about the top photo
I needed a friendly face for this hub. Otherwise it would have been too nerdy.
Nina Hartley is a leading figure in her film genre. She is aging gracefully, and has even branched out into mainstream movies. Ms Hartley also has a great sense of humor.
Copyright 2012 and 2013 by Larry Fields