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?



Generalization of the shakehands/condom puzzle?
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>


