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:

- "Two couples get together for an evening of hetero swinging. What is the minimum number of condoms necessary for safe sex in all of the male-female pairings?" http://mathematicsontribe.tribe.net/thread/d0f5c284-762d-4045-be74-21e6ede7e31e

**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.)
- If two tokens are adjacent, the adjacent sides share marks.
- 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?