19
$\begingroup$

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.)
  • 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?

Improve this question
$\endgroup$
13
  • 17
    $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    Commented Dec 31, 2009 at 0:03
  • 12
    $\begingroup$ 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? $\endgroup$
    – Tom Leinster
    Commented Dec 31, 2009 at 0:37
  • 6
    $\begingroup$ 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. $\endgroup$
    – Ben Webster ♦
    Commented Dec 31, 2009 at 4:02
  • 4
    $\begingroup$ Actually, I would encourage you to edit it out of the question, as a courtesy to everyone on the site. $\endgroup$
    – Ben Webster ♦
    Commented Dec 31, 2009 at 4:03
  • 3
    $\begingroup$ I first heard the condom problem from Vasek Cvatal who phrased it in the crudest and most explicit terms possible. That way, it stuck in my mind and I solved it 5 years later. He's a very famous combinatorialist, for example, he heard of the Art Gallery Problem at a conference and solved it in a day. $\endgroup$
    – ilan vardi
    Commented Feb 24, 2010 at 23:11

2 Answers 2

Reset to default
15
$\begingroup$

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

Improve this answer
$\endgroup$
38
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • 13
    $\begingroup$ I think it's indeed sad that some people, even on this website, are offended by a question that uses something sexual in its formulation. $\endgroup$
    – faridrb
    Commented Feb 22, 2010 at 12:54
  • 3
    $\begingroup$ I'd like to like the condom problem, since I think it's cute to celebrate a person having multiple "safe" sex partners (in mutual respect and understanding, hopefully) in the context of a math problem. But nonetheless the condom thing rubbed me the wrong way (ahem), I think because I couldn't help but see in it a celebration of the sex-as-conquest view that I find disturbingly prevalent among males (in my culture?). $\endgroup$
    – Dustin Clausen
    Commented Feb 22, 2010 at 15:53
  • 7
    $\begingroup$ Donald Knuth wrote a paper called "The toilet paper problem" and had no problems getting it published. I think this is indication that it is not the explicit nature that disturbs Americans but just the sexual nature. $\endgroup$
    – ilan vardi
    Commented Feb 22, 2010 at 19:38
  • 9
    $\begingroup$ OK, I see your point. But since physical violence is even more reprehensible than consensual sex, I suggest we start rewriting mathematical history by renaming the Killing form in Lie Algebra as it brings to mind, at least to me, the disturbing imagery of the Cambodian Killing Fields of the Khmer Rouge genocide. I suggest calling it the Friendship form. I could continue with the Fock representation, but if that brings something distracting and uncomfortable to mind, then I suggest that it is your mind that is to blame as it is too easily distracted by a certain imagery. $\endgroup$
    – ilan vardi
    Commented Feb 22, 2010 at 22:36
  • 8
    $\begingroup$ Given that the raison d'etre of this paper is sitting on the toilet deciding with which roll to wipe, I would say that it refers directly to bodily functions which are not usually associated with higher intellectual pursuits. $\endgroup$
    – ilan vardi
    Commented Feb 22, 2010 at 23:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .