Propuestos Publimetro

[Th3_K4T]

Juan se juntó con sus amigos en un restaurant ® y ahora volverá a su casa ©. Antes debe pasar por la farmacia (F) ¿Por cuántos caminos puede lograr su objetivo, si sólo puede desplazarse hacia la derecha y abajo?

 

doble :banana:

¿De cuántas maneras se puede llegar de R a C sin tener la necesidad de pasar por la farmacia y respetando las reglas de desplazamiento anteriores?

 

 

Bueno, primero hay que ver de cuántas maneras se puede llegar a F siguiendo las reglas, supongamos que nos da A maneras. Luego calculamos de cuántas maneras se puede llegar de F a C, que serían B maneras, entonces el resultado de los caminos posibles sería A*B

 

Como no puede ir para arriba o para la izquierda, notamos de inmediato que la única manera de llegar de R a F es en 4 movimientos. También es importante señalar que sólo puede ir hacia abajo 2 veces y hacia la derecha 2 veces, en distinto orden.

 

Llamemos a los movimientos de la siguiente forma entonces:

 

A1, A2, D1 y D2

 

Podríamos decir entonces que la cantidad de movimientos totales quedaría expresado como 4! = 24, sin embargo, esto tiene un error, ya que por ejemplo, la ruta A1 A2 D1 D2 es equivalente a A2 A1 D2 D1. En realidad corresponde a una combinatoria de la forma 4 sobre 2, es decir, tengo un universo de 4 posibles movimientos, y sólo debo tomar 2, eso queda:

 

4 C 2 = 4!/ (2! * 2!) = 6

 

 

Es decir existen 6 caminos de R a F.

 

Ahora analicemos el camino de F a C, que debe ser 3 veces a la derecha y dos veces abajo, en el fondo, la cantidad de veces que 3 variables se pueden acomodar en 5 espacios, o lo que es igual, la cantidad que dos variables se pueden acomodar en 5 espacios (matemáticamente da la misma cantidad de combinaciones):

 

5 C 3 = 5!/(2!*3!) = 10

 

Por lo que si no me equivoco, la cantidad de caminos es 60.

 

Ahora para sacar las rutas totales de R a C, son 5 movimientos a la derecha y 4 hacia abajo, eso da un total de nueve movimientos, por lo cual la cantidad total de movimientos es:

 

9 C 5 = 126

 

Y como las rutas que pasan por F son 60, entonces las que no pasan por F son 126 - 60 = 66

Edited December 2, 2011 by Th3_K4T

[PsicoStitch]

Prop 7:

 

De ahora en adelante voy a ver el problema en un grafo, donde cada persona es un vértice y conocer a una persona representa adyacencia.

 

La primera condición nos dice que tenemos un grafo G 3-regular y la tercera nos dice que es conexo. Además, como el grado mínimo de G es mayor que 1, existe un ciclo C. Sea C un ciclo maximal en G y v en C. Como G es 3-regular, entonces tiene un vecino w aparte de sus dos vecinos del ciclo. Si suponemos que w no pertenece al ciclo, como la segunda condición nos dice que no hay triángulos, entonces w no puede ser adyacente a uno de los vecinos de v en el ciclo. Por la tercera condición, tendremos que todo vecino de w debe ser adyacente a un vecino de v en el ciclo, lo que contradice la maximalidad de C. Luego w pertenece al ciclo (el argumento anterior también nos dice que no hay vértices fuera del ciclo). Además, la distancia sobre el ciclo entre v y w no puede ser 2, pues se forma un triángulo; no puede ser 3 pues se viola la segunda restricción y no puede ser mayor a 5 pues se viola la tercera restricción.

 

Lo anterior implica que el ciclo C es de largo 8 (implica también que no puede tener otra cardinalidad y explicita las adyacencias salvo isomorfismo).

 

Después de toda esa masturbación, la respuesta es 8.

[killers_666]

Edite mi post para que se viera la fórmula y si tiene que ver la función parte entera para utilizarla, y la fuente que puse es la demostración de la fórmula utilizada ya que no es muy conocida.

 

Saludos

[Profesorx]

Excelente idea wn!

 

Yo quería intentar el último, pero tengo la duda sobre la relación de conocer. Puede ser que Juan conozca a Pedro, pero que Pedro no conozca a Juan? Osea la duda es si la relación es simétrica o no.

En la vida real en general es simétrica, pero aquí tengo la duda porque se habla de conocerse/desconocerse mutuamente.

 

Debería ser simétrica....

 

Juan se juntó con sus amigos en un restaurant ® y ahora volverá a su casa ©. Antes debe pasar por la farmacia (F) ¿Por cuántos caminos puede lograr su objetivo, si sólo puede desplazarse hacia la derecha y abajo?

 

doble :banana:

¿De cuántas maneras se puede llegar de R a C sin tener la necesidad de pasar por la farmacia y respetando las reglas de desplazamiento anteriores?

 

 

Bueno, primero hay que ver de cuántas maneras se puede llegar a F siguiendo las reglas, supongamos que nos da A maneras. Luego calculamos de cuántas maneras se puede llegar de F a C, que serían B maneras, entonces el resultado de los caminos posibles sería A*B

 

Como no puede ir para arriba o para la izquierda, notamos de inmediato que la única manera de llegar de R a F es en 4 movimientos. También es importante señalar que sólo puede ir hacia abajo 2 veces y hacia la derecha 2 veces, en distinto orden.

 

Llamemos a los movimientos de la siguiente forma entonces:

 

A1, A2, D1 y D2

 

Podríamos decir entonces que la cantidad de movimientos totales quedaría expresado como 4! = 24, sin embargo, esto tiene un error, ya que por ejemplo, la ruta A1 A2 D1 D2 es equivalente a A2 A1 D2 D1. En realidad corresponde a una combinatoria de la forma 4 sobre 2, es decir, tengo un universo de 4 posibles movimientos, y sólo debo tomar 2, eso queda:

 

4 C 2 = 4!/ (2! * 2!) = 6

 

 

Es decir existen 6 caminos de R a F.

 

Ahora analicemos el camino de F a C, que debe ser 3 veces a la derecha y dos veces abajo, en el fondo, la cantidad de veces que 3 variables se pueden acomodar en 5 espacios, o lo que es igual, la cantidad que dos variables se pueden acomodar en 5 espacios (matemáticamente da la misma cantidad de combinaciones):

 

5 C 3 = 5!/(2!*3!) = 10

 

Por lo que si no me equivoco, la cantidad de caminos es 60.

 

Ahora para sacar las rutas totales de R a C, son 5 movimientos a la derecha y 4 hacia abajo, eso da un total de nueve movimientos, por lo cual la cantidad total de movimientos es:

 

9 C 5 = 126

 

Y como las rutas que pasan por F son 60, entonces las que no pasan por F son 126 - 60 = 66

 

Perfecto, 2 :banana: para ti

 

 

Prop 7:

 

De ahora en adelante voy a ver el problema en un grafo, donde cada persona es un vértice y conocer a una persona representa adyacencia.

 

La primera condición nos dice que tenemos un grafo G 3-regular y la tercera nos dice que es conexo. Además, como el grado mínimo de G es mayor que 1, existe un ciclo C. Sea C un ciclo maximal en G y v en C. Como G es 3-regular, entonces tiene un vecino w aparte de sus dos vecinos del ciclo. Si suponemos que w no pertenece al ciclo, como la segunda condición nos dice que no hay triángulos, entonces w no puede ser adyacente a uno de los vecinos de v en el ciclo. Por la tercera condición, tendremos que todo vecino de w debe ser adyacente a un vecino de v en el ciclo, lo que contradice la maximalidad de C. Luego w pertenece al ciclo (el argumento anterior también nos dice que no hay vértices fuera del ciclo). Además, la distancia sobre el ciclo entre v y w no puede ser 2, pues se forma un triángulo; no puede ser 3 pues se viola la segunda restricción y no puede ser mayor a 5 pues se viola la tercera restricción.

 

Lo anterior implica que el ciclo C es de largo 8 (implica también que no puede tener otra cardinalidad y explicita las adyacencias salvo isomorfismo).

 

Después de toda esa masturbación, la respuesta es 8.

 

 

De todo lo que escribiste, lo único que entendí fue masturbación :ROLF:

 

Si alguien lo puede verificar o refutar

 

 

Edite mi post para que se viera la fórmula y si tiene que ver la función parte entera para utilizarla, y la fuente que puse es la demostración de la fórmula utilizada ya que no es muy conocida.

 

Saludos

 

Asumiendo que X es el número de pisos, o sea 5, la fórmula no te da.

 

E | (x-1)*(x+1)*(2x-1) / 8 | sería

E | 4 · 6 · 9 / 8 | = 27

 

pero tu dijiste 48

 

 

Actualizo con el de hoy:

 

 

Propuesto 8

 

 

Un coreógrafo ha planeado un complicado esquema de baile, en el que en cada paso 12 bailarines intercambian posiciones (las que están numeradas del 1 al 12) de acuerdo a la regla de la gráfica de arriba.

Así, por ejemplo, si las posiciones están originalmente ocupadas en orden por los bailarines A, B, C, D, E, F, G, H, I, J, K, L, entonces después de un paso el orden sería D, L, I, H, J, A, C, F, B, K, E, G.

¿Cuántas veces -como mínimo- debe repetirse este paso de baile para que los 12 bailarines vuelvan a ocupar sus posiciones originales?

 

 

Edited December 2, 2011 by Profesorx

[PsicoStitch]

Autoverifico que mi hueá está mala. El grafo de Petersen apaña (n=10).

[kreat666]

 

Propuesto 8

 

 

Un coreógrafo ha planeado un complicado esquema de baile, en el que en cada paso 12 bailarines intercambian posiciones (las que están numeradas del 1 al 12) de acuerdo a la regla de la gráfica de arriba.

Así, por ejemplo, si las posiciones están originalmente ocupadas en orden por los bailarines A, B, C, D, E, F, G, H, I, J, K, L, entonces después de un paso el orden sería D, L, I, H, J, A, C, F, B, K, E, G.

¿Cuántas veces -como mínimo- debe repetirse este paso de baile para que los 12 bailarines vuelvan a ocupar sus posiciones originales?

 

 

La permutación se puede descomponer en ciclos disjuntos como

(A D H F)(B L G C I)(E J K)

 

luego el orden de la permutación es mcm(4,5,3)=60.

 

Por lo tanto el paso de baile debe repetirse al menos 60 veces para que los bailarines vuelvan a su posición original.

 

 

 

Para entender esta cuestión en poco tiempo alguien puede leer esto

http://www.uam.es/personal_pdi/ciencias/gallardo/capitulo3b.pdf

[kreat666]

Propuesto 3

 

Me dio 48: Trataré de escribir el desarrollo pronto.

Edited December 3, 2011 by kreat666

[Th3_K4T]

Tengo una sugerencia, la respuesta podrías ponerla en un spoiler en la primera página luego del propuesto.

[killers_666]

Tuve que editar nuevamente la fórmula xq me equivoque y puse una nada que ver.

 

saludos

[Th3_K4T]

Autoverifico que mi hueá está mala. El grafo de Petersen apaña (n=10).

 

Agrego más info, este es un dibujo del grafo de petersen:

 

 

Artículo en Wikipedia:

 

http://es.wikipedia....afo_de_Petersen

 

 

Como ven, cumple con todas las condiciones, en ese caso, el número de nodos, o personas, es 10. El tema es si se puede aceptar esto como una demostración matemática, yo no lo creo. El problema debería quedar abierto, aunque claro, ya conocemos la respuesta.

Edited December 4, 2011 by Th3_K4T