Dinámica Porteña Jr.

Quedan todos invitados este jueves a la segunda sesión del seminario “Dinámica Porteña Jr.” a llevarse a cabo en el Instituto de Matemáticas (IMA) de la PUCV, esta vez la charla queda a cargo de Fabián Contreras.  (Dinámica Porteña)

05-05-16 Fabian Contreras

Anuncios
Categorías: Sin categoría | Deja un comentario

¿Y cuál es el truco?

A continuación detallamos una secuencia de pasos a seguir:

  1. Elegir un número de 3 o más dígitos (los dígitos permitidos son 1, 2, 3, …, 9);
  2. Escoger uno de los dígitos del número elegido y forme un nuevo número con los dígitos restantes (en el mismo órden, pero sin el dígito escogido);
  3. Restamos el nuevo número con la suma de todos los dígitos (incluyendo el elegido);
  4. Sumamos los dígitos del resultado de la resta hecha en el paso anterior;

Con este último dato, ¿será posible “adivinar” el dígito escogido?, ¿de qué modo?.

Solución: Considere un número a_{n-1}a_{n-2}\ldots a_{0} con n dígitos (n\geq3). Supongamos que escogemos el dígito a_m (con 0\leq m\leq n-1), entonces
a_{n-1}\ldots a_{m-1}a_{m+1}\ldots a_{0} - \sum\limits_{i=0}^{n-1}a_i = a_{n-1}10^{n-1} + \ldots+ a_{m-1}10^{m-1}+a_{m+1}10^{m+1}+\ldots+a_0- \sum\limits_{i=0}^{n-1}a_i = [9]_{n-1}a_{n-1}+\ldots+[9]_{m-1}a_{m-1}+[9]_{m+1}a_{m+1}+\ldots+9a_1 - a_m

donde [9]_k = 9999\ldots9 (k veces). En este paso debemos notar que el valor anterior más un dígito a_m\in\{1,2,\ldots,9\} es divisible por 9, esto nos dice que si sacamos el módulo 9 de la diferencia anterior (resto de la división por 9 del valor), vamos a obtener como resultado -a_m, que es el valor negativo del dígito que buscamos. Para concluir debemos notar lo siguiente: todo número es congruente a la suma de sus dígitos módulo 9 (esto sigue de 10^kx = [9]_kx + x = x \,\;(\text{mod} \;9)).

acertijo chino

Veamos un ejemplo. Considere el número 112348 y supongamos que escogemos el dígito x y que el dato de la suma de los dígitos de la diferencia (explicada en el punto 3) es 16. Como antes, notamos que 16\equiv -2\,\;(\text{mod}\;9), por lo tanto, x=2.

Categorías: Cálculo, Competición | Deja un comentario

Mayor o menor?

¿Qué valor es mayor, 1000^{1000} o 1001^{999}?

Solución: Por un argumento de velocidad de crecimiento (o de divergencia) deberíamos esperar que 1000^{1000} sea mayor. Para mostrar esto, usaremos lo que conocemos como el teorema de Newton:
(a+b)^n = \sum\limits_{k=0}^n \frac{n!}{k!(n-k)!}a^{n-k}b^k
De esta forma, tenemos que
(1000+1)^{999} = \sum\limits_{k=0}^{999} \frac{999!}{k!(999-k)!}1000^{999-k} = 1000^{999} + \frac{999!}{998!}1000^{998}+\ldots+\frac{999!}{998!}1000+1

Conjeturamos lo siguiente:
\frac{999!}{k!(999-k)!} \leq 1000^k
Para probar esto usamos inducción. Notemos que para k=1 la desigualdad anterior es válida, asi que la suponemos cierta para k=m. De este modo,
\frac{999!}{(m+1)!(999-m-1)!} = \frac{999-m}{m+1} \frac{999!}{m!(999-m)!}\leq \frac{999-m}{m+1} 1000^m\leq 1000\cdot 1000^m = 1000^{m+1}
Por lo tanto, la desigualdad vale también para k=m+1 y concluímos con la prueba.

De esta forma,
(1000+1)^{999} = \sum\limits_{k=0}^{999} \frac{999!}{k!(999-k)!}1000^{999-k} \leq \sum\limits_{k=0}^{999} 1000^k \cdot 1000^{999-k} = 1000^{1000}
Esto muestra que 1001^{999}\leq 1000^{1000}.

Categorías: Cálculo, Competición | Deja un comentario

Misión posible o imposible?

Considere la siguiente figura,
macro
La pregunta es: ¿Podemos trazar tal figura sin levantar el lápiz y sin pasar por ninguno de sus segmentos más de una vez?

Seguir leyendo…

Categorías: Grafos | Etiquetas: , , , , | Deja un comentario

La báscula ingeniosa

El siguiente problema me pareció muy entretenido y particularmente ingenioso, veamos de qué se trata:

Supongamos que tenemos N canastas con bombones. No tenemos ni la menor idea de cuántos bombones hay en cada canasta, pero sabemos que todas las canastas tienen bombones de 10 gramos, excepto una de ellas. Existe una de las canastas que solo tiene bombones de 9 gramos. El desafío es encontrar cuál de las canastas es la que tiene los bombones de 9 gramos, sabiendo que podemos retirar bombones de cualquiera de las canastas para pesarlos y sólo podemos usar la báscula (una pesa simple que mide gramos) exactamente una vez.

Seguir leyendo…

Categorías: Cmat, Competición | Deja un comentario

Ecuación engañosa

Hola,

Vamos con un problema sencillo del CMAT, pero que es algo engañoso.

Problema 1:

Determine si la ecuación:

x^5 + 2004x^3+x+1=0

Tiene soluciones enteras

Solución:

Como siempre comencemos con la fase de análisis del problema.

Lo primero que se le viene a la mente a la gran mayoría es comenzar a probar con algunos números a ver si encontramos de suerte la solución. Es claro que con números positivos no hay por donde que la suma de todos esos factores sume 0, así que se podría probar con algún número negativo, por ejemplo: -1.

(-1)^5 + 2004\times(-1)^3+(-1)+1 \neq 0

Podríamos probar con algunos números mas, pero es probable que no lleguemos tan fácilmente al resultado.
Seguir leyendo…

Categorías: Cmat | Deja un comentario

Una versión aleatória del teorema de Ruelle

A continuación, facilito el texto de disertación que definió mi tesis para la obtención del grado académico de “mestre” (master) en la Universidade Federal da Bahia, Brasil. Espero que esto sea un aporte a la difusión de las ciencias y sirva como punto de partida para introducirse en esta subárea de los sistemas dinámicos.

Resumen/Abstract

Presentamos una nueva aplicación del recientemente popularizado método de acoplamientos (o transporte optimal) para obtener decaimiento exponencial de correlaciones. A modo de introducción, enunciamos los teoremas de Perron-Frobenius e de Ruelle-Sarig, como versiones preliminares a nuestro resultado e como objetos de comparación. Nuestro objetivo es probar el teorema de Ruelle en un contexto más general como lo son las cadenas contables topológicas de Markov aleatórias completas,para esto vamos a introducir el método de acoplamientos que hace uso de una contracción de la métrica de Wasserstein sobre las medidas de probabilidad definidas en un espacio de shift-completo aleatório. Vamos a ver que tal método muestra varias ventajas en relación a los clásicos métodos conocidos para probar decamiento de correlaciones.

Disertación: Una versión aleatória del teorema de Ruelle

Categorías: Sistemas Dinámicos | Etiquetas: , , , , , , , , , , | Deja un comentario

Puntos medios enteros

Este problema corresponde a un problema presentado en la segunda fecha del CMAT (Campeonato Interescolar de Matemáticas) para el 4to nivel (4to medio – Ultimo año de secundaria).

Problema: Considere 5 puntos de coordenadas enteras en el plano cartesiano (n1, m1), (n2, m2), (n3, m3), (n4, m4), (n5, m5). Muestre que el punto medio de al menos uno de los segmentos que dichos puntos determinan tiene también coordenadas enteras.

Primero, pueden probar con algunos números para ver si realmente resulta o no. Es importante notar que probar no permite determinar si es verdadera la afirmación o no, solo nos permite divisar si debemos irnos por el camino de probar la afirmación o generar una contradicción para demostrar que es falso. Parece que en este caso la afirmación es verdadera.

Para partir, veamos la definición del punto medio:

Con Punto1 = (X1, Y1) ; Punto2= (X2, Y2) => Punto Medio = ((X1+X2)/2;(Y1+Y2)/2))

Ahora bien, nos están hablando de números enteros. En el cálculo del punto medio, ¿Qué necesito para que la fracción anterior sea entera? Necesito que el numerador (valor de arriba) sea múltiplo de 2.

Esto significa que la suma de los dos valores debe ser múltiplo de 2. ¿Cómo se llaman los números múltiplos de 2? Números pares. Ahora bien, ¿qué necesito para que la suma de dos números sea número par?

  1. Ambos números son pares.
  2. Ambos números son impares.

Es importante notar que hasta el momento solo hemos utilizado palabras claves del enunciado. ¿Necesitamos usar algo del plano cartesiano? ¿Hemos usado que son 5 puntos y no 6? Para nada. Simplemente analizamos el problema en base a los datos más generales que nos entrega y después pasamos a los datos específicos que nos permita resolverlos.

Como queremos que el punto medio esté compuesto por dos números pares, eso significa, que queremos que el punto medio sea definido por sumas de números pares y números impares. Para poder probar esto, pongámonos en el peor caso, si en el peor caso funciona significa que funciona para todos los otros, ¿a qué suena esto? Al palomar por supuesto. Si no conocen al palomar vean post anteriores.

El peor caso es el que tomas un par de puntos y la paridad del valor para X1 es distinta que la de X2 o que la paridad de Y1 sea distinta a la de Y2. Con P1 = (X1,Y1) y P2 = (X2, Y2).

  1. (Par, par) = (Impar, Par); (Par, Impar); (Impar, Impar).
  2. (Impar, Impar) = (Impar, Par); (Par, Impar); (Par, par).
  3. (Impar, par) = (Par, Par); (Impar, Impar); (Par, Impar).
  4. (Par, Impar) = (Par, Par); (Impar, Impar); (Impar, Par).

Si se fijan, si se repite la paridad de X1 y Y1, esto genera que la suma de ambos puntos sea par tanto para X e Y. Por ejemplo:

(Par, Impar) + (Par, Impar) = (Par + Par, Impar + Impar) = (Par, Par).

Y aquí viene lo interesante, ¿cuántas combinaciones distintas tenemos de paridades para un punto?

La primera coordenada (X) puede ser par o impar y la segunda coordenada (Y) puede ser par o impar: 2 * 2 = 4.

Esto significa que tenemos 4 combinaciones distintas de paridad, pero nuestro enunciado nos dice que tenemos 5 puntos de coordenadas enteras.

  • Esto implica, por palomar, que alguno de ellos debe repetirse.
  • Si uno de ellos se repite la suma de ambas coordenadas de los dos puntos para calcular el valor medio será par
  • Si es par, esto implica la división por 2 generará un número entero para ambas coordenadas del punto medio.
  • Y esto cubre el peor caso y se demuestra que al menos uno de los puntos medios tendrá coordenadas enteras, por lo que, se demuestra el enunciado.

Bueno, otra vez nos topamos con palomar, pero es interesante en este caso que si se analizan bien las definiciones entregadas en el enunciado podemos llegar rápidamente a los datos importantes que nos permitan encontrar el camino para la solución del problema.

Pronto se vienen nuevos problemas.

Saludos

Categorías: Cmat | Deja un comentario

El problema de las gallinas – CMAT

En esta ocasión les presentaré un problema que se ve bien entretenido. A diferencia del post anterior, en este no encontré una solución sofistica utilizando algún método bonito. Si ustedes lo encuentran, por favor, no duden en postearlo.

Este problema se me presentó en segundo medio y la verdad que no recuerdo si lo resolví o no:

Problema: En una isla mágica hay 2003 gallinas azules, 1994 gallinas rojas y 1985 gallinas blancas. Las gallinas tienen la siguiente particularidad: si se encuentran dos de distinto color, ambas cambian al tercer color (no existe otro tipo de encuentros). Decida si es posible, luego de algunos cambios, que todas las gallinas queden del mismo color, sea cual sea este color común.

Como dije, no tengo ninguna fórmula mágica para resolverlo, pero si hay algunos aspectos a analizar.

Solución:

  1. Definiré las gallinas Azules como A, gallinas rojas como R y gallinas blancas como B.
  2. La notación AB -> RR. Significa que se transformó una gallina Azul y una gallina Blanca en dos gallinas Rojas. Lo mismo para las otras combinaciones.
  3. Primero podemos ver que entre las gallinas rojas y blancas hay una diferencia de 9 gallinas. Entre rojas y azules, hay una diferencia de 9 gallinas también. Esto es importante.
  4. Cuando tenemos números grandes, es importante ver si podemos prescindir de ellos, esto nos permitirá trabajar de mejor manera y enfocarnos en la solución final.
  5. El objetivo es “decidir si es posible” que todas las gallinas queden del mismo color. Esto significa que basta que mostremos una manera que pase esto (cualquier manera) y hemos resuelto o problema o demostremos que no es posible. Claramente mostrar una manera puede ser mucho más sencillo, pero si no es posible perderíamos el tiempo tratando de encontrar tal manera. Es muy importante esta diferencia entre mostrar y demostrar. Demostrar en general es más difícil porque nos debiésemos poner en todos los casos posibles.
  6. A mi me parece que se puede, así que trataré de ver si se puede.
  7. Según el enunciado si se encuentran dos gallinas de distinto color, se vuelven al tercer color. Ahora sería interesante pensar una forma donde grupos de gallinas con una determinada relación entre ellas, se puedan transformar a un solo color. Considerando esto, podemos notar que: AAAR -> AABB -> ABAB -> RRRR. O sea, si tomamos grupos en la proporción 3:1, podemos transformar todas las gallinas del color en menor cantidad. Puede verse inútil ahora, pero nos podría servir para tratar de armar grupos de este estilo.
  8. Ahora, como vimos en el punto tres hay diferencia de número entre los grupos de gallinas. Si tenemos dos grupos con la misma cantidad de gallinas, podemos transformarlas al tercer grupo completamente. Considerando esto, es una buena idea tomar grupos del mismo tamaño (1985), así si logramos que las gallinas restantes queden de un solo color, bastaría mezclar los dos grupos de los otros colores, ya que, tendrán el mismo tamaño.
  9. O sea, tenemos 1985 gallinas Azules, 1985 gallinas Rojas, 1985 gallinas Blancas y con 18 restantes Azules y 9 Rojas. Según lo anterior podemos dejar de lado los grupos de 1985 gallinas, ya que, si logramos que las restantes sean de un solo color, simplemente juntamos dos de esos grupos en el color al cual transformamos todas.
  10. Como dijimos anteriormente nos deshicimos de los números grandes y el problema se reduce a ver si con 18 gallinas Azules y 9 gallinas Rojas, podemos volverlas todas al mismo color.
  11. Lo que viene a continuación es simplemente fruto de prueba y error. Así que si en realidad no tiene mucho peso, pero si quería mostrar de que a partir de un problema sencillo, podemos hacer conjeturas y elementos de base que permiten simplificarlo a un problema relativamente sencillo.
  12. Ahora, haremos las siguientes transformaciones. Si logramos que dos grupos tengan la misma cantidad de gallinas, ganamos. 18A – 9R – 0B (5 azules y 5 rojas) -> 13A – 4R – 10B (2 Azules y 2 Blancas) -> 11A – 8R – 8B (8 Rojas y 8 Blancas) -> 27 Azules.
  13. Como logramos que las 27 gallinas sueltas quedaban azules, ahora tenemos: 27A – 1985A – 1985R – 1985B, lo único que resta es 1985R – 1985B -> 3970A. Esto significa que las 3997 gallinas quedan Azules.
  14. Como mostramos un caso, esto significa que es posible y la solución es sí.

Bueno, espero intenten resolver el problema y mejor aún si encuentran una solución más “bonita”. Saludos y hasta la próxima.

Categorías: Cmat | 2 comentarios

Principio del Palomar – Ejemplo Campeonato Interescolar Matemáticas

Hola,

Un aspecto interesante de las matemáticas y de los conocimientos en general, es que es difícil olvidarlos por un momento para razonar como si no tuviera algún conocimiento específico.

¿A qué me refiero con olvidarlos? Un ejemplo podría ser con el siguiente problema:

“En la finca del tio de Euclides hay gallinas y perros en total pueden encontrar 148 patas y 60 cabezas ¿cuántos perros y cuantas gallinas hay en la finca ?”

Si le presentas este problema a un estudiante universitario le parecerá obvio utilizar un sistema de ecuaciones, pero ¿qué pasa con un estudiante de 10 años que requiere resolver este problema? Quizás comience a dibujar en la pizarra las gallinas y los perros hasta llegar a una solución. A esto me refiero con olvidar los conocimientos, veo difícil que un estudiante de ingeniería no considere como primera, segunda y tercera opción resolverlo con un sistema de ecuaciones.

¿A qué se debía esta introducción? Es que durante mi participación en el campeonato interescolar de matemáticas chileno en el año 2005:

Problema: “El crucero del amor tiene 206 pasajeros provenientes de cinco países distintos. Se sabe que siempre que se sientan seis pasajeros en una misma mesa al menos dos de ellos tienen la misma edad. Demuestre que entre los 206 pasajeros hay al menos cinco pasajeros que tienen la misma edad, el mismo sexo y la misma nacionalidad”

Este problema lo resolví en 4to medio y ahora intenté resolverlo nuevamente. Recuerdo mi razonamiento al resolver el problema y era: “Me tengo que poner en el peor caso, si me pongo en el peor caso y se cumple, eso significa que se cumpliría en todos el resto de los casos”. Así también recuerdo que tuve que escribir mucho para fundamentar este argumento y me parecía completamente lógico para mi, pero tenía que fundamentarlo.

Lo que a mi me parecía lógico y tenía que explicar, cuando estuve en la universidad aprendí que era algo que existía y se llamaba Principio del Palomar y dice así:

“El principio del palomar, también llamado principio de Dirichlet o principio de las cajas, establece que si n palomas se distribuyen en palomares, y si n > m, entonces al menos habrá un palomar con más de una paloma” (Wikipedia).

Un ejemplo del palomar:

“Tengo 3 personas, te puedo asegurar que hay 2 que tienen el mismo sexo”. La cantidad de sexos es 2 = m y la cantidad de personas es 3 = n. Entonces 3 > 2 y n > m, entonces al menos habrá dos personas del mismo sexo.

Ahora, volvamos al problema planteado. La resolución larga es más explicativa y está enfocada a las personas de un nivel escolar. La resolución corta es la resolución aburrida y va para los universitarios, aunque probablemente ambos la puedan entender.

Solución 1 (resolución larga):

  1. Cada vez que se sientan 6 personas en una mesa al menos dos de ellos tienen la misma edad.
    1. Acá claramente hay una aplicación del principio del palomar. Si las 6 personas son palomas y las edades son los palomares esto implica que teniendo 5 palomares, al menos 2 palomas quedarán en el mismo palomar. O sea, hay 5 edades distintas para todas las personas, así siempre que tome un grupo de 6 personas, al menos 2 tendrán la misma edad. Estos palomares los llamaremos palomares de edades.
  2. Las personas vienen de 5 países distintos.
    1. Esto significa que tenemos 5 palomares de países. Como tenemos 206 personas, esto significa que en cada palomar hay 41 personas (41 x 5 = 205) y una persona extra que queda en alguno de los palomares. ¿Por qué hacemos esto? Porque queremos construir un palomar que considere nacionalidad, edad y sexo.
  3. Tomemos el caso de las personas de 1 país (41 personas) y sus edades. No importa el país, si tomamos uno cualquiera no perdemos generalidad.
    1. Tenemos 5 palomares de edades como vimos en el punto 1 o 5 edades distintas
    2. Las 41 personas divididas en los 5 palomares de edades implica que habrán 8 personas en cada palomar de edad y una persona extra que queda en alguno de los palomares de edad. A este palomar le llamaremos palomar de edad y nacionalidad.
  4. Ahora tomemos el palomar de edad y nacionalidad que tiene 9 personas. Por principio del palomar las podemos dividir en dos sexos: masculino y femenino. Como son 9 personas, en un palomar quedarán 5 y en el otro 4. Estas 9 personas ya sabemos que tienen la misma edad y la misma nacionalidad y si consideramos la última división tenemos 5 personas que tienen el mismo sexo. O sea, tenemos 5 personas con misma edad, nacionalidad y sexo.
  5. El enunciado nos pedía: “Demuestre que entre los 206 pasajeros hay al menos cinco pasajeros que tienen la misma edad, el mismo sexo y la misma nacionalidad” que es justamente lo que demostramos.
  6. Un aspecto que no se puede dejar pasar es que esta es una demostración. Esto quiere decir que cualquiera que sea el grupo que cumpla los requisitos esto se va a dar, cualquier grupo. Es importante tener esto en cuenta porque alguna persona puede tomar 1 grupo en particular y mostrar que se cumple, pero nosotros lo demostramos para todos los grupos posibles. Hay una gran diferencia en eso y la recalco para que la analicen.
  7. Desafío: Si te fijas en el punto 4 hay una persona que sobró. ¿Cuál podría ser el enunciado más estricto del problema para utilizar a todas las personas? No mires la resolución corta, ya que, ahí se ve el enunciado más estricto.

Solución 2 (Resolución corta):

  1. Usaremos el punto 1 de la resolución larga. Tenemos personas que pueden ser de 5 países distintos, de 5 edades distintas y de 2 sexos distintos. Entonces por cada país puedo tener 5 edades distintas, o sea, puedo armar 5 x 5 = 25  palomares distintos, donde cada uno tiene una nacionalidad y una edad, pero ninguno se repite.
  2. Ahora, agregemosle el género y tenemos 25 x 2, porque a cada uno de los palomares anteriores le agregamos el sexo M o F. Esto implica que tenemos 50 palomares distintos para meter a 206 personas. Cada uno de estos palomares contiene a personas que tengan el mismo sexo, misma nacionalidad y misma edad.
  3. Entonces aplicando palomar, tenemos 206 personas y dividido en 50 es 4, con resto 6. O sea, esas 6 personas que quedaron en el resto deben entrar a cualquiera de los palomares que ya contienen 4 personas. Esto implica que tenemos un palomar con 5 personas que tienen el mismo sexo, la misma nacionalidad y la misma edad. De hecho, con esas 6 personas podemos tener al menos 6 grupos que cumplen la condición, así que podríamos hacer el enunciado más estricto.

Bueno, espero que le haya gustado el problema y ahora como desafío, ¿cómo lo resolverían solo con dibujitos? ¿podrían olvidar el principio del palomar para resolverlo?

Categorías: Cmat | 3 comentarios

Crea un blog o un sitio web gratuitos con WordPress.com.