Estrategias de conteo, De cuantas formas...
- ¿De cuántas formas pueden separarse 5000 sobres idénticos en paquetes de 50 entre cuatro grupos estudiantes, de modo que cada grupo tenga al menos 250 pero no más de 1500 sobres?.
Solo pude resolver esta parte:
5000 sobres en paquetes de 50 son 100 paquetes, 250 sobres en paquetes de 50 son 5 y 1500 sobres iguales en paquetes de 50 son 30.
El problemas se reduce a partir de 100 paquetes iguales en 4 grupos de estudiantes de modo que cada grupo reciba al menos 5 paquetes pero no más de 30.
Es decir (x^5+x^6+... X^30)^4 siendo la solución del problema el coeficiente x^100
Función generatriz:
x^5+x^6+...x^30=x^5(1+x+...x^25)
Solo pude resolver esta parte.
1 Respuesta
·
·
¡Hola Carolinaboni!
Efectivamente, simplificamos los números y es como repartir 100 cosas entre 4 personas de modo que cada una reciba entre 5 y 30 inclusives
La función generatriz es
(x^5+x^6+...+x^30)^4 =
Y debemos encontrar el coficiente 100
Veo que has hecho una simplificación
[x^5(1+x^2+ ... + x^25)]^4 = x^20·(1+x^2+...+x^25)^4
Luego podemos tomar la función
(1+x^2+...+x^25)^4
y buscarle el coeficiente de x^80
Esto son las soluciones enteras no negativas de
x + y + z + t = 80
que son
CR(4,80)
Pero ahora tienes que aplicar el principio de inclusión-exclusión, primero quitas las que tienen un número mayor de 25 y queda
CR(4,80) - C(4,1)·CR(4,55)
Ahora sumas las tienen dos números mayores de 25
CR(4,80) - C(4,1)·CR(4,55) + C(4,2)·CR(4,30)
y finalmente restas las que tienen tres números mayores de 25
CR(4,80) - C(4,1)·CR(4,55) + C(4,2)·CR(4,30) - C(4,3)·CR(4,5)=
Y no se puede continuar porque no puede haber 4 números mayores de 25.
Traducimos esa cifra a combinaciones normales
C(83,80) - 4·C(58,55) + 6·C(33,30) - 4·C(8,5) =
A mi me gustan los combinatorios simétricos para hacer las cuentas a mano
C(83,3) - 4·C(58,3) + 6·C(33,3) - 4·C(8,3) =
83·82·81/6 - 4·58·57·56/6 + 6·33·32·31/6 - 4·8·7·6/6=
83·41·27 - 2·58·19·56 + 33·32·31 - 4·8·7 = 969
·
Y se puede comprobar si esta bien, voy a desarrollar la función generatriz con programa Máxima:
(1+x^2+...+x^25)^4=
·
·
Lo tengo que dejar aquí por varias horas, no me da ese resultado, el coeficiente de x^80 es 1771 mientras que 969 también sale, pero es el coeficiente de x^84. Y ya llevo mucho rato y yo no encuentro el fallo que he podido cometer, para mi que estas cuentas tendrían que dar el coeficiente de x^80 pero no lo dan. A lo mejor estoy cometiendo unfallo tan tonto que no me doy cuenta mira a ver si lo encuentras tú.
Espera que creo que ya he visto el fallo, estaba excluyendo combinaciones válidas, aquellas en las que uno de los grupos tenía 25 paquetes que es el máximo y es válido. La cadena correcta de inclusión exclusión es esta:
CR(4,80) - C(4,1)·CR(4,54) + C(4,2)·CR(4,28) - C(4,3)·CR(4,2)=
C(83,80) - 4·C(57,54) + 6·C(31,28) -4·C(5,2) =
C(83,3) - 4·C(57,3) + 6·C(31,3) - 4·C(5,2) =
83·82·81/6 - 4·57·56·55/6 + 6·31·30·29/6 - 4·5·4/2 =
83·41·27 - 2·19·56·55 + 31·30·29 - 40 = 1771
¡BIIEEN!
Y eso es todo, saludos.
:
:
