La generalización de la shakehands/condón rompecabezas?

Question

El clásico apretón de manos rompecabezas va algo como esto:

• "Dado que todo el mundo tiene diferentes enfermedades de la piel, ¿cómo puede usted con seguridad darle la mano a 3 personas cuando sólo tiene 2 guantes?"

Sus variaciones comunes son:

• "¿Cómo puede un hombre tener relaciones sexuales seguras con 3 mujeres que usan 2 condones?"
• "¿Cómo puede un médico operar en 3 pacientes con sólo 2 guantes, evitando la piel-contacto con la sangre entre dos personas"

Digamos que N es el número de otras personas (pacientes/mujeres...etc) y K es el número de guantes (o condones). En el caso de N=3 y K=2 no es difícil (y su solución fácilmente disponibles en la red).

PREGUNTA 1: En general, ¿qué podemos decir acerca de lo factible N y K? Parece (2K >= N+1) es una condición necesaria (K guantes 2K lados y hay un total de N+1 personas involucradas). Es esto suficiente?

Investigando en Google, me encontré con una publicación que se cobró la generalización de este similar puzzle es un problema abierto:

• "Dos parejas se reúnen para una noche de hetero balanceo. ¿Cuál es el mínimo número de condones necesarios para el sexo seguro en todos los de la macho-hembra emparejamientos?" http://mathematicsontribe.tribe.net/thread/d0f5c284-762d-4045-be74-21e6ede7e31e

PREGUNTA 2: supongo que la forma general de la cuestión el estudio de la viabilidad de N parejas y K condones. Lo que se sabe sobre el problema general? Está todavía abierto?

---

(Qiaochu Yuan:) Basado en los downvotes, que me imagino que se refieren a la manera en la que el problema se declaró en lugar de su contenido, aquí es un "limpiar" la versión adecuada para los matemáticos:

Tiene una colección de $K$ fichas que tienen dos lados, cada uno de los cuales puede ser marcado. Hay dos familias de marcas, $N$ de los cuales son de la primera familia y $M$ de los cuales son de la segunda familia. Para cada par $(i, j)$ de una marca de la familia en primer lugar y el segundo de la familia, intente los siguientes:

• La pila de una colección de fichas de izquierda a derecha. (Las fichas pueden ser rotados.)
• Si dos fichas son adyacentes, los lados adyacentes comparten las marcas.
• Marca el lado izquierdo de la izquierda token con marca $i$ y el lado derecho de la derecha token con marca $j$. Este movimiento sólo es posible si cada uno de los lados para ser marcado es inicialmente sin marcar o está marcado sólo con la marca que usted está tratando de marcar y con ninguna otra marca.

Para que los valores de $K, N, M$ es esto posible?

Answer 1

Este problema es conocido como "guante problema" o, de hecho, "el condón problema". Estaba casi resuelto por Hajnal y Lovasz en 1978, con toques finales a poner por Vardi en 1991.

http://mathworld.wolfram.com/GloveProblem.html

http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/condones-n-m

Answer 2

Gracias por publicar mi solución. Todavía estoy sorprendido de que este problema sigue siendo controvertido después de 20 años. De hecho, antes de la publicación de mi libro los editores comunicado declaraciones en el sentido de que el capítulo de mi libro titulado "El Condón Problema" era sexista. Esta es seguida por algunos de los comentarios anteriores. Los editores decidieron seguir adelante con mi formulación propuesta cuando fue señalado por (hembra) a los revisores que mi formulación (a diferencia de lo que se da aquí) fue neutral en términos de género, en el sentido de que los nombres de los "hombres" y "mujeres" eran intercambiables, mientras que en la eufemística formulación involucra guantes de todos los médicos eran varones y a todas las enfermeras eran todas mujeres, por lo que el políticamente correcto versión fue la que verdaderamente sexista. Los comentarios anteriores de que el condón problema es ofensivo para las mujeres implica que el contenido sexual, naturalmente, debe ofender a las mujeres, que es obviamente incorrecta y es más un reflejo de la persistencia de ciertas puritana de los Estados unidos de los valores. En cualquier caso, Addison Wesley decidió a publicarlo, y el resto es historia. Si la decisión de los más reputados de editorial técnico no es suficiente para usted, entonces me pregunto qué es. Por otra parte, he resuelto el problema, así que si respeto a mi los esfuerzos que estaban bastante, dado que la solución es muy difícil, entonces por favor formularlo como yo. Como para las matemáticas, es siempre cierto que una solución explícita es la mejor.

-Ilan Vardi