He conocido a un grupo de 9 compañeros (estudiantes de Doctorado), y cuando llegó el apretón de manos fue complicado como siempre apretón de manos a todos y evitar cross overs.
Así que un chico sugerido (él no era en serio) para estudiar el problema de que el número mínimo de rondas para un círculo de $n$ amigos apretón de manos que no cruces se producen. De couse el mínimo, si permitimos que los crossovers es $n-1$ rondas, porque si lo arreglamos de una persona, entonces en cada ronda se le da la mano a la mayoría de la otra persona. Pero hay un momento donde los dos chicos junto a él se dan la mano, y así que él se sienta en esa ronda.
La pregunta natural es si existe una fórmula para el número mínimo de rondas necesarias en este caso, o al menos límite inferior menor que el trivial enlazado en la que cada persona le da la mano a todos los demás, mientras que el resto se queda quieto esperando a que termine.
No estoy esperando una solución, sino más bien con la esperanza de que si este problema ha sido estudiado antes. Cuando he intentado buscar me encontré con todo tipo de problemas de la tarea como "si 534345 apretones de manos que sucedió entonces, ¿cuántas personas que estaban allí" ... yo no estaba seguro también de los términos de búsqueda; he intentado tanto "crossovers" y "intersección", pero fue en vano.
Editar:
A partir de los comentarios me doy cuenta de que tal vez más sólida definición del problema es necesario. Aquí va:
Hay un conjunto $P$ $n$ personas colocadas en los vértices de un regular $n$-gon. El objetivo es que después de que el "programa" termina, cada persona debe tener un apretón de manos con cada otra persona exactamente una vez. Por "apretón de manos", nos referimos a que dos personas tienen una arista que los une. La ejecución se realiza en las rondas, que en cada ronda de una persona puede ser "apretón de manos" con otra persona, o no hacer nada. Una persona $i$ que sacudió las manos en algunas ronda precedente con un subconjunto de personas $J\subseteq (P-\{i\})$ se considera sólo la gente que no estrechar la mano con $(P-(J\cup\{i\}))$ en la siguiente ronda, al seleccionar uno de ellos para estrechar la mano. La restricción es que en ninguna ronda no hay dos bordes pueden intersecar.
La pregunta es para determinar el número mínimo de rondas necesarias para resolver este problema ?
También estaría interesado en un caso especial en el que los bordes están restringidos a ser "líneas rectas", en la representación de la restricción de un poco diferente de la plana gráfico condición, a una forma más geométrica condición.
