Algoritmo combinatorio para asignar personas a grupos

Question

Un compañero de trabajo vino a mí con un problema interesante, uno práctico que tiene que ver con un grupo de "gente nueva en la ciudad" del que es parte.

18 amigos quieren cenar en grupos para cada uno de los próximos 4 días. Las reglas son como sigue:

1. Cada día el grupo se divide en 4 grupos de 4, y un grupo de 2.
2. cualquier par de personas dado sólo verá entre sí como máximo una vez en el transcurso de los 4 días.
3. Cualquier persona determinada solo será parte del grupo de tamaño 2 como máximo una vez.

Una fuerza bruta de búsqueda recursiva para un conjunto válido de asignación de grupo es obviamente impracticable. Introduje una lógica simple para podar partes del árbol lo antes posible, pero no lo suficiente como para hacerlo práctico.

En realidad, estoy empezando a sospechar que podría ser imposible seguir todas las reglas, pero no puedo presentar un argumento combinatorio sobre por qué sería eso.

¿Alguna idea?

Answer 1

16 amigos se pueden programar 4x4 por 4 noches con dos mutually orthogonal latin squares de la orden 4. Asignar a cada amigo a una posición distinta en la cuadrícula de 4x4. En la primera noche, grupo por fila. En el segundo, grupo por columna. En el tercero, agrupe por entrada similar en la casilla latina # 1 (rango de la tarjeta en el ejemplo 4x4). En el cuarto, agrupa por entrada similar en la casilla latina n. ° 2 (palo de carta en el ejemplo 4x4). De hecho, la construcción del avión afín da lugar a tres plazas latinas mutuamente ortogonales, por lo que se podría programar una quinta noche, lo que garantiza que cada par de amigos se reúna exactamente una vez.

Tal vez el horario para 16 podría extenderse, utilizando la libertad de la quinta noche no utilizada.

EDITAR: aquí está el horario para 16 personas durante 5 noches. Cada fila es una noche. Cada columna es una persona La entrada es el grupo al que están asignados.

[0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3] 
[0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3] 
[0, 1, 2, 3, 1, 0, 3, 2, 2, 3, 0, 1, 3, 2, 1, 0] 
[0, 2, 3, 1, 1, 3, 2, 0, 2, 0, 1, 3, 3, 1, 0, 2] 
[0, 3, 1, 2, 1, 2, 0, 3, 2, 1, 3, 0, 3, 0, 2, 1]