Archivo de la categoría: Sin clasificar

Un problema de probabilidad y escuchar música

El problema

Les comparto un problema que se me ocurrió en las (muchas) horas que he pasado en el carro escuchando música, cuando vivía en la Ciudad de México. El estéreo del carro ordena las canciones alfabéticamente. Tiene un botón que permite «avanzar una canción». Pero a veces tarda mucho: si estoy escuchando «Adele – Hello», hay que apretar el botón muchas veces para llegar a «Shakira – Dónde están los ladrones».

En esas épocas descubrí una estrategia «intuitiva» para llegar más rápido a la canción. La idea es la siguiente: pasar temporalmente al modo de «canción aleatoria», apretar el botón unas cuantas veces para acercarme a la canción que quiero (en el ejemplo anterior, digamos que después de dos o tres veces el botón me lleva a «Paquita la del Barrio – Rata de dos Patas»), y de ahí quitar el aleatorio y avanzar normal. Eso, intuitivamente, siempre me ahorró muchos pasos. El problema consiste en encontrar la estrategia óptima, en donde se permiten mezclar pasos normales y aleatorios.

Para eso, voy a plantear un problema muy concreto. De aquí en adelante supondré que el lector sabe un poco de probabilidad. Pensemos que hay 2n canciones, numeradas de 1 a 2n. Estoy en la canción n y quiero llegar a la canción 2n. Pensemos que el estéreo tiene exactamente dos botones, el A que avanza 1 (y de 2n lleva a 1), y el B que lleva a una canción aleatoria (cualquiera de las canciones, incluida la actual, tiene probabilidad 1/2n de ser elegida). En cada paso se permite ver en qué canción estoy, y de ahí decidir apretar A o B. ¿Cuál es la estrategia que en valor esperado tiene menos pasos? ¿Cuál es ese valor esperado?

En la imagen de aquí abajo se muestra un ejemplo de una forma de apretar los botones para n=5, con 2n=10 canciones. Las flechas rojas corresponden a avanzar 1 apretando el botón A. Las flechas azules corresponden a ir a un lugar aleatorio apretando el botón B. Se apretaron los botones en el orden ABBAA, de modo que se hicieron 5 pasos.

Ejemplo de estrategia ABBAA
Un ejemplo en el que se usa la estrategia ABBAA. La canción 1 es de ABBA. Es Dancing Queen. «Feel the beat form the tambourine… Oh yeah…».

Ese es el enunciado del problema. De aquí en adelante empiezo a hablar de ideas para resolverlo, así que si quieres intentarlo, este es el momento correcto.

Primeras ideas

Notemos que la estrategia «siempre A, hasta llegar a 2n» toma exactamente n pasos siempre. La estrategia «siempre B» es para intentar atinarle, y en cada paso tiene probabilidad de éxito 1/2n. Entonces, en esta segunda estrategia la cantidad de pasos requeridos es una variable aleatoria con distribución geométrica de parámetro p=1/2n, de modo que el número esperado de pasos es 1/p=2n.

Sin embargo, suena a que la estrategia esbozada al inicio de esta entrada es intuitivamente mejor: usar el B para acercarse y luego el A para llegar.

La solución

Vamos a mostrar que la mejor estrategia en valor esperado es la siguiente: «apretar el botón B hasta llegar aproximadamente al intervalo [n-2\sqrt{n}, n], y de ahí apretar el botón A» hasta llegar a n.

El primer argumento es que en cada paso, lo que hace la estrategia sólo depende de en qué canción estamos. En efecto, el paso A es determinista y el B es una variable uniforme independiente de todo lo demás.

El segundo argumento es que, si en algún momento de la estrategia usamos el botón A, entonces después de ello nunca nos conviene usar el botón B. Lo probamos por contradicción: supongamos que por cualquier razón en la estrategia óptima tenemos que hacer un AB. El paso A es determinista, y sabíamos exactamente a qué canción nos iba a llevar (a la siguiente). Pero hacer el paso B en cualquier lugar que estemos es simétrico, pues nos lleva a una canción aleatoria. Si a priori sabíamos que íbamos a hacer un paso B, lo mejor es hacerlo lo antes posible. Así, la estrategia que substituye esos pasos AB por B se ahorra un paso, y no es óptima. Contradicción.

Ahora, afirmo lo siguiente. Si la estrategia óptima es apretar A cuando estamos en la canción j, entonces también va a ser apretar A cuando estemos en cualquier canción k con j\leq k < 2n. Esto es debido al argumento anterior: al apretar A llegamos a j+1, que por el párrafo de arriba, no le puede tocar B. Entonces le toca A. De ahí llegamos a j+2, que de nuevo no le puede tocar B. Y así sucesivamente (inductivamente), hasta llegar a 2n-1.

Lo que acabamos de probar es que la estrategia óptima se ve de la siguiente manera para algún entero k: «Apretar B hasta que lleguemos a alguno de los últimos k elementos. De ahí, apretar A hasta llegar a 2n.» Nos falta determinar cuál es la mejor k que podemos usar.

A estas alturas ya podemos calcular explícitamente el valor esperado de pasos en esta estrategia. El evento «llegar a alguno de los últimos k elementos» tiene probabilidad k/2n de ocurrir cada que se aprieta el botón B, así que la cantidad de veces que hay que apretar B para ello es una variable aleatoria geométrica de valor esperado 2n/k. Una vez que llegamos a los últimos k elementos, caemos a cualquier elemento del intervalo \{2n-k+1, 2n-k+2,\ldots,2n\} con la misma probabilidad, y respectivamente nos tomará \{k-1, k-2,\ldots, 0\} pasos en llegar a 2n, es decir, la cantidad de pasos que hacemos es una variable aleatoria uniforme discreta de media (k-1)/2.

Así, en total usamos (2n/k) + (k-1)/2 pasos para llegar. Queremos lograr que esta expresión sea lo más pequeña posible. Usando la desigualdad entre la media geométrica y la aritmética, notamos que

    \[\frac{2n}{k}+\frac{k-1}{2}=\frac{2n}{k}+\frac{k}{2}-\frac{1}{2} \geq 2\sqrt{n} - \frac{1}{2},\]

y que la igualdad se da si y sólo si \frac{2n}{k}=\frac{k}{2}, es decir, si y sólo si k=2\sqrt{n}. En este caso, la cantidad media de pasos que usamos es 2\sqrt{n}-\frac{1}{2}.

Aquí arriba hicimos un poquito de trampa. En realidad k=2\sqrt{n} tiene sentido para la estrategia sólo cuando \sqrt{n} es un número entero. Sin embargo, por la convexidad de la función \frac{2n}{k}+\frac{k}{2} tenemos la garantía de que o bien \lfloor 2\sqrt{n} \rfloor o bien \lceil 2\sqrt{n} \rceil dan el máximo.

Conclusión y otros problemas

Está cool que hayamos bajado la cantidad de pasos que se necesitan de valor esperado de algo que era n a algo que es del tamaño 2\sqrt{n}. Para hacerse una idea de los pasos que se pueden ahorrar, toma una colección de 800 canciones. Originalmente se necesitaban 400 pasos +1 para ir de la mitad al final. Con la nueva estrategia se requieren como 40.

Hacer esta estrategia en la vida real es un poco complicado pues los estéreos no muestran el número exacto de la canción en la que se está, además de que es difícil memorizar a qué canción le toca qué número. Pero a veces sí muestran el nombre de la canción y más o menos «se le puede aproximar».

Hay un par de variantes interesantes. Una es ¿qué sucede si además de tener botón +1 y aleatorio, también tenemos botón -1?. En esta variante la solución no cambia mucho, pero es bueno intentarla para repasar las ideas de la prueba.

La otra variante es la siguiente. La estrategia óptima, como está descrita arriba, tiene un problema: es posible que nunca termine, o que tome muchísimos pasos en terminar (esto será muy improbable y por eso el valor medio se compensa). Así, imaginemos que queremos la restricción adicional de que la estrategia que usemos nunca use más de, digamos, 4n pasos. En esta variante: ¿cuál es la estrategia óptima? ¿cuántos pasos toma?

VIII Concurso Galois-Noether: Segunda Etapa

Ken 2 CC-BY - Editada2

En esta entrada se dan los resultados de la segunda etapa del VIII Concurso Universitario de Matemáticas Galois-Noether que se aplicó el día sábado 9 de junio de 2018. Hubo 27 participantes de habla hispana y 52 de habla portuguesa.

Problemas y soluciones

El examen consistió de seis problemas para resolver en cuatro horas y media. Al inicio del examen hubo media hora para aclarar los enunciados de los problemas. Puedes ver los problemas del examen, así como sus soluciones, en el siguiente archivo.

Cada problema se evaluó sobre 10 puntos, dando puntos parciales por avances hacia la solución.

A continuación se enuncia el tema de cada problema.

  • Problema 1: Desigualdades
  • Problema 2: Álgebra lineal
  • Problema 3: Cálculo
  • Problema 4: Teoría de números
  • Problema 5: Probabilidad
  • Problema 6: Teoría de grupos

De acuerdo a las estadísticas, los problemas 1, 2, 5 y 6 tuvieron aproximadamente la dificultad deseada. Los problemas 3 y 4 quedaron un poco más fáciles de lo que se esperaba, de modo que en las puntuaciones altas fue difícil marcar una distinción clara entre las habilidades de los concursantes. En años siguientes se buscará subir un poco la dificultad de estos problemas.

Sobre los concursantes

En total 79 personas presentaron el examen de segunda etapa. De entre los que presentaron el examen, el promedio redondeado a centésimas fue de 15.17. La calificación más alta fue 38 puntos y la más baja fue 2.

Ganadores del VIII Concurso Galois-Noether

A continuación se muestran los primeros tres lugares de la competencia. En caso de empate, el criterio de desempate fue la puntuación del examen de primera etapa.

  1. Thiago – Landim de Souza Leao – Universidade Federal de Penambuco – Brasil
  2. Thiago Ribeiro Tergolino – Instituto Militar de Engenharia – Brasil
  3. Wesley Rodrigues Machado – Instituto Militar de Engenharia – Brasil

¡Muchas felicidades a ellos tres! Para quedar en estos lugares se requiere de una gran cantidad de trabajo bien orientado.

Selección de la UNAM para la IX CIIM

De acuerdo a la convocatoria, el examen Galois-Noether sirve como selectivo para determinar a los cuatro estudiantes que representan al equipo de la UNAM en la Competencia Iberoamericana Interuniversitaria de Matemáticas. Los cuatro alumnos de la UNAM con la mejor puntuación del examen y que participarán en la CIIM fueron:

  • Víctor Hugo Almendra Hernández
  • Leonardo Ariel García Morán
  • Siddhartha Emmanuel Guzmán Morales
  • Zeús Caballero Pérez

¡Muchas felicidades!

El Líder del Equipo de la UNAM para la IX CIIM fue el Mat. Luis Eduardo García Hernández, quien ha colaborado en la organización de la competencia y otras actividades de resolución de problemas a nivel universitario.

¡Les deseamos mucho éxito a todos ellos en la IX CIIM!

Constancias y dudas

Todos los concursantes que hayan participado en la segunda etapa pueden solicitar una constancia. Cualquier estudiante puede consultar su calificación personal desglosada por problema. Para realizar cualquiera de estas dos cosas, favor de escribir a leomtz@im.unam.mx.

Taller SEME de interacción matemáticas-industria

Esta semana participaré en la Semana de Estudios Matemáticas-Empresa en el Instituto de Matemáticas de Orsay. La idea es cool: varias organizaciones francesas vienen, presentan problemas frente a un montón de doctorantes y postdocs, y ellos proponen modelos para atenderlos. Creo que en México el CIMAT hace algo parecido.

Instituto de Matemáticas de Orsay

Esta vez viene Aeropuertos de París, el SNFC (encargada de trenes y metro) y algunas empresas. A mi me tocó Aeropuertos de París y trabajaremos en la detección de ruido aéreo. Mi plan es ver cómo se trabaja en esto para después intentar implementarlo en otros lados.

Las empresas traen algunas ideas de como resolverlos. Proponen desde cosas estándar aplicadas como series de tiempo, análisis estadísticos, optimización combinatoria, hasta cosas «de moda» como machine learning y algoritmos de IoT. Se ve que estará divertido.

Los detalles del taller se pueden encontrar en el siguiente enlace: https://www.math.u-psud.fr/seme2019/programme.php

Aborto y la taxonomía de los embarazos no deseados

Introducción

En estos días las redes sociales están repletas de comentarios que discuten la legalidad del aborto. Si bien es un tema interesante por sí mismo, el reciente proceso en Argentina para determinar su legalidad ha sido catalizador para que decenas de personas viertan sus opiniones al respecto. Debido a que es un tema muy polémico, a veces las discusiones no se encuentran en el mismo nivel retórico y esto genera caos y antagonizmos.

La idea principal de esta entrada no es dar mi punto de vista acerca de algunas aristas del problema, aunque hablaré de ello hacia el final. Más bien la principal razón por la que escribo esta entrada es para dejar en claro los diversos niveles de discusión del tema, de modo que ayude a tener discusiones más informadas y conciliatorias.

Los problemas principales

Hay dos situaciones con las que queremos lidiar. La más discutida es la siguiente.

Situación 1: Una mujer (o una pareja) ya se encuentra en una situación de embarazo no deseado. Lidiar con esto incorrectamente trae consecuencias severas.
Problema 1: Lidiar de la mejor forma posible con este embarazo no deseado.

Por supuesto, sin un marco ético este problema no está bien definido. ¿Qué es «la mejor forma»? ¿Qué es lidiar? Mencionaré eso en breve, pero sígueme la corriente por un momento antes de entrar a esos detalles.

La Situación 1 es corolario de otra situación:

Situación 2: Existen los embarazos no deseados.
Problema 2: Erradicar o minimizar la cantidad de embarazos no deseados

De nuevo, hay que precisar términos. Pero estoy seguro que a estas alturas podemos estar de casi de acuerdo en las siguientes cosas:

  • Son problemas diferentes. El Problema 1 asume que ya se dio un embarazo no deseado y lo que se pregunta es la mejor forma de lidiar con él. El Problema 2 se pregunta por un paso antes del embarazo no deseado.
  • Ninguno de los dos problemas se puede resolver en su totalidad. Siempre habrá excepciones que se escapen a las precauciones tomadas. A lo mejor que podemos apuntar es a intentar resolverlos de manera óptima.
  • Si quieremos minimizar las «consecuencias severas» del Problema 1, entonces tenemos que lidiar con ambos.
  • El Problema 1 tiene más matices éticos y espirituales que el Problema 2.

Sobre la Situación 1

Supongamos por el momento que una mujer (o pareja) tiene un embarazo no deseado. «Lo mejor» que se puede hacer depende mucho del sistema de valores de cada persona.

Por un lado, para alguien de pensamiento progresista la madre tiene derecho absoluto sobre su cuerpo y debería poder abortar si así lo desea. Bajo este punto de vista el estado debe de permitir de manera legar ejercer el aborto para minimizar los riesgos inherentes a los abortos clandestinos. Llevando este punto de vista más al extremo, el estado incluso debe proveer mediante la seguridad social el acceso gratuito a la interrupción del embarazo.

Por otro lado, para un católico fundamentalista se tiene que respetar la vida desde la concepción. Sus creencias le dicen que incluso a los pocos días el ente concebido tiene un alma, y que su derecho a la vida está por encima del derecho de la madre para decidir qué hacer con su cuerpo. Desde este sistema de creencias existen otras formas de lidiar con el aborto clandestino: apoyar a la madre durante su embarazo, encontrar un destino para el hijo no deseado, educar con respecto a los riesgos de los métodos caseros de aborto.

Idealmente, dentro de una sociedad laica, tenemos que abstenernos de permitir que nuestra espiritualidad interfiera con los asuntos de estado. Lo más adecuado sería actuar de manera objetiva y científica. Pero no creo que esto sea posible en este momento. Lo más acertado es orientarnos por la ciencia y las respuestas parciales que tiene con respecto a conexiones neuronales, impulsos nerviosos y conciencia de uno mismo.

Sobre la Situación 2

Lo que me gusta de la Situación 2 es que estudiarla es mucho más objetivo que estudiar la Situación 1. Más aún, el análisis de la Situación 1 pone mucha carga en la (o las) víctimas del embarazo no deseado. Resolver el Problema 2 ataca el problema de raíz, quita la carga de responsabilidad de abortar o no de las víctimas, y la pone sobre las políticas públicas o los perpetradores.

Discutamos la Situación 2 entonces. Lo que buscamos ahora es minimizar la cantidad de embarazos no deseados. Es definitivamente un problema grande y problemas grandes requieren buenas soluciones. En matemáticas usamos el método de divide-y-conquista para encontrar sub-problemas pequeños que sean más fáciles de atacar. Para determinar estos problemas en el caso del aborto, conviene establecer una taxonomía de los embarazos no deseados. A continuación propongo una taxonomía ejemplo que, si bien no afirmo que sea óptima, por lo menos cubre una gran cantidad de los casos.

Me gustaría empezar con los embarazos no deseados consecuencia de una relación sexual no consensuada. En este caso estamos en el área de violencia intrafamiliar, abuso de poder y de delincuencia. Este es el problema que atienden iniciativas como #MeToo. Se tienen que implementar políticas que faciliten que la víctima hable, que sea escuchada y que los culpables tengan el castigo que merecen.

De este modo, supondré ahora que el embarazo no deseado es consecuencia de una relación sexual consensuada. Para determinar cómo disminuirlos, me parece que de entre ellos hay que distinguir aquellos en los que no se tuvo prevención, y aquellos en los que sí.

Cuando digo que el embarazo fue a causa de no tener prevención, pienso en varias posibilidades. Una es que no haya intención de prevención por malicia de alguna de las partes (hombre o mujer), con lo cual de nuevo caemos en el tema de violencia. Otra es que no haya intención de prevención por ignorancia, para lo cual necesitamos buenas políticas de educación sexual. Finalmente, pienso en los casos en los que aún con la intención de tener prevención, no la hay por falta de medios económicos. Aquí debe haber un esfuerzo de seguridad social para proveer métodos anticonceptivos de manera gratuita.

Con una naturaleza distinta están los embarazos no deseados en donde sí hubo prevención. Pero hablo no sólo de una prevención «light» en la que se usa sólo condón o sólo pastillas anticonceptivas. Me parece que estas medidas mínimas siguen cayendo en la falta de educación sexual. A lo que me refiero es a una discusión seria con la pareja para evitar el embarazo no deseado en la mayor medida posible: usar más de un método, tener un plan de acción para un condón roto, etc. Un embarazo no deseado bajo estas circunstancias es, desde mi punto de vista, de los que no se van a poder erradicar: son verdaderos accidentes.

Idealmente, se tienen que establecer políticas públicas mediante las cuales sólo la ínfima cantidad de embarazos correspondientes a los verdaderos accidentes tengan que pasar a ser tratados en la Situación 1.

A título personal

Yo no creo en la vida desde la concepción. En general soy de pensamiento progresista. En mi muy particular punto de vista:

  • Se requiere atender tanto la Situación 1 como la Situación 2, pero…
  • … idealmente un embarazo no deseado debería ser algo muy, muy excepcional y hacia allá hay que ir, por lo que…
  • … hay que invertir más energía y recursos públicos a la Situación 2.
  • Mientras sigan existiendo embarazos no deseados, deben existir opciones legales para interrumpirlos. Cada persona (paciente o médico), debe tener el derecho de ser partícipe, o no, del aborto de acuerdo a su sistema de valores y creencias, así como su circunstancia.

Algunos casos esquina

Hay preguntas tangenciales que también surgen en las discusiones sobre la legalidad del aborto. Si bien desvían el tema de los problemas principales, también vale la pena estar atentos a su existencia para mantener el debate enfocado y tal vez para discutirlas en su momento.

  • Si una madre prosigue con el embarazo no deseado, ¿eso necesariamente implica que tiene que proseguir con la maternidad?
  • Si una de las partes responsables del embarazo (o un tercero ) quiere al hijo, pero la otra no, ¿el embarazo debe proseguir?
  • ¿Hasta las cuántas semanas se debe permitir el aborto?

Concurso Galois-Noether 2018: Resultados 1a Etapa

Generales

¡Los resultados de la primera etapa del Concurso Universitario de Matemáticas Galois-Noether 2018 ya están listos!

El examen se aplicó en 14 sedes y a través de la gran red de universidades que participan en Olimpiada Brasileña de Matemáticas. Se hizo una versión del examen en español y una versión en portugués. La versión en español fue aplicada a 152 concursantes y la versión en portugués a 733, marcando la edición del concurso con más participantes hasta la fecha.

Nos alegra contar con la participación de distintas sedes y el interés de concursantes a través de America Latina y Brasil. Es una señal del creciente interés de la resolución de problemas a nivel universitario.

Respuestas y fe de erratas

Las respuestas correctas a los problemas del examen son:

  • 1 a 5: B D C C C
  • 6 a 10: D D C X C
  • 11 a 15: C D X C B
  • 16 a 20: A B A D A
  • 21 a 25: C D B B C

Las X significan errores en el examen. Agradecemos a los organizadores y concursantes que nos hicieron llegar observaciones al respecto. Las revisamos con cuidado y mencionamos las siguientes correcciones.

Los problemas 9 y 13 de la versión del examen en español tenían errores. En el problema 9 la solución correcta era 16, pero esta no era una de las opciones. En el problema 13 se puede ver que la función requerida no existe. Adicionalmente, el problema 25 tenía una pequeña imprecisión en la redacción. Estos errores fueron corregidos en la versión en portugués.

La selección del corte fue decidida con cuidado tomando estos errores en cuenta, tomando las decisiones de modo que más personas fueran incluidas para la segunda etapa.

Estadística de puntuaciones y corte

Debido a las ligeras diferencias entre el examen en español y en portugués, las estadísticas del examen se presentan por separado. Los resultados de OBM se presentan sin considerar los problemas 9 y 13

Media español: 8.81 de 25
Varianza español: 14.88
Media portugués: 9.24 de 23
Varianza portugués: 14.55

Para garantizar que la selección de ganadores se realizara de manera equivalente, el corte fue elegido por separado para la versión en portugués y la versión en español. De esta forma, la regla de 15% de concursantes y las consideraciones adicionales dan los siguientes cortes:

Corte español: 14/25 puntos
Corte portugués: 13/23 puntos

Listas de ganadores

Aplicando los cortes anteriores, un total de 157 concursantes pasan a la segunda etapa del concurso. La lista de ganadores se puede consultar en el siguiente enlace.

Ganadores Primera Etapa Galois-Noether 2018

A todos estos concursantes: ¡Muchas felicidades por este logro!

Pueden encontrar material para continuar con su preparación en este enlace.

El examen de segunda etapa se llevará a cabo el próximo sábado 9 de junio en la sede a la que asistieron a realizar la primera etapa. Les pedimos de favor ponerse en contacto con el organizador local de la sede para acordar detalles de ubicación y hora.

Invitados adicionales

Adicionalmente, los siguientes concursantes de la UNAM también son invitados para presentar el examen el sábado 9 de junio como parte del proceso selectivo para conformar al equipo que representará a la UNAM en la CIIM 2018 (pero no como parte del Concurso Galois-Noether):
  • Rodrigo Malagón Rodríguez
  • Siddhartha Emmanuel Morales Guzmán
  • Zeús Caballero Pérez

Dudas o aclaraciones

Como siempre, estamos al pendiente de cualquier duda del concurso o aclaraciones sobre el proceso. Cualquier duda se puede preguntar mediante los comentarios de esta publicación, o bien al correo leomtz[a]im.unam.mx.