Tienen 40 personas en 4 tablas: cómo cambiar las tablas de modo que el mínimo número posible de personas están sentados con alguien en su tabla original

Question

Tan sólo unos simples premisas:

• 40 personas, 10 personas por mesa
• En algún punto en el que desea cada uno para cambiar las tablas, y tienen un par de personas como sea posible sentarse en una mesa con alguien que se sentó con la primera vez.

Esta no es una tarea problema--este es un problema que me estoy encontrando mientras intentaba organizar un evento de networking. Hay dos preguntas principales:

1) Es posible idear una reasignación esquema estaban todo el mundo está sentado con un totalmente nuevo de la multitud?

2) Suponiendo que la respuesta a (1) es no, lo que es razonable de un algoritmo para la reasignación de que hará que tantas personas como sea posible, están sentados con nuevas personas en su nueva tabla.

La razón por la que creo que la respuesta a (1) es "No", es porque hice 100k simulaciones de azar de mesa de reasignación para cada persona (el código de abajo), desde que descubrí que había cero tiempos donde nadie estaba sentado en una mesa con alguien que se sentó en la primera ronda. En promedio, el máximo "redundante" de la tabla (es decir, el que tenía la mayoría de las personas que fueron previamente se sentaron juntos), tuvo alrededor de 4.65 personas que se sentaron el uno con el otro la primera vez, y había cerca de un 87% de probabilidad de que el número de 4 o 5. El min parecía ser 3.

Más allá de lo que realmente no puedo envolver mi cabeza alrededor de este. Si hay un nombre para este tipo de problemas, por favor hágamelo saber, o, mejor aún, si usted tiene una buena respuesta, vamos a escuchar. Gracias!

M = rep(0,100000)
x <- rep(1:4, each=10)
for(k in 1:100000)
{
 s <- sample( 1:40, 40 ) 
 x2 <- x[s]
 m1 <- max( summary(as.factor(x2[1:10])) ) 
 m2 <- max( summary(as.factor(x2[11:20])) ) 
 m3 <- max( summary(as.factor(x2[21:30])) ) 
 m4 <- max( summary(as.factor(x2[31:40])) )  
 M[k] <- max( c(m1,m2,m3,m4) ) 
 if( M[k] == 0 ) print(s) 
}

Answer 1

[I puede regresar con algunos comentarios adicionales a los punteros en la parte posterior, ya que esta respuesta no tiene en la actualidad sugieren un algoritmo general; va más allá de 3 sesiones, en particular, no es en general un problema resuelto, aunque hay algunas estrategias útiles, y una gran cantidad de conexiones a problemas relacionados.]

Esto está estrechamente relacionado con el social golfista problema (" $g$ grupos de $k$ golfistas juegan para $w$ semanas sin jugar con alguien que haya jugado anteriormente?"). [El original de dicho problema - hace 20 años - considerado 8 grupos de cuatro jugadores de golf, y se preguntó cuántas semanas se podría jugar sin la repetición de los socios. 11 semanas podría ser descartada, por lo que el interés se centró en si 10 semanas fue posible, para que la respuesta finalmente resultó ser 'sí'.]

Hay también mucho mayores Kirkman colegiala problema, que se refiere a las 15 chicas caminando en tripletes de una vez cada día y preguntando cómo pueden hacer esto por 7 días sin que nadie caminando con alguien que anteriormente ha acompañado.

[Hay una serie de variantes en el social golfista problema. Algunas de ellas pueden relacionarse más directamente a su problema.]

Estos problemas también están íntimamente relacionadas con el diseño experimental en las estadísticas (por ejemplo, muchas de las soluciones óptimas de los social golfista problema - arreglos de dar el mayor $w$ por $g,k$ - son resolverse equilibrada diseños de bloque incompleto, o RBIBDs).

En relación a tus dos preguntas:

1. Esto es posible para todo el mundo a evitar que alguien que he tenido antes en su segundo 'sentado' si hay al menos tantas tablas como personas por mesa (es decir, el tamaño de la tabla no es más que la raíz cuadrada del número de invitados).

   En efecto, si las mesas son 'pequeños' en este sentido, usted debería ser capaz de obtener al menos 3 consecutivos arreglos - "sesiones" - donde todo el mundo se sienta con toda la gente nueva cada vez.

   Así, por ejemplo, para 8 mesas de 5 personas yo tengo una solución a la mano para hasta 6 "sesiones" (esto puede haber sido superado, más recientemente, ya que los resultados que estoy viendo en este momento son bastante antiguos). Generalmente hablando, la más pequeña de las tablas, el más 'social' de audiencias, que pueden ser acomodados.

   Su caso ha 'grandes' tablas (más personas por mesa de tablas) así que no hay 'social' de la segunda sesión.

2. Tres personas juntas que han estado juntos antes, será el mínimo alcanzable con una segunda ronda y 4 mesas de 10.

   Podemos ver bastante fácilmente que no puede ser de 2 (esto es probablemente lo que whuber es llegar a por la elevación de la generalizada principio del palomar). Considerar a las personas de la tabla; en la primera sesión hemos sello de su mano con una 'a'. Ahora ordenamos en pares, en las cuatro tablas, dos en la mesa de Un, dos en la tabla B, dos en la tabla C, dos en la tabla D. ¿Qué vamos a hacer con las dos a la izquierda? Deben sentarse en las mesas que ya tiene un par de personas con "un" sellos.

   En consecuencia, el número mínimo de alcanzable repite no puede ser inferior a tres. Podríamos considerar la posibilidad de que podría ser mayor que tres, pero ya que usted ya tiene una solución en la que es de tres, usted sabe que es alcanzable, no haga falta perder más esfuerzo tratando de establecer que tres es posible.

   Usted podría entonces tratando de minimizar el número de "tres turbas" / maximizar el número de dobles-ups.

   Claramente se puede obtener un promedio de "2.5" en la segunda sesión (la mitad de la gente se sienta con otros 2 que ya se sentó con la mitad con una persona que ya se sentó con). Aquí las letras minúsculas se refieren a la "sellos" en sus manos (es decir, la tabla de personas estaban en la primera sesión):

     A: aaabbcccdd
     B: aabbbccddd
     C: aaabbcccdd
     D: aabbbccddd
   

   Este debe ser el mejor posible de lograr. De las 9 personas en la mesa en la ronda 2, en promedio 7.5 de ellos son "nuevos" y 1.5 de ellos ya hemos sentado con.