[Zionira]

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!!!

[Ricardo Boza]

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.

[Zionira]

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!!

[Abdulai]

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.

[Zionira]

Vale!! Ahora lo entiendo mejor!! Gracias !!!!

[feriva]

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.

[Luis Fuentes]

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.

[feriva]

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.

[Zionira]

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.

[feriva]

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.