# Generalization of the shakehands/condom puzzle?

The classic handshake puzzle goes something like this:

• "Given that everyone has a different skin disease, how can you safely shake hands with 3 people when you have only 2 gloves?"

Its common variations are:

• "How can a man engage in safe sex with 3 women using 2 condoms?"
• "How can a doctor operate on 3 patients with only 2 gloves while avoiding skin-blood contact between any two people"

Let's say N is the number of other people (patients/women...etc) and K is the number of gloves (or condoms). The above case of N=3 and K=2 is not hard (and its solution readily available on the net).

QUESTION 1: In general, what can we say about the feasible N's and K's? It seems like (2K >= N+1) is a necessary condition (K gloves has 2K sides and there are a total of N+1 people involved). Is this also sufficient?

While researching on Google, I came across a posting that claimed the generalization of this similar puzzle is an open problem:

QUESTION 2: I assume the general form of the question would study the feasibility of N couples and K condoms. What is known about the general problem? Is it still open?

(Qiaochu Yuan:) Based on the downvotes, which I would guess are directed at the way in which the problem is stated rather than its content, here is a "cleaned up" version appropriate for mathematicians:

You have a collection of $K$ tokens which have two sides, each of which can be marked. There are two families of marks, $N$ of which are of the first family and $M$ of which are of the second family. For each pair $(i, j)$ of a mark of the first family and the second family, attempt the following:

• Stack a collection of tokens from left to right. (Tokens may be rotated.)
• Mark the left side of the leftmost token with mark $i$ and the right side of the rightmost token with mark $j$. This move is only possible if each of the sides to be marked is either initially unmarked or is marked only with the mark you are trying to mark it with and with no other marks.

For which values of $K, N, M$ is this possible?

-
For those of you not in the know, the key to the puzzle is that it is possible to turn gloves and condoms inside-out. –  Qiaochu Yuan Dec 31 '09 at 0:03
After some thought, I can answer QUESTION 1 myself. To keep things PG for now, let's use the doctor/patient version. Suppose 2K = N+1, let's number the gloves and the patients from 1...K and 1...2K-1 respectively. Here's the algorithm: Put on glove K first, then for i=1 to K-1, place glove i over glove K and operate on patient i, then set aside glove i. When gloves 1 through K-1 are used, operate on patient K with glove K. Now, for i=1 to K-1, flip glove i inside out (so the clean side is now exposed), put the inverted glove i over glove K and operate on patient K+i. –  Shlomo Shmai Dec 31 '09 at 0:15
Would anyone downvoting this care to leave a comment explaining why? It seems a reasonable question to me, unless the answer's well-known (in which case someone should give a reference). Or are people bothered about the condom thing? –  Tom Leinster Dec 31 '09 at 0:37
I'm sure you didn't mean it to be provocative, but the condom thing is in bad taste. I wouldn't delete or down vote the question just on that, but I would avoid such examples in the future. –  Ben Webster Dec 31 '09 at 4:02
Actually, I would encourage you to edit it out of the question, as a courtesy to everyone on the site. –  Ben Webster Dec 31 '09 at 4:03

This problem is well-known as "glove problem" or, indeed, "condom problem". It was almost solved by Hajnal and Lovasz in 1978, with final touches put by Vardi in 1991.

http://mathworld.wolfram.com/GloveProblem.html

http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/condoms-n-m

-