Autor Tema: Problema de combinatoria

0 Usuarios y 1 Visitante están viendo este tema.

24 Noviembre, 2019, 12:29 pm
Leído 884 veces

Zionira

  • Nuevo Usuario
  • Mensajes: 15
  • Karma: +0/-0
  • Sexo: Femenino
Hola!! Buenos días!! Tengo una duda con el problema siguiente:
¿De cuántas maneras diferentes se pueden colocar los números 1,2,4,5,6,8,9,10,12 y 15 en una fila de tal modo que cualquier número aparezca antes que su doble?
En un principio intenté resolverlo por partes partiendo de que si o si los números 1,2,4 y 8 deben estar en ese orden e intentando meter el resto en medio con números combinatorios. Pero se me ha hecho muy extraño y me gustaría saber otras formas de hacerlo porque dudo mucho que esté bien. Muchas gracias de antemano!!!

24 Noviembre, 2019, 02:32 pm
Respuesta #1

Bobby Fischer

  • Aprendiz
  • Mensajes: 477
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
    • chess.com
Hola,

La solución es \( 37800 \) maneras. Una forma es: ver todas las posibles permutaciones y eliminar aquellos casos que no cumplan alguna de las condiciones. Los casos que pasan el filtro son aquellos que las cumplen todas. Por supuesto, con ordenador.

En cada una de las permutaciones, calculo las posiciones que ocupan los elementos del conjunto y luego las comparo entre ellas. Los números de  \( \{1,2,4,8\} \), \( \{5,10\} \), \( \{6,12\} \), \( \{9\} \) y \( \{15\} \) están relacionados con los otros de su propio conjunto pero no con los de los demás. Las condiciones que hay que imponer son que la posición del 1 sea menor que la del 2, que la del 2 sea menor que la del 4, que la del 4 sea menor que la del 8, que la del 5 sea menor que la del 10 y que la del 6 sea menor que la del 12. Si las cumplen todas, eso significa que todo número de la permutación aparece antes que su doble. Dicha permutación pasa el filtro.

Se pueden ordenar las instrucciones del código para hacerlo más eficiente sin entrar en obstáculos. Adicionalmente, medí el tiempo de evaluación.

Código: [Seleccionar]
function []=bobby_51() % MatLab
tic
v=[1,2,4,5,6,8,9,10,12,15];
P=perms(v);
[m,~]=size(P);
k=0;
for j=1:m
    [pos1]=position(1,P(j,:));
    [pos2]=position(2,P(j,:));
    [pos4]=position(4,P(j,:));
    [pos8]=position(8,P(j,:));
   
    if pos1<pos2
        continue
    elseif pos2<pos4
        continue
    elseif pos4<pos8
        continue
    end
   
    [pos5]=position(5,P(j,:));
    [pos10]=position(10,P(j,:));
   
    if pos5<pos10
        continue
    end
   
    [pos6]=position(6,P(j,:));
    [pos12]=position(12,P(j,:));
   
    if pos6<pos12
        continue
    end
    k=k+1;
end
disp(k)
toc
    function[pos]=position(number,v)
        for i=1:length(v)
            if v(i)==number
                pos=i;
                break
            end
        end
    end

end

Código: [Seleccionar]
>> bobby_51
       37800
Elapsed time is 10.804050 seconds.
>>

Saludos.

24 Noviembre, 2019, 03:20 pm
Respuesta #2

Zionira

  • Nuevo Usuario
  • Mensajes: 15
  • Karma: +0/-0
  • Sexo: Femenino
Hola de nuevo!! Muchas gracias por tu respuesta!! Pero lastimosamente aunque ahora con un programa se podría llegar a la respuesta como tú lo hiciste, yo buscaba una respuesta teórica, aplicando matemáticas teóricas y no programación de cara a mis exámenes. Por otra parte, me has ayudado a despejar dudas con respecto a los cinco conjuntos que has señalado, muchas gracias!!!!
Saludos!! E infinitas gracias de nuevo!! :aplauso:

24 Noviembre, 2019, 03:27 pm
Respuesta #3

Abdulai

  • Moderador Global
  • Mensajes: 2,366
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino

Son 10 números, por lo tanto son \( 10! \) permutaciones.

Pero eso contiene las permutaciones de \( \{1,2,4,8\}=4! \) , las de \( \{5,10\}=2! \) y las de \( \{6,12\}=2! \)  de las cuales solo una es válida respectivamente.

Por lo tanto son  \( \dfrac{10!}{4!2!2!}= 37800 \)  maneras diferentes.

24 Noviembre, 2019, 06:07 pm
Respuesta #4

Zionira

  • Nuevo Usuario
  • Mensajes: 15
  • Karma: +0/-0
  • Sexo: Femenino
Vale!! Ahora lo entiendo mejor!! Gracias !!!!

24 Noviembre, 2019, 08:27 pm
Respuesta #5

feriva

  • Matemático
  • Mensajes: 9,078
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.


Hola.

Hola!! Buenos días!! Tengo una duda con el problema siguiente:
¿De cuántas maneras diferentes se pueden colocar los números 1,2,4,5,6,8,9,10,12 y 15 en una fila de tal modo que cualquier número aparezca antes que su doble?

Estás interpretando que estén “inmediatamente antes”; supongo que en clase habrán aclarado eso, porque, si no, por lo que dice el enunciado literalmente, el problema podría ser otro; y serían muchas más permutaciones.

Saludos.

24 Noviembre, 2019, 09:16 pm
Respuesta #6

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,066
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Estás interpretando que estén “inmediatamente antes”; supongo que en clase habrán aclarado eso, porque, si no, por lo que dice el enunciado literalmente, el problema podría ser otro; y serían muchas más permutaciones. 

No se si entiendo lo que quieres decir, feriva. Pero nadie en este hilo ha interpretado que estén "inmediatamente antes".

Las permutaciones calculadas, bien empíricamente por Bobby Fischer o bien algebraicamente por Abdulai, son bajo el supuesto (razonable) de que cada número aparezca antes que su doble, pero no necesariamente inmediatamente antes.

Saludos.

24 Noviembre, 2019, 09:42 pm
Respuesta #7

feriva

  • Matemático
  • Mensajes: 9,078
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.
Hola

Estás interpretando que estén “inmediatamente antes”; supongo que en clase habrán aclarado eso, porque, si no, por lo que dice el enunciado literalmente, el problema podría ser otro; y serían muchas más permutaciones. 

No se si entiendo lo que quieres decir, feriva. Pero nadie en este hilo ha interpretado que estén "inmediatamente antes".

Saludos.

Hola, Luis. No, he si yo, que al decir Zionira "En un principio intenté resolverlo por partes partiendo de que si o si los números 1,2,4 y 8 deben estar en ese orden" entendí que estaba diciendo "juntos"; pero no, después habla de meter números por medio.

Muchas gracias.

Saludos.

25 Noviembre, 2019, 09:14 am
Respuesta #8

Zionira

  • Nuevo Usuario
  • Mensajes: 15
  • Karma: +0/-0
  • Sexo: Femenino
Exacto, siento mucho si no me expresé bien. El ejercicio no especificaba que estuvieran inmediatamente después, aunque en ese supuesto se simplifica un poco conceptualmente no? Es decir, en ese caso tendrías cinco bloques y tendrías que permutarlos por lo que las posibilidades serían 5!
Corríjanme si me equivoco y muchas gracias a todos!!

Saludos.

25 Noviembre, 2019, 09:27 am
Respuesta #9

feriva

  • Matemático
  • Mensajes: 9,078
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.
Hola.

Hola!! Buenos días!! Tengo una duda con el problema siguiente:
¿De cuántas maneras diferentes se pueden colocar los números 1,2,4,5,6,8,9,10,12 y 15 en una fila de tal modo que cualquier número aparezca antes que su doble?
En un principio intenté resolverlo por partes partiendo de que si o si los números 1,2,4 y 8 deben estar en ese orden e intentando meter el resto en medio con números combinatorios. Pero se me ha hecho muy extraño y me gustaría saber otras formas de hacerlo porque dudo mucho que esté bien. Muchas gracias de antemano!!!

Sí, perdona, que anoche pensé que podría haber esa ambigüedad y no me atreví a decir nada, pero pensaba explicarte mi manera de pensarlo:



Yo esto lo suelo pensar así, con números que se colocan en unas plazas.

Tienes 10 posiciones para colocar los números de izquierda a derecha: - - - - - - - - - -

Si tuvieras dos posiciones nada más y una sola pareja, sólo podrías colocarlos de una manera, ya que uno siempre tiene que estar a la izquierda y otro a la derecha; es decir, serían la mitad de las permutaciones \( \dfrac{2!}{2}
  \). Por las mismas, si tuvieras tres posiciones y una pareja, sería la mitad de las variaciones de 2 agrupadas de tres en tres, \( \dfrac{3!}{2}
  \) (lo puedes hacer a mano buscándolas; en este caso quedaría una casilla vacía para un número suelto cualquiera).

EDITADO

En tu problema, hay algunas parejeas que comparten números y otras independientes, que son 5,10 y 6,12

Para 5,10 tienes \( (V_{10,2})/2=45
  \); para la otra quedan dos lugares menos, ocho, (ya están colocados el 5 y el 10 en todas sus posiciones) entonces son \( (V_{8,2})/2=28
  \)

...

Ahora quedan las formadas por 1,2,4,8, que son tres parejas, pero no son independientes

Si tomamos la pareja formada con los dos del centro, 2,4, quedan seis posiciones y tenemos : \( (V_{6,2})/2=15
  \).

Cada una de éstas forman dos variaciones con los otros dos números, 1 y 8, ya que, el 1 quede siempre a la izquierda del 2 y el 4 a la izquierda del 8; las multiplica por 2.

\( 45\cdot28\cdot15\cdot2=37800
  \).

Yo creo que así se ve bastante bien; si acaso, ponte un ejemplo con menos parejas, que tú puedas hacerlo colocando de verdad las cosas y contándolas por la cuenta de la vieja, así se todo mucho mejor.


Saludos.

25 Noviembre, 2019, 10:19 am
Respuesta #10

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,066
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Exacto, siento mucho si no me expresé bien. El ejercicio no especificaba que estuvieran inmediatamente después, aunque en ese supuesto se simplifica un poco conceptualmente no? Es decir, en ese caso tendrías cinco bloques y tendrías que permutarlos por lo que las posibilidades serían 5!
Corríjanme si me equivoco y muchas gracias a todos!!

Correcto. Si fuese así, serían las formas de ordenar los cinco bloques: \( 5! \).

Saludos.

25 Noviembre, 2019, 07:47 pm
Respuesta #11

Zionira

  • Nuevo Usuario
  • Mensajes: 15
  • Karma: +0/-0
  • Sexo: Femenino

Ahora quedan las formadas por 1,2,4,8, que son tres parejas, pero no son independientes

Si tomamos la pareja formada con los dos del centro, 2,4, quedan seis posiciones y tenemos : \( (V_{6,2})/2=15
  \).

Cada una de éstas forman dos variaciones con los otros dos números, 1 y 8, ya que, el 1 quede siempre a la izquierda del 2 y el 4 a la izquierda del 8; las multiplica por 2.

\( 45\cdot28\cdot15\cdot2=37800
  \).


Vale, muchas gracias. Pero no me ha quedado muy claro el último paso. Es decir, entiendo que tras escoger el sitio de las tres primeras parejas, es decir seis lugares, te quedan cuatro para colocar 15,9 1 y 8 pero no entiendo porque esto lo arreglas multiplicando por dos.

Saludos!

25 Noviembre, 2019, 08:03 pm
Respuesta #12

feriva

  • Matemático
  • Mensajes: 9,078
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.

Ahora quedan las formadas por 1,2,4,8, que son tres parejas, pero no son independientes

Si tomamos la pareja formada con los dos del centro, 2,4, quedan seis posiciones y tenemos : \( (V_{6,2})/2=15
  \).

Cada una de éstas forman dos variaciones con los otros dos números, 1 y 8, ya que, el 1 quede siempre a la izquierda del 2 y el 4 a la izquierda del 8; las multiplica por 2.

\( 45\cdot28\cdot15\cdot2=37800
  \).


Vale, muchas gracias. Pero no me ha quedado muy claro el último paso. Es decir, entiendo que tras escoger el sitio de las tres primeras parejas, es decir seis lugares, te quedan cuatro para colocar 15,9 1 y 8 pero no entiendo porque esto lo arreglas multiplicando por dos.

Saludos!


Cuando tomas la pareja 2,4, la tienes distribuida de distinta manera pero siempre así 2...4...

y los demás entre medias.

Ahora quedan cuatro lugares. Como el 1 tiene que preceder al 2 y el 4 al 8, tendrán que ir así

1...2...4...8  (uno)

Spoiler
o así

4...8...1...2  (y dos)


Y los otros números que no forman parejas no importan, son los huecos.
[cerrar]

No perdona, sólo van así, 1...2...4...8, que veo que, si no, me salen más ahora, qué estaba diciendo yo. Claro, no respetaban la condición en lo del spoiler, no era así.

Lo que ocurre es mucho más simple, como quedan dos huecos, en ellos pueden ir 9,15 ó 15,9, estas dos posibilidades y, por el principio multiplicativo, pues el doble de todas las que hay. Multiplicas por 2.

Es por lo que tú decías al principio precisamente, esos tienen que ir fijos en orden.

Para estar segura, toma cualquier disposición; tenemos colocados ya los números 1,2,4,5,6,8,10,12 de todas las maneras posibles; toma una ordenación cualquiera, por ejemplo

1,6,12,_,2,5,10,_4,8

Todas son así, con dos huecos y esos números de puestos de una manera y otra; pues de cada una sólo puedes hacer dos con el 9 y el 15

1,6,12,9,2,5,10,15,4,8

1,6,12,15,2,5,10,9,4,8



Saludos.


25 Noviembre, 2019, 08:20 pm
Respuesta #13

noisok

  • Junior
  • Mensajes: 73
  • Karma: +0/-0
  • Sexo: Masculino
A ver si lo entiendes mejor intentando razonar la fórmula de una permutación con repetición. Esa fórmula se aplica cuando alguno u alguno de los elementos se repiten. En realidad es una permutación normal, solo que hay que eliminar ciertos casos por la repetición de los elementos.
Lo razonare con ejemplo sencillo: Si tenemos 3 cifras: 1,2,3. El numero de numeros que podemos formar es 3!=6. Estos son: 123, 132, 213, 231, 312, 321. Ahora pongamos que las cifras son 1,1,3. El numero de numeros seran los mismos que los anteriormente dados pero donde tenemos un dos debemos poner un 1, pues la cifra en donde antes habia un dos ahora tenemos un uno, dando: 113, 131, 113, 131, 311, 311. Vemos que se repiten y son en realidad solo 3. Que es lo mismo que considerar la permutación normal dividido por el factorial del elemento que se repite 2!.  Se puede generalizar...
En el problema planteado, no se repiten los elementos, sin embargo te dicen que ciertos elementos deben estar en orden fijo, por ejemplo 5,10. No importa lo que se intercale entre estos números. Pero el orden de esos dos es invariante. Por tanto fijate que estas dos cifras esta en todas posibilidades y que las permutaciones de esos dos números son 2!, y por tanto el orden en que estaran es o 5,10 o 10,5. Por eso dividimos las permutaciones normales por el 2!. De esas dos posibilidades solo nos interesa la 5,10. Que es lo mismo que si me dicen que hay dos cincos o dos dieces. Una vez apliques la reducción anterior podemos hacerla para otro bloque, como  el bloque 1,2,4,8, y se aplica el mismo razonamiento. Estas 4 cifras están en todas las permutaciones, en varios grupos donde cada grupo representa una de las posibles permutaciones del total de posibles que  son 4!, pero el orden no importa, por lo que  solo nos interesa uno de esos grupos y por eso lo dividimos por 4!, y es lo mismo que si me dicen que las cuatro cifras están repetidas por igual. Por tanto, nota que es lo mismo que pasa cuando repites un elemento. Y así sucesivamente..
Se que igual no lo he explicado del todo bien, pero espero que pilles la idea. Esta idea intenta explicar la fórmula de Abdulai, que me parece la más sencilla de aplicar y entender y en el fondo se justifica con la de una formula de permutación con repetición.

26 Noviembre, 2019, 08:53 pm
Respuesta #14

Zionira

  • Nuevo Usuario
  • Mensajes: 15
  • Karma: +0/-0
  • Sexo: Femenino
Entendido, gracias!! :aplauso: