[Ainor]

Amigos aquí les tengo otro problemita...denme sus opiniones.
Un edificio tiene sus pisos enumerados del 0 al 25. El ascensor del edificio tiene sólo dos botones, uno amarillo y uno verde. Al apretar el botón amarillo, asciende 7 pisos, y al apretar el botón verde, desciende 9 pisos. Si se aprieta el botón amarillo cuando no hay suficientes pisos por encima, el ascensor se rompe, y lo mismo ocurre cuando se aprieta el botón verde y no hay suficientes pisos por debajo. ¿Cuántas secuencias diferentes de botones existen tal que le permita a una persona subir del piso 0 al 11 utilizando el ascensor sin romperse?

[teeteto]

Puedes ir pensando "hacia atrás". Por ejemplo: para llegar al 11 puedo hacerlo sólo desde el 20 o desde el 4. Pero para llegar al 20 o al 4 sólo lo puedo haber hecho desde el 13. Al 13 se puede llegar desde el 22 o desde el 6, etc...

También puedes hacerte un árbol como el que te adjunto.

[elcristo]

¿Los problemas de este tipo solo se pueden sacar de forma lógica o hay alguna otra forma de hacerlo? Es decir, utilizando algún tipo de estructura matemática, algoritmos o cosas así.

Simple curiosidad

[Luis Fuentes]

Hola

¿Los problemas de este tipo solo se pueden sacar de forma lógica o hay alguna otra forma de hacerlo? Es decir, utilizando algún tipo de estructura matemática, algoritmos o cosas así.

Es que resolver un problema usando la lógica es resolverlo mediante matemáticas.

Si quieres encuadrar este problema en un campo concreto de las matemáticas, sería un problema de matemática discreta.

Saludos.

[Abdulai]

¿Los problemas de este tipo solo se pueden sacar de forma lógica o hay alguna otra forma de hacerlo? Es decir, utilizando algún tipo de estructura matemática, algoritmos o cosas así.

Simple curiosidad

Una manera es con matrices, el inconveniente es que debido al tamaño de las matrices no son ejercicios para hacer a mano.

Construimos la matriz de la siguiente manera:  Cada fila se corresponde a un piso y habrá un 1 en los pisos que se pueda acceder y 0 en los que no.

Las filas de las potencias de esa matriz corresponderán con los pisos a los que se puede acceder en n etapas y su valor la cantidad de caminos distintos.



Como se trata de una matriz de 26x26 elementos, la vamos a generar y manipular con Matlab.

Código: [Seleccionar]

M=zeros(26);
for k=1:26
    if k+7 < 27 ; M(k,k+7)=1 ; end
    if k-9 > 0  ; M(k,k-9)=1 ; end
end

A partir de ahí se pueden ir calculando las sucesivas potencias o, si se prefiere, una rutina en Matlab que vaya calculando las potencia y las liste, o algo mas elaborado.

Lo que a mi me dió fué que después de 13 pulsaciones válidas cualesquiera se termina siempre en el piso 11 (de 48 maneras diferentes)

Pero si por distraídos nos pasamos no hay problema, pulsamos 16 veces más y estaremos de vuelta en el piso 11 (de 384 maneras diferentes)

[Ainor]

¿Los problemas de este tipo solo se pueden sacar de forma lógica o hay alguna otra forma de hacerlo? Es decir, utilizando algún tipo de estructura matemática, algoritmos o cosas así.

Simple curiosidad

Una manera es con matrices, el inconveniente es que debido al tamaño de las matrices no son ejercicios para hacer a mano.

Construimos la matriz de la siguiente manera:  Cada fila se corresponde a un piso y habrá un 1 en los pisos que se pueda acceder y 0 en los que no.

Las filas de las potencias de esa matriz corresponderán con los pisos a los que se puede acceder en n etapas y su valor la cantidad de caminos distintos.



Como se trata de una matriz de 26x26 elementos, la vamos a generar y manipular con Matlab.

Código: [Seleccionar]

M=zeros(26);
for k=1:26
    if k+7 < 27 ; M(k,k+7)=1 ; end
    if k-9 > 0  ; M(k,k-9)=1 ; end
end

A partir de ahí se pueden ir calculando las sucesivas potencias o, si se prefiere, una rutina en Matlab que vaya calculando las potencia y las liste, o algo mas elaborado.

Lo que a mi me dió fué que después de 13 pulsaciones válidas cualesquiera se termina siempre en el piso 11 (de 48 maneras diferentes)

Pero si por distraídos nos pasamos no hay problema, pulsamos 16 veces más y estaremos de vuelta en el piso 11 (de 384 maneras diferentes)

Amigo a que te refieres cuando dices las filas de las potencias, y bueno de esta pregunta también se deriva preguntarte cuales son las sucesivas potencias que calculas?

[Abdulai]

Me refiero a las potencias de la matriz de transiciones.  Como tiene 676 elementos (26x26), copio y pego lo que me devuelve la rutina en Matlab

Código: [Seleccionar]

T=[0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0
   0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0
   0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0
   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0
   1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0
   0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0
   0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0
   0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0
   0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0
   0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0
   0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0
   0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0
   0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0
   0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1
   0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0
   0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0
   0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0
   0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0
   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0
   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0];

Cada elemento de índice i,j  representa la transición del piso i al j. Si es 1 se puede ir al pulsar, si es 0 no.

La matriz  \( T^2 \)  representará los pisos a los que se puede alcanzar con dos pulsaciones, \( T^3 \) con 3 pulsaciones etc.

Como en este problema se trata de encontrar los destinos partiendo de la planta baja (1er fila), al evaluar \( T^n \) solo hay que fijarse en la 1er fila, ya que serán los destinos partiendo de planta baja.

Con esta rutina Quick&Dirty en Matlab obtengo un listado de la 1er fila hasta las 32 pulsaciones:

Código: [Seleccionar]

Q=M;Q(1,:) % Lista solo la primer fila
for k=2:32
    Q=M*Q;Q(1,:)
end

No pego el listado porque es kilométrico.

--------------------------------------------------

Debido a que después de un número determinado de pulsaciones solo se puede llegar a uno o dos pisos el problema puede simplificarse mucho, haciendo que el tratamiento con matrices sea matar moscas a cañonazos.

Pero si las posibilidades al pulsar fueran mayores, como ser que se puedan acceder a mas pisos o la cantidad de pisos a subir o bajar fuera diferente según donde se esté, otros métodos serían inmanejables debido a la gran cantidad de posibilidades y las matrices serían una buena elección.

Pero bueno... vos preguntaste por otros métodos

[elcristo]

Pues sí, es matar una mosca a cañonazos, pero bueno, esta era la curiosidad que tenía, por si aparecen problemas muchos más complejos saber que existen métodos para hacerlos que no sea con el cuento de la vieja.

[Luis Fuentes]

Hola

 Un pequeño cálculo que puede hacerse previamente y que, aunque no da directamente la solución, si ayuda a simplificar el problema es calcular primero cuantas veces hay que subir y cuantas que bajar para ir del \( 0 \) al \( 11 \).

 Equivalentemente se trata de hallar las soluciones no negativas de:

\(  7s-9b=11 \)

 Por la teoría general de ecuaciones diofánticas lineales puede verse que las soluciones no negativas son de la forma:

 \( (s,b)=(8,5)+k(9,7) \) con \( k \) entero no negativo

 Si excluimos soluciones donde pasemos dos veces por el mismo piso y dado que sólo hay \( 26 \) pisos tiene que cumplirse que \( s+b<26 \) y de ahí \( k=0 \).

 Es decir necesariamente se subirá \( 8 \) veces y se bajará \( 5 \).

Saludos.