DE

Enero 2009

Luis Acosta Romero

Sergio Yansen Núñez

EJERCICIO

TÉCNICAS

CONTEO

PROBLEMA

Un curso tiene 289 alumnos que deben ser distribuidos en 17 grupos de igual cantidad. El curso es dividido en varios períodos y al inicio de cada período los grupos son redistribuidos, siempre de la misma manera. Dos alumnos que ya a han estado en un mismo grupo, no deben volver a estar juntos en un grupo. Determine el número máximo de períodos tal que es posible respetar estas condiciones.

Analicemos primero el caso para 9 alumnos, los cuales formarán 3 grupos de 3 alumnos.

Para objeto de facilitar la presentación de la resolución, se le asignará a cada alumno un número de 1 a 9. Al ordenar estos número en una matriz, se obtiene inmediatamente un solución. Los grupos serán las columnas de la matriz.

1 2 3

4 5 6

7 8 9

Se debe tener en cuenta que no interesa la cantidad de grupos que se pueda forma, sino que sea posible formarlos. Es así que partir por otros grupos es irrelevante para la solución que se busca.

Para formar los nuevos grupos, se desplazan los números marcados con rojo, en todos los lugares posible, de modo que no queden nuevamente en la misma columna, es decir, que no formen parte del mismo grupo. Para ello, se mantendrá la primera fila, los elementos de la segunda fila se moverán un lugar, y los de la segunda fila se moverán dos lugares, obteniéndose las siguientes posibilidades:

1 2 3

6 4 5

8 9 7

1 2 3

5 6 4

9 7 8

Aquí ya hay 3 soluciones al problema. Sin embargo está faltando una. Los elementos de una misma fila de la matriz, nunca han estado en una misma columna, por lo tanto, dan otra posibilidad de para formar grupos. Luego, tendremos 4 soluciones al problema, las cuales me muestran a continuación:

1 2 3

6 4 5

8 9 7

1 2 3

5 6 4

9 7 8

1 2 3

4 5 6

7 8 9

1 4 7

2 5 8

3 6 9

Veamos que ocurre con el caso de 16 alumnos, formando 4 grupos de 4 alumnos:

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

Al mover los elementos de la segunda fila en un lugar, los elementos de la segunda fila en dos lugares y los de la tercera fila en tres lugares, ocurre lo siguiente:

Primer Movimiento:

1 2 3 4

8 5 6 7

11 12 9 10

14 15 16 13

Segundo Movimiento:1 2 3 4

7 8 5 6

9 10 11 12

15 16 13 14

Note lo que ocurre con el segundo movimiento. El primer grupo tiene dos integrantes que ya estaban en un grupo anterior. Por lo tanto, el procedimiento utilizado para el caso de 9 alumnos, no es válido para este caso. Comencemos nuevamente con este caso. Una posibilidad para el primer grupo es la siguiente:

1 5 9 13

2 6 10 14

3 7 11 15

4 8 12 16

Cambiemos la primera fila y la primera columna entre si, obteniéndose la matriz:

1 2 3 4

5 6 10 14

9 7 11 15

13 8 12 16

Note que esta matriz no representa otra solución al problema, pues el segundo grupo tiene dos alumnos que estaban en el grupo anterior. En la región encerrada en azul,apliquemos un método similar al utilizado para el caso anterior; la primera fila se moverá una unidad hacia atrás y la segunda fila, dos unidades, obteniéndose:

1 2 3 4

5 6 10 14

9 11 15 7

13 16 8 12

Intercambiando ahora las dos zonas encerradas en rojo y desplazando los números encerrados en azul, tal como se hizo en el paso anterior, se obtiene una nueva solución:

1 2 3 4

6 5 9 13

10 15 7 11

14 12 16 8

Aquí tenemos una nueva solución al problema.

En esta matriz obtenida, se intercambia nuevamente los números en rojo. Note que los números 6, 10 y 14 deben ubicarse en la única alternativa posible, para que no se repitan con algún grupo anterior. Además, las zonas en azul se desplazan tal como se hizo anteriormente, obteniéndose la siguiente solución:

1 2 3 4

15 9 13 5

7 14 6 10

11 8 12 16

Aplicando la misma metodología, teniendo cuidado de ubicar los números 15, 7 y 11 en los únicos lugares posibles, se llega a lo siguiente:

1 2 3 4

8 13 5 9

12 10 14 6

16 7 11 15

Note como el 13 fue desplazándose en los últimos pasos.

Así obtenemos las 5 soluciones siguientes:

1 5 9 13

2 6 10 14

3 7 11 15

4 8 12 16

1 2 3 4

5 6 10 14

9 11 15 7

13 16 8 12

1 2 3 4

6 5 9 13

10 15 7 11

14 12 16 8

1 2 3 4

15 9 13 5

7 14 6 10

11 8 12 16

1 2 3 4

8 13 5 9

12 10 14 6

16 7 11 15

Analicemos que ocurre con el caso de 25 alumnos, y veamos que el procedimiento recién empleado nos permite llegar a las soluciones. No olvide que, más que buscar las soluciones, se debe centrar la atención en el cómo contar las soluciones. Comencemos con la primera solución:

1 6 11 16 21

2 7 12 17 22

3 8 13 18 23

4 9 14 19 24

5 10 15 20 25

Cambiando los elementos en rojo, y desplazando los números en azul, en uno, dos y tres espacios respectivamente, se obtiene:

1 2 3 4 5

6 7 12 17 22

11 13 18 23 8

16 24 29 9 14

21 25 10 15 20

Realicemos nuevamente las modificaciones a esta matriz. Obtendremos:

1 2 3 4 5

7 6 11 16 21

12 18 23 8 13

17 9 14 19 24

22 20 25 10 15

Estos números ya formaban parte de un grupo, por lo tanto, este procedimiento no nos permitió determinar la solución al problema. Note que la cantidad de elementos que se están desplazando es par. ¿Tendrá algo que ver esto?

Note lo que ocurre con los números 21 y 24.

Utilicemos el procedimiento que se utilizó para el caso de 9 alumnos. Recordemos que éste se iniciaba con:

1 6 11 16 21

2 7 12 17 22

3 8 13 18 23

4 9 14 19 24

5 10 15 20 25

Desplazaremos los número en azul, en un lugar la primera fila, en dos la segunda, y así hasta recorrer todas las columnas, obteniéndose:

Primer Movimiento:

1 6 11 16 21

22 2 7 12 17

18 23 3 8 13

14 19 24 4 9

10 15 20 25 5

Segundo Movimiento:

1 6 11 16 21

17 22 2 7 12

8 13 18 23 3

24 4 9 14 19

15 20 25 5 10

1 6 11 16 21

12 17 22 2 7

23 3 8 13 18

9 14 19 24 4

20 25 5 10 15

Tercer Movimiento: Cuarto Movimiento:

1 6 11 16 21

7 12 17 22 2

13 18 23 3 8

19 24 4 9 14

25 5 10 15 20

Los cuatro movimientos, mas la matriz original nos dan 5 soluciones, pero recuerde que el considerar las filas de la matriz como grupos, entrega una nueva solución. Por lo tanto, el problema tendrá 6 soluciones.

Note como en este caso, donde la cantidad de grupos es impar, bastó con ir desplazando los números de las filas de la matriz, salvo la primera, una cierta cantidad de veces, a fin de que todos los elementos de una fila recorran todas las columnas y que no se junten dos números nuevamente en la misma columna. Sin embargo, cuando la cantidad de grupos es par, este procedimiento no funciona, debido a que existirán elementos que volverán a una posición anterior. Es por ello que aparecen formas distintas de resolución, dependiendo si la cantidad de grupos es par o impar. ¿o no dependerá de ello…?

Miremos rápidamente el caso de 36 alumnos, es decir, 6 grupos. La solución son 7 períodos.

1 7 13 19 25 31

2 8 14 20 26 32

3 9 15 21 27 33

4 10 16 22 28 34

5 11 17 23 29 35

6 12 18 24 30 36

Primer Movimiento

1 2 3 4 5 6

7 8 14 20 26 32

13 15 21 27 33 9

19 22 28 34 10 16

25 29 35 11 17 23

31 12 18 24 30 36

Segundo Movimiento1 2 3 4 5 6

8 7 13 19 25 31

14 21 27 33 9 15

20 34 10 16 22 28

26 17 23 29 35 11

32 30 36 12 18 24

Tercer Movimiento

1 2 3 4 5 6

21 13 19 25 31 7

27 20 26 32 8 14

33 16 22 28 34 10

9 35 11 17 23 29

15 24 30 36 12 18

Cuarto Movimiento

1 2 3 4 5 6

16 19 25 31 7 13

22 32 8 14 20 26

28 15 21 27 33 9

34 23 29 35 11 17

10 18 24 30 36 12

Quinto Movimiento

1 2 3 4 5 6

23 25 31 7 13 19

29 14 20 26 32 8

35 33 9 15 21 27

11 22 28 34 10 16

17 12 18 24 30 36

Sexto Movimiento

1 2 3 4 5 6

12 31 7 13 19 25

18 26 32 8 14 20

24 21 27 33 9 15

30 16 22 28 34 10

36 11 17 23 29 35

Aquí aparecen las 7 soluciones del problema.

Solución al problema original:

Teniendo 289 alumnos, al formar 17 grupos deberíamos pensar en una matriz de 17 filas y 17 columnas

1 18 35 52 69 86 103 120 137 154 171 188 205 222 239 256 273

2 19 36 53 70 87 104 121 138 155 172 189 206 223 240 257 274

3 20 37 54 71 88 105 122 139 156 173 190 207 224 241 258 275

4 21 38 55 72 89 106 123 140 157 174 191 208 225 242 259 276

5 22 39 56 73 90 107 124 141 158 175 192 209 226 243 260 277

6 23 40 57 74 91 108 125 142 159 176 193 210 227 244 261 278

7 24 41 58 75 92 109 126 143 160 177 194 211 228 245 262 279

8 25 42 59 76 93 110 127 144 161 178 195 212 229 246 263 280

9 26 43 60 77 94 111 128 145 162 179 196 213 230 247 264 281

10 27 44 61 78 95 112 129 146 163 180 197 214 231 248 265 282

11 28 45 62 79 96 113 130 147 164 181 198 215 232 249 266 283

12 29 46 63 80 97 114 131 148 165 182 199 216 233 250 267 284

13 30 47 64 81 98 115 132 149 166 183 200 217 234 251 268 285

14 31 48 65 82 99 116 133 150 167 184 201 218 235 252 269 286

15 32 49 66 83 100 117 134 151 168 185 202 219 236 253 270 287

16 33 50 67 84 101 118 135 152 169 186 203 220 237 254 271 288

17 34 51 68 85 102 119 136 153 170 187 204 221 238 255 272 289

Así, los 17 movimientos que puede realizar el alumno 2, representa los 17 grupos con personas distintas que se pueden realizar, además del grupo que se puede considerar con las filas de la matriz.

Por lo tanto, durante 18 períodos es posible formar grupos con las condiciones solicitadas.