Problema de velocidad gay citas

Question

He aquí un interesante problema que se me ocurrió la otra noche.

Con la recta de speed dating, (suponiendo que el número de hombres y mujeres son iguales), el número de iteraciones que se deben realizar antes de cada hombre ha chateado con cada mujer es N/2, donde N es el número total de personas.

La velocidad Gay es mucho más compleja. El modelo tradicional, obviamente, no funciona. Suponiendo que en la recta de la velocidad de las citas, los hombres permanecen en sus mesas, la de "sentarse" a los hombres en la velocidad gay no va a satisfacer el uno al otro (ni el "pie" de los hombres).

Conteo de combinaciones en la velocidad gay manualmente, consulte los siguientes números:

f(2) = 1
f(3) = 3
f(4) = 3
f(5) = 5
f(6) = 5

Estos números sugieren que la velocidad gay se puede hacer con N o N-1 iteraciones (aunque de una forma mucho más caótico patrón).

Alguien tiene alguna idea? También, si es N iteraciones, ¿existe un patrón que podría ser seguido? I. e.: podrían los señores círculo de una mesa rectangular en sentido de la moda, a continuación, reorganizarse y continuar en otro mundo de la moda, que, dado cualquier número de hombres, cada hombre puede ser emparejado con cada otro hombre en el menor número de iteraciones y sin vinculación a dos hombres juntos dos veces.

Answer 1

Para un número impar, es fácil. Imagina una mesa larga con un asiento en un extremo y $\frac{N-1}{2}$ asientos a lo largo de cada lado largo. Cada persona tiene una cita con la persona a través de. Después de cada ronda, cada persona se mueve de un asiento de las agujas del reloj. Usted debe ser capaz de convencerse de que cada persona reúne todos los otros después de N rondas, pero no se puede hacer mejor, ya que cada persona necesita para satisfacer la N-1 a los demás y tiene que sentarse una vez.

Fija incluso caso, ahora óptimo: Si N es par, el uso de la misma tabla. Alguien se sienta en la cabeza. Los otros N-1 gire en torno a que el anterior. Cada uno habla con el, directamente a través de. Esto nos lleva de N-1 rondas en el caso, lo cual es óptimo. Lo siento a la par que ha de gritar el camino más largo.

El puente de los jugadores llaman a esto una Howell movimiento.

Answer 2

Tengo velocidad gay citas eventos y las cartas de asiento para 12 participantes hasta 22. Es un poco complejo, pero esencialmente usted divide la sala en 2 partes y después 1/2 la habitación conoce a los otros 1/2. Entonces básicamente hacer lo mismo para solo el 1/2 todo el camino hasta que todo el mundo ha conocido uno al otro.

Answer 3

Funciona de la misma como un torneo round robin. Este sitio web lo hace todo por ti: tournamentscheduler.net simplemente ingrese los nombres de los equipos y los números de la tabla para las localizaciones.