Adivinanza: Asignación de alumnos por grupos

Question

Supongamos que tienes una clase con 25 alumnos. Quiere asignar 6 tareas a lo largo del trimestre y que para cada una de ellas los alumnos trabajen en grupos de 5. Pero quiere hacerlo de forma que los alumnos trabajen en grupos de 5. Pero quiere hacerlo de forma que no haya dos alumnos que trabajen en el mismo grupo para dos tareas diferentes. ¿Es esto posible?

Lo he calculado para el caso de 25 alumnos en grupos de 5 y (creo) $m^2$ estudiantes agrupados en grupos de $m$ si $m$ es una primera potencia.

Pero estas no son todas las posibilidades. Las condiciones para que las situaciones funcionen son claramente si tienes $n$ personas colocadas en grupos de tamaño $k$ deberías tener eso $k$ divide n. Pero si quieres que funcione de manera que puedas tener a todo el mundo trabajando con todo el mundo exactamente una vez con tamaños de grupo constantes debería ser el caso $k-1$ divide $n-1$ ya que cada alumno trabaja con $k-1$ nuevos alumnos cada vez y tienen un total de $n-1$ estudiantes con los que eventualmente tengan que trabajar. Resulta que los números n que satisfacen esto son $k + s k(k-1)$ para cualquier número entero no negativo $s$ . Así que.., $s = 0$ es trivial y $s = 1$ corresponde a los cuadrados.

Así que mi pregunta es: ¿es necesariamente posible resolver esto cuando $s > 1$ . Es decir:

¿Es posible tomar una clase con $k+s k(k-1)$ alumnos, agrúpalos en grupos de tamaño $k$ para una serie de tareas de modo que todos trabajen con todos exactamente una vez?

Además, ¿qué ocurre en los casos en los que no hay un número primo de estudiantes?

Answer 1

El caso $s=1$ con $n=k^2$ estudiantes que reciben $k+1$ deberes en grupos de $k$ está directamente relacionado con el problema de encontrar $k-1$ cuadrados latinos mutuamente ortogonales de orden $k$ . En $m$ deberes para $k$ grupos de $k$ estudiantes cada uno, podemos construir $m-2$ cuadrados latinos mutuamente ortogonales de orden $k$ . Sea $a_{ij}$ sea el número del grupo en el que el alumno $i$ trabaja en el $j$ -th assignment. Asocie a cada alumno $j$ con la entrada $(a_{i1},a_{i2})$ de los cuadrados latinos a construir, es decir, el grupo del alumno en la primera tarea determina la fila y el grupo en la segunda tarea determina la columna. Como no hay dos alumnos que trabajen dos veces en el mismo grupo, se establece una biyección entre los alumnos y las entradas. Ahora utilice todas las tareas restantes para construir un cuadrado latino cada una, estableciendo la entrada $(a_{i1},a_{i2})$ a $a_{ij}$ (para $j=3,\ldots,n$ ). Dado que los estudiantes de un grupo para la asignación $j$ están en grupos diferentes para su asignación $1$ cada número sólo se escribe una vez por fila, y como están en grupos diferentes para la asignación $2$ Cada número sólo se escribe una vez por columna, por lo que se trata de cuadrados latinos. Y como están en grupos diferentes para cualquier tarea $j'\neq j$ dos entradas no pueden coincidir en $j$ y en $j'$ por lo que los cuadrados latinos son ortogonales por pares.

En treinta y seis oficiales problema propuesto por Euler en $1782$ pide un par de cuadrados latinos ortogonales de orden seis. Tarry ( $1901$ ) demostró mediante un extenso trabajo de casos que no existe tal par, y Stinson ( $1984$ ) y Burger, Kidd y van Vuuren ( $2011$ ) han ofrecido pruebas más breves; en las respuestas a la pregunta Cuadrado latino ortogonal 6*6 .

La no existencia de un par de cuadrados latinos ortogonales de orden $6$ implica que no sólo no se puede asignar $36$ estudiantes a $6$ grupos de $6$ para $7$ deberes de la manera deseada; ni siquiera puede hacerlo por $4$ deberes para casa.

Este es el único resultado que he podido encontrar que da una respuesta negativa a su pregunta. Para todos los demás casos, es decir, $s=1$ con $k\gt6$ y $s\gt1$ con cualquier $k$ los resultados publicados son compatibles con la existencia de tales asignaciones. La dirección Manual de diseños combinatorios contiene una tabla con límites inferiores sobre el número de cuadrados latinos mutuamente ortogonales de orden dado. En la mayoría de los casos, el límite inferior está bastante lejos del límite superior $n-1$ que necesita para sus tareas, es decir, puede que existan tales tareas pero hasta ahora no se ha encontrado ninguna. Secuencia OEIS A001438 da los números máximos conocidos de cuadrados latinos mutuamente ortogonales, pero sólo se conocen hasta $n=9$ por lo que no hay información nueva, ya que todos los números hasta $9$ excepto $6$ son potencias primos y por lo tanto permiten $n-1$ cuadrados. Harvey tenía una página de resultados (ahora archivada) para el problema del golfista social, pero los resultados parecen bastante débiles: los límites inferiores en la diagonal no tienen en cuenta la construcción de la potencia principal; los límites superiores por debajo de la diagonal (correspondientes a su $s\gt1$ ) no son más que los límites superiores triviales $\left\lfloor\frac{n-1}{k-1}\right\rfloor$ y los límites inferiores son en su mayoría inferiores a los superiores. El único caso para $s\gt1$ y $k\gt2$ para el que el límite inferior es igual al límite superior (de modo que se sabe que existe una solución a su problema) es $s=2$ , $k=3$ , $n=15$ para lo cual $7$ pueden asignarse a $5$ grupos de $3$ . Así pues, poco parece saberse sobre la existencia de soluciones para $s\gt1$ .