Hay 25 estudiantes en una clase que se sientan en cinco filas de cinco. Cada semana se sentarán en un orden diferente.
Después de un número de semanas que cada estudiante se ha sentado junto a todos los alumnos de los otros, el siguiente significado al lado del otro, uno detrás del otro, o sentado en diagonal juntos. ¿Cuál es el menor número de semanas en las que esto puede suceder?
El caso de los 16 a los estudiantes sentados en cuatro filas de cuatro ha sido resuelto en:
Se puede hacer en 5 semanas:
01 02 03 04 05 14 07 04 12 17
06 07 08 09 10 25 18 22 01 20
11 12 13 14 15 02 09 03 13 08
16 17 18 19 20 16 23 06 21 24
21 22 23 24 25 10 19 05 15 11
09 19 02 14 17 02 22 23 12 24
07 21 12 05 03 15 13 14 09 08
23 25 01 24 11 10 18 11 01 17
04 15 08 10 22 21 05 16 19 06
13 16 18 06 20 07 20 03 25 04
06 16 07 15 12
14 24 17 10 03
21 04 02 25 13
18 20 11 22 05
09 01 23 08 19
He utilizado un método relativamente simple programa de computadora para producir los últimos cuatro asientos. Se utiliza una "escalada" de la optimización, es decir, que en repetidas ocasiones trató de intercambio para los estudiantes al azar, y si el número total de pares adyacentes aumento, a continuación, mantenga el swap o bien volverlas a colocar. Para producir una disposición de los asientos, se ejecuta el mencionado optimización de un par de veces a partir de un azar de los asientos y, a continuación, elige el mejor uno se encuentra (es decir, el que presenta la mayoría de los nuevos pares dio ninguna de las anteriores semanas arreglos ya elegido). Tuve entonces producir conjuntos de 5 asientos hasta que se encuentra un conjunto que contiene todos los pares.
También he puesto mi programa para encontrar soluciones a $N=6$. Se encontraron 7 semanas de solución:
01 02 03 04 05 06 12 33 14 22 08 16
07 08 09 10 11 12 05 23 35 04 06 36
13 14 15 16 17 18 32 15 19 07 26 09
19 20 21 22 23 24 01 24 11 28 17 25
25 26 27 28 29 30 21 13 10 02 20 34
31 32 33 34 35 36 29 31 30 27 18 03
01 25 29 27 13 34 22 35 27 13 23 20
14 03 05 16 02 06 31 14 36 03 12 21
32 17 19 31 18 15 26 24 11 08 10 18
35 21 33 09 36 07 15 34 25 07 19 06
10 08 30 20 12 28 30 28 16 32 29 33
23 26 11 22 04 24 09 01 04 02 05 17
14 18 08 20 10 19 16 02 08 10 11 09
28 05 32 29 01 34 20 34 14 33 21 35
26 13 09 11 31 12 22 04 29 15 03 05
03 22 35 23 27 15 36 19 31 07 30 18
07 24 02 25 04 17 24 17 27 23 32 25
16 33 36 21 06 30 13 26 01 06 28 12
19 30 14 03 28 17
02 12 16 06 31 08
29 26 35 20 24 27
04 18 01 05 07 09
13 33 22 36 34 21
15 25 10 32 23 11
No es un simple límite inferior. Hay $N^2$ a los estudiantes, por lo que hay $N^2(N^2-1)/2$ parejas de estudiantes que necesitan sentarse uno al lado del otro en algún momento. El número de pares adyacentes en una semana la disposición de los asientos es $2N(N-1) + 2(N-1)^2 = 2(N-1)(2N-1)$. Dividir para obtener un límite inferior en el número de semanas. Tenga en cuenta que este crece cuadráticamente en $N$.
Para $N=5$ obtenemos $300/72=4.167$ lo $5$ semanas son necesarias.
Para $N=6$ obtenemos $630/110=5.727$ lo $6$ semanas son necesarias.
Sin embargo, dado lo difícil que era encontrar un 7-semana de la solución, es casi seguro que no es posible alcanzar en 6 semanas.
Las siguientes son sesiones por siete semanas que permiten a todos conocer a todos los demás:
Week 1 Week 2 Week 3
[ 0 1 2 3 4] [18 16 19 15 17] [ 7 9 5 8 6]
[ 5 6 7 8 9] [ 8 6 9 5 7] [ 2 4 0 3 1]
[10 11 12 13 14] [23 21 24 20 22] [17 19 15 18 16]
[15 16 17 18 19] [ 3 1 4 0 2] [12 14 10 13 11]
[20 21 22 23 24] [13 11 14 10 12] [22 24 20 23 21]
Week 4 Week 5 Week 6
[ 8 15 1 20 13] [20 12 1 19 7] [22 14 7 0 12]
[11 22 19 3 18] [11 9 5 10 21] [20 16 21 4 3]
[ 4 6 17 24 5] [17 8 22 14 23] [17 1 6 5 23]
[ 2 14 10 9 16] [24 13 4 3 15] [13 18 8 2 15]
[21 12 23 7 0] [ 2 18 0 16 6] [ 9 19 10 11 24]
Week 7
[ 1 10 21 7 4]
[ 3 19 17 18 24]
[15 11 0 22 5]
[12 16 23 20 13]
[19 2 8 6 9]
Esta es sólo una respuesta parcial, lo que demuestra que el menor número de semanas en las que esto puede suceder es $5$ o $6$. Sospecho que el número de es $5$, pero no tengo una prueba.
A ver que, al menos, $5$ sesiones son necesarias, tenga en cuenta que se requiere un total de $\tbinom{25}{24}=300$ reuniones entre los estudiantes. Un rápido recuento muestra que hay $$\frac12(4\times3+12\times5+9\times8)=72,$$ reuniones para cada sesión, así que vamos a necesitar, al menos, $5$ semanas para que todos los estudiantes alcancen.
Aquí es una serie de seis sesiones en las que cada estudiante cumple con todos los otros estudiantes, que he construido y comprobado por la mano, por lo que puede ser un error. El tiempo dedicado a la construcción de este me convence de que es muy probable que sea posible en sólo cinco sesiones; sin (también) mucho esfuerzo, las primeras cinco sesiones de miss sólo $20$ parejas de estudiantes.
01 02 03 04 05
06 07 08 09 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
17 19 22 06 15
08 01 09 24 05
20 18 11 02 14
16 03 10 21 04
13 25 12 23 07
18 25 14 03 24
21 17 06 19 12
02 05 13 04 15
23 20 07 16 01
11 09 10 22 08
09 02 03 07 18
12 25 15 17 04
05 22 23 08 24
11 13 21 01 16
14 20 06 19 10
21 15 13 10 08
24 12 01 25 11
07 14 03 05 04
09 23 16 22 20
17 06 18 02 19
25 07 01 11 15
24 04 19 14 18
13 10 08 05 22
17 02 06 09 23
20 12 21 03 16
Aquí es una serie de siete sesiones en las que cada estudiante cumple con todos los otros estudiantes:
01 02 03 04 05
06 07 08 09 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
17 19 18 15 06
13 01 16 05 24
12 20 03 22 14
02 21 10 25 04
09 11 08 23 07
21 25 10 14 03
18 17 02 08 23
20 04 15 11 05
19 06 01 07 13
22 12 16 09 24
04 10 25 16 20
14 06 13 23 08
03 21 24 11 17
18 01 12 22 07
02 05 19 09 15
06 14 07 21 01
09 17 13 15 25
04 11 03 12 23
20 24 19 02 10
22 08 18 05 16
08 06 03 17 24
22 01 23 20 05
21 14 10 09 25
13 04 07 18 11
02 16 12 19 15
11 12 20 07 05
06 14 01 21 23
18 16 10 19 03
02 24 04 08 09
13 22 15 17 25
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
