Ejercicio 15. Seccion 4.5
59 views
Skip to first unread message
Exequiel Saucedo
May 18, 2011, 8:52:01 PM5/18/11
to tcomp-fich-unl
Hola chicos,queria saber si me pueden ayudar con el ejercicio 15 de la
seccion 4.5!Muchas gracias!
seccion 4.5!Muchas gracias!
Diego Galizzi
May 19, 2011, 9:59:56 AM5/19/11
to tcomp-fich-unl
On May 18, 9:52 pm, Exequiel Saucedo <exequiel_cuer...@hotmail.com>
wrote:
de entre 21. Es decir, tenemos 21 números unos (tal que su suma es
21), y tenemos que tomar cinco grupos que corresponden a cada x_i.
Para separar los unos por grupos, podemos agregar 4 barras que los
separen, por ejemplo:
1 | 1 1 1 | 1 1 1 1 1 1 1 | 1 1 1 1 1 1 1 | 1 1 1
Equivale a :
x_1 = 1
x_2 = 3
x_3 = 7
x_4 = 7
x_5 = 3
Claramente sum(x_i) = 21
Otro ejemplo:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 | | 1 1 1 1 1 1 | |
Equivale a:
x_1 = 15
x_2 = 0
x_3 = 6
x_4 = 0
x_5 = 0
Entonces, la cantidad de soluciones posibles sin restricciones es la
cantidad de formas de ubicar 4 barras en 25 (21 unos más 4 barras)
posiciones. Esto es:
C(25, 4) = 12650
El ejercicio nos plantea que hagamos esto, pero con ciertas
restricciones. Desde ya, todos los incisos van a dar un número menor
que 12650.
En el (a) nos dice que x_1 >= 1. Entonces simplemente le damos un 1 a
x_1. Y hacemos lo mismo que antes, pero donde hay 20 unos (ya le dimos
uno a x_1) y 4 barras. Esto es:
C(24, 4) = 10626
En el (b) nos dice que todos los x_i >= 2. De forma análoga, le damos
2 unos a cada x_i, 10 unos en total. De esta forma nos quedamos con 11
unos para repartir. Entonces:
C(15, 4) = 1365
El (c) ya es distinto, porque nos da una restricción máxima, nos dice
que x_1 <= 10. O sea, que no le podemos asignar más de 10 unos a x_1.
Pero podemos ver que lo que buscamos es lo mismo que la cantidad de
soluciones totales menos la cantidad de soluciones donde x_1 > 10.
Entonces, le damos 11 unos a x_1, nos quedan 10 para repartir,
entonces tenemos:
C(14, 4) = 1001 cantidad de soluciones donde x_1 > 10.
La cantidad de soluciones sin restricciones la calculé antes, y es:
C(25, 4) = 12650.
Finalmente, la cantidad de soluciones donde x_1 <= 10, son:
C(25, 4) - C(14, 4) = 11649
Para el (d) es hacer lo que venimos haciendo, teniendo un poco de
cuidado. De entrada le asignamos 15 unos a x_3 y un uno a x_2. Nos
quedan 5 unos para repartir, entonces hay:
C(9, 4) = 126 soluciones.
(recordar que el 9 se debe a los 5 unos más las 4 barras)
Sin embargo, hay más restricciones, x_1 <= 3, hacemos lo mismo que en
el inciso anterior, y le damos 4 unos a x_1 para luego restar estas
soluciones. Nos queda 1 sólo uno, entonces hay:
C(5, 4) = 5
La última restricción que nos queda por tener en cuenta es x_2 < 4, de
la misma forma, le damos 4 unos a x_2 y hacemos la resta. Recordemos
que a x_2 ya le habíamos dado un uno, por lo que sólo tenemos que
darle 3 unos más. Nos quedan 2 unos, entonces hay:
C(6, 4) = 15
Finalmente, hacemos la resta:
C(9, 4) - C(5, 4) - C(6, 4) = 126 - 5 - 15 = 106
Saludos, Diego.
wrote:
> Hola chicos,queria saber si me pueden ayudar con el ejercicio 15 de la
> seccion 4.5!Muchas gracias!
Hola, pensalo como que tenes que elegir cinco grupos de números unos,
> seccion 4.5!Muchas gracias!
de entre 21. Es decir, tenemos 21 números unos (tal que su suma es
21), y tenemos que tomar cinco grupos que corresponden a cada x_i.
Para separar los unos por grupos, podemos agregar 4 barras que los
separen, por ejemplo:
1 | 1 1 1 | 1 1 1 1 1 1 1 | 1 1 1 1 1 1 1 | 1 1 1
Equivale a :
x_1 = 1
x_2 = 3
x_3 = 7
x_4 = 7
x_5 = 3
Claramente sum(x_i) = 21
Otro ejemplo:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 | | 1 1 1 1 1 1 | |
Equivale a:
x_1 = 15
x_2 = 0
x_3 = 6
x_4 = 0
x_5 = 0
Entonces, la cantidad de soluciones posibles sin restricciones es la
cantidad de formas de ubicar 4 barras en 25 (21 unos más 4 barras)
posiciones. Esto es:
C(25, 4) = 12650
El ejercicio nos plantea que hagamos esto, pero con ciertas
restricciones. Desde ya, todos los incisos van a dar un número menor
que 12650.
En el (a) nos dice que x_1 >= 1. Entonces simplemente le damos un 1 a
x_1. Y hacemos lo mismo que antes, pero donde hay 20 unos (ya le dimos
uno a x_1) y 4 barras. Esto es:
C(24, 4) = 10626
En el (b) nos dice que todos los x_i >= 2. De forma análoga, le damos
2 unos a cada x_i, 10 unos en total. De esta forma nos quedamos con 11
unos para repartir. Entonces:
C(15, 4) = 1365
El (c) ya es distinto, porque nos da una restricción máxima, nos dice
que x_1 <= 10. O sea, que no le podemos asignar más de 10 unos a x_1.
Pero podemos ver que lo que buscamos es lo mismo que la cantidad de
soluciones totales menos la cantidad de soluciones donde x_1 > 10.
Entonces, le damos 11 unos a x_1, nos quedan 10 para repartir,
entonces tenemos:
C(14, 4) = 1001 cantidad de soluciones donde x_1 > 10.
La cantidad de soluciones sin restricciones la calculé antes, y es:
C(25, 4) = 12650.
Finalmente, la cantidad de soluciones donde x_1 <= 10, son:
C(25, 4) - C(14, 4) = 11649
Para el (d) es hacer lo que venimos haciendo, teniendo un poco de
cuidado. De entrada le asignamos 15 unos a x_3 y un uno a x_2. Nos
quedan 5 unos para repartir, entonces hay:
C(9, 4) = 126 soluciones.
(recordar que el 9 se debe a los 5 unos más las 4 barras)
Sin embargo, hay más restricciones, x_1 <= 3, hacemos lo mismo que en
el inciso anterior, y le damos 4 unos a x_1 para luego restar estas
soluciones. Nos queda 1 sólo uno, entonces hay:
C(5, 4) = 5
La última restricción que nos queda por tener en cuenta es x_2 < 4, de
la misma forma, le damos 4 unos a x_2 y hacemos la resta. Recordemos
que a x_2 ya le habíamos dado un uno, por lo que sólo tenemos que
darle 3 unos más. Nos quedan 2 unos, entonces hay:
C(6, 4) = 15
Finalmente, hacemos la resta:
C(9, 4) - C(5, 4) - C(6, 4) = 126 - 5 - 15 = 106
Saludos, Diego.
Damian Schlimovich
May 20, 2011, 9:22:02 AM5/20/11
to tcomp-f...@googlegroups.com
Sr Profesor, el ejercicio 21 de la 4.5, te pide la cantidad de formas de
distribuir 6 bolas INDISTINGUIBLES en 9 cajas distinguibles. El teorema 4 es
para objetos distinguibles, quice probar haciendo q las 6 bolas sean de un
tipo--->9!/6! Pero el resultado es dif. Rosen en el solucionario
usa el Teorema 2, por que?
distribuir 6 bolas INDISTINGUIBLES en 9 cajas distinguibles. El teorema 4 es
para objetos distinguibles, quice probar haciendo q las 6 bolas sean de un
tipo--->9!/6! Pero el resultado es dif. Rosen en el solucionario
usa el Teorema 2, por que?
Damián E. Schlimovich
Vice - Director de Relaciones Públicas 2010-2011
Rotaract Club de Paraná (4940)
"fortalecer comunidades, unir continentes"
Visitá nuestra web: www.rotaractparana.org.ar
-----Mensaje original-----
De: tcomp-f...@googlegroups.com [mailto:tcomp-f...@googlegroups.com]
En nombre de Diego Galizzi
Enviado el: jueves, 19 de mayo de 2011 11:00 a.m.
Para: tcomp-fich-unl
Asunto: [tcomp-fich-unl] Re: Ejercicio 15. Seccion 4.5
Diego Galizzi
May 20, 2011, 10:19:59 AM5/20/11
to tcomp-fich-unl
On May 20, 10:22 am, "Damian Schlimovich" <damian.pn...@gmail.com>
wrote:
organizado.
Olvidate de los teoremas, lo que importa es el razonamiento. Más
importante que lo que dice el teorema 2, es su demostración. El
ejercicio 21 lo podes ver como el 15 que respondí antes. Ahora tenés
que armar 9 grupos de bolas, donde tenemos 6 bolas en total. Esto se
puede resolver separando las bolas con barras, indicando a que caja le
corresponden las bolas. Por ejemplo:
x | x | | x x | x | | | x |
En este caso tenemos:
caja 1: 1 bola
caja 2: 1 bola
caja 3: ninguna
caja 4: 2 bolas
caja 5: 1 bola
caja 6: ninguna
caja 7: ninguna
caja 8: 1 bola
caja 9: ninguna
Otro ejemplo
| | | | | | | | x x x x x x
La caja 9 tiene las 6 bolas, el resto de las cajas están vacías.
Entonces, para hacer esto, tenemos que colocar las 8 barras entre las
6 bolas. Tenemos un total de 8+6 lugares, donde queremos ubicar las 8
barras. Entonces hay:
C(8+6, 8) = 3003 posibilidades.
Fijate que es lo mismo si dejamos las barras fijas, y elegimos las
bolas:
C(8+6, 6) = 3003
El teorema 2 lo que te dice es eso, siempre podes separar n grupos con
(n-1) barras. Entonces, vas a tener (n - 1 + r) lugares, de donde
queres ubicar (n-1) dejando los r elementos fijos:
C(n - 1 + r, n - 1)
De nuevo, lo podés pensar dejando las (n-1) barras fijas, y ubicando
los r elementos:
C(n - 1 + r, r)
Si no entendes bien por que las dos formas son igualmente válidas,
quizás te sirva ver el corolario 1 de la sección 4.3.
wrote:
> Sr Profesor, el ejercicio 21 de la 4.5, te pide la cantidad de formas de
> distribuir 6 bolas INDISTINGUIBLES en 9 cajas distinguibles. El teorema 4 es
> para objetos distinguibles, quice probar haciendo q las 6 bolas sean de un
> tipo--->9!/6! Pero el resultado es dif. Rosen en el solucionario
> usa el Teorema 2, por que?
>
> Damián E. Schlimovich
> Vice - Director de Relaciones Públicas 2010-2011
>
> Rotaract Club de Paraná (4940)
>
> "fortalecer comunidades, unir continentes"
>
> Visitá nuestra web: www.rotaractparana.org.ar
>
Primero, es mejor si creas un hilo nuevo de emails, así queda más
> distribuir 6 bolas INDISTINGUIBLES en 9 cajas distinguibles. El teorema 4 es
> para objetos distinguibles, quice probar haciendo q las 6 bolas sean de un
> tipo--->9!/6! Pero el resultado es dif. Rosen en el solucionario
> usa el Teorema 2, por que?
>
> Damián E. Schlimovich
> Vice - Director de Relaciones Públicas 2010-2011
>
> Rotaract Club de Paraná (4940)
>
> "fortalecer comunidades, unir continentes"
>
> Visitá nuestra web: www.rotaractparana.org.ar
>
organizado.
Olvidate de los teoremas, lo que importa es el razonamiento. Más
importante que lo que dice el teorema 2, es su demostración. El
ejercicio 21 lo podes ver como el 15 que respondí antes. Ahora tenés
que armar 9 grupos de bolas, donde tenemos 6 bolas en total. Esto se
puede resolver separando las bolas con barras, indicando a que caja le
corresponden las bolas. Por ejemplo:
x | x | | x x | x | | | x |
En este caso tenemos:
caja 1: 1 bola
caja 2: 1 bola
caja 3: ninguna
caja 4: 2 bolas
caja 5: 1 bola
caja 6: ninguna
caja 7: ninguna
caja 8: 1 bola
caja 9: ninguna
Otro ejemplo
| | | | | | | | x x x x x x
La caja 9 tiene las 6 bolas, el resto de las cajas están vacías.
Entonces, para hacer esto, tenemos que colocar las 8 barras entre las
6 bolas. Tenemos un total de 8+6 lugares, donde queremos ubicar las 8
barras. Entonces hay:
C(8+6, 8) = 3003 posibilidades.
Fijate que es lo mismo si dejamos las barras fijas, y elegimos las
bolas:
C(8+6, 6) = 3003
El teorema 2 lo que te dice es eso, siempre podes separar n grupos con
(n-1) barras. Entonces, vas a tener (n - 1 + r) lugares, de donde
queres ubicar (n-1) dejando los r elementos fijos:
C(n - 1 + r, n - 1)
De nuevo, lo podés pensar dejando las (n-1) barras fijas, y ubicando
los r elementos:
C(n - 1 + r, r)
Si no entendes bien por que las dos formas son igualmente válidas,
quizás te sirva ver el corolario 1 de la sección 4.3.
Diego Galizzi
May 20, 2011, 12:33:17 PM5/20/11
to tcomp-fich-unl
> Sr Profesor, el ejercicio 21 de la 4.5, te pide la cantidad de formas de
> distribuir 6 bolas INDISTINGUIBLES en 9 cajas distinguibles. El teorema 4 es
> para objetos distinguibles, quice probar haciendo q las 6 bolas sean de un
> tipo--->9!/6! Pero el resultado es dif. Rosen en el solucionario
> usa el Teorema 2, por que?
>
> Damián E. Schlimovich
> Vice - Director de Relaciones Públicas 2010-2011
>
> Rotaract Club de Paraná (4940)
>
> "fortalecer comunidades, unir continentes"
>
> Visitá nuestra web: www.rotaractparana.org.ar
El teorema cuatro dice algo totalmente distinto. Para usar el teorema
> distribuir 6 bolas INDISTINGUIBLES en 9 cajas distinguibles. El teorema 4 es
> para objetos distinguibles, quice probar haciendo q las 6 bolas sean de un
> tipo--->9!/6! Pero el resultado es dif. Rosen en el solucionario
> usa el Teorema 2, por que?
>
> Damián E. Schlimovich
> Vice - Director de Relaciones Públicas 2010-2011
>
> Rotaract Club de Paraná (4940)
>
> "fortalecer comunidades, unir continentes"
>
> Visitá nuestra web: www.rotaractparana.org.ar
cuatro tenes que tener elementos distinguibles y saber cuantos
elementos queres poner en cada caja.
Reply all
Reply to author
Forward
0 new messages