[Math] Generalization of the shakehands/condom puzzle

abstract-algebraalgorithmsco.combinatorics

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?

Best Answer

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

Related Question