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:


*

*"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?
 A: Thank you for posting my solution. I am still amazed that this problem remains controversial after 20 years. Indeed, before publication, my book editors communicated statements to the effect that the chapter of my book entitled "The Condom Problem" was sexist. This is echoed by some of the above comments. The editors decided to go ahead with my proposed formulation when it was pointed out by (female) reviewers that my formulation (as opposed to what is given here) was gender neutral in the sense that the names "men" and "women" were interchangeable whereas in the euphemistic formulation involving gloves all the doctors were male and all the nurses were all female, so the politically correct version was the truly sexist one. The above comments that the condom problem is offensive to women imply that sexual content should naturally offend females, which is obviously incorrect and is more a reflection of the persistence of certain puritanical United States values. In any case, Addison Wesley decided to publish it, and the rest is history. If the decision of the most reputed technical publisher is not good enough for you, then I wonder what is. Moreover, I solved the problem, so if you respect my efforts which were fairly involved since the solution is quite tricky, then please formulate it as I have. As for the mathematics, it is always true that an explicit solution is best.
-Ilan Vardi
A: 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
