20. Aritmética modular para Sawyer, Locke y demás Perdidos |
Escrito por Alfonso J. Población Sáez |
Jueves 01 de Febrero de 2007 |
De cómo un conjunto de números aparecido en la serie Perdidos permite introducir a los alumnos en la interpolación polinómica (ver mes pasado) y la aritmética modular. Después la guía habitual de la serie Numb3rs, ahora incrementada por su recuperación en Antena 3 los jueves. Solución a la cuestión planteada a propósito de los números de Lost Recordemos la cuestión planteada hace dos meses: el polinomio interpolador con nodos los números naturales del 1 al 6 e imágenes los valores 4, 8, 15, 16, 23, 42, respectivamente, es decir el polinomio P(x) = (– 9 x5 + 170 x4 – 1175 x3 + 3670 x2 – 4896 x + 2400) toma valores enteros (P(x) ∈ Z) para cualquier x∈Z (para los no habituados, Z designa al conjunto de los números enteros). Se pide probar (o refutar) esta afirmación. De la media docena de mensajes recibidos (es un alivio saber que hay alguien por ahí), describo la enviada por Alberto Castaño Domínguez, lector habitual de esta y otras secciones de DivulgaMAT, por ser la más concisa y elegante (al menos bajo mi punto de vista). A su razonamiento añado algunos comentarios que intentan acercar la prueba a la inmensa mayoría. Utiliza (como debe ser en un ejercicio de este tipo) congruencias. Supongo que todos conocéis qué es eso. Por si acaso, hagamos un pequeño repaso. Hay muchas situaciones, aplicaciones, problemas, en los que únicamente se está interesado en conocer el resto de la división de dos números enteros. Estas cuestiones las estudia la aritmética modular, y el concepto básico inicial que emplea es el de números congruentes. Dos números a y b son congruentes módulo m si al dividir ambos por ese valor m producen el mismo resto. Se representa así: a ≡ b mod m. Por ejemplo, 23 ≡ 15 mod 4, porque al dividir 23 entre 4 y 15 entre 4 el resto es el mismo, 3. Es fácil probar que a ≡ b mod m, si y sólo si, a-b es un múltiplo de m En matemáticas esto se escribe diciendo que m|(a-b) (se lee, m divide a a−b, es decir, que a−b dividido entre m tiene resto cero). Diariamente utilizamos las congruencias en muchas ocasiones. Por ejemplo leyendo la hora de los relojes: las 23 horas son las 11 de la noche. El reloj sólo tiene 12 horas, sólo utiliza 12 números, y después de recorrerlos todos, las 13 horas equivale a la 1 de la tarde (o sea 23 ≡ 11 mod 12). La letra del NIF se calcula mediante congruencias. En informática para asignar localizaciones de memoria de un ordenador a los datos que componen un fichero (por ejemplo para asignar claves a los usuarios de tarjetas de crédito, o para localizar los datos de los alumnos de un colegio), se utilizan congruencias. Volvamos a nuestro polinomio. Escribamos su expresión del siguiente modo: −40 P(x) = 9 x5 - 170 x4 + 1175 x3 - 3670 x2 + 4896 x − 2400 El problema es equivalente a demostrar que el segundo miembro de la igualdad toma siempre valores múltiplos de 40 para cualquier x entero que pongamos. Para que un número sea múltiplo de 40, debe ser múltiplo de 8 y de 5. Pues probemos esto último. Podemos simplificar un poco los coeficientes. 170 = 21 x 8 + 2. O sea que al dividir 170 entre 8 nos da el mismo resto que al dividir 2 entre 8 (es decir, 170 ≡ 2 mod 8), por lo que ¿para qué vamos a trabajar con números grandes? En lugar de 170 pongamos 2 que para lo que queremos ver, da igual. De este modo, repasando todos los coeficientes, tenemos que
Entonces en vez de trabajar con el polinomio inicial, podemos trabajar con uno más sencillo: Q(x) = x5 − 2x4 − x3 + 2x2 = x2 (x3 − 2x2 − x + 2) Finalmente se trata de comprobar que al sustituir x por cualquiera de los ocho valores con los que trabajamos módulo 8, obtenemos un múltiplo de 8. Es decir, Utilizamos el mismo razonamiento para demostrar que P(x) es múltiplo de 5 para cualquier x entero que pongamos. Calculemos los coeficientes de P(x) módulo 5:
Ahora el polinomio módulo 5 es R(x) = −x5 + x Veo por ahí alguien que levanta la mano y pregunta que porqué no hemos hecho la cuenta una única vez buscando las congruencias directamente con 40 en vez de con 5 y con 8 y así trabajar con un único polinomio. En efecto, se puede hacer, pero piensa un poco. Con el polinomio obtenido debemos después calcular ¡40 valores! Mientras que así, aunque trabajemos con dos polinomios (muy sencillos por otro lado), sólo hemos precisado calcular 13 imágenes. Por muy supersticioso que uno sea, el ahorro de trabajo compensa. ¿Alguna otra pregunta? No. Pues continuemos……
1.- Alex de la Iglesia ha comenzado el rodaje de la película Los crímenes de Oxford, basada en la novela homónima de nuestro compañero y colaborador de DivulgaMAT, Guillermo Martínez. En http://blasfemandoenelvrticedeluniverso.blogspot.com podéis ir leyendo cómo se va desarrollando el rodaje diariamente junto a las reflexiones del director. Entre los actores se encuentran Elijah Word, Sir John Hurt (que encarna al matemático Arthur Seldon), Leonor Watling y Tom Frederic, entre otros. 2.- Desde el jueves 18 de Enero Antena 3 Televisión ha decidido emitir los capítulos de la primera temporada de Numb3rs que no habían programado en un horario más “normal” (23:00). El 18 de Enero pusieron el capítulo 1.8.- Crisis de Identidad y el 25 de Enero el 1.9.- El francotirador. Si todo va como debe ser, el jueves 1 de febrero emitirán el episodio 1.10.- Una bomba sucia, el 8 de febrero el 1.11.- El sacrificio, el 15 el episodio 1.12.- Más allá del ruido y el 22 el 1.13.- La caza del hombre. Sus reseñas las tenéis en el artículo del mes de Abril de 2006. Recordemos que en la primera tanda no emitieron el episodio 1.4.- Fallo de Estructura (que podría aparecer en cualquier momento, o no).
Episodio 2.18.- Todo es justo (All´s Fair). Fechas de emisión: Lunes 5 de Febrero (22:20), Martes 6 de Febrero (17:45), Sábado 17 de Febrero (21:30), Domingo 18 (15:30). Argumento: Saida es una ciudadana iraquí que va a realizar un documental en los Estados Unidos. Mientras hablaba por un teléfono móvil, es raptada y asesinada el día anterior a mantener una importante entrevista. Previamente había recibido algunas amenazas de muerte. El agente Kareem Allawi se une al equipo de Don para investigar el caso. Mientras, Charlie cena con una antigua amiga, Susan Berry, que se encuentra en Los Ángeles en la promoción de un libro. Ambos parecen llevarse muy bien …. Aspectos Matemáticos: Probabilidad y Regresión Logística, juegos con información incompleta, Sudokus y Cuadrados Latinos. En este capítulo, el agente Don trata de resolver un crimen en el que el testimonio de varios testigos parece ser falso. Varios testigos indican que tres sospechosos tienen aproximadamente la misma estatura, pero esos valores no concuerdan con el sexo de los mismos. Entonces pregunta a su hermano si hay algún procedimiento matemático que ayude a determinar que declaraciones de los testigos son las correctas. Su hermano propone utilizar una regresión logística. Se trata de un modelo útil cuando se trata de predecir el valor de una variable que sólo admite dos posibilidades (dicotómica). La función de regresión proporciona la probabilidad de que se verifique un suceso y su expresión más común es con α, β, γ constantes. Es un modelo que se utiliza mucho en ciencias de la salud (presencia o ausencia de enfermedad o infección en un individuo), en biología, sociología, etc. La anterior expresión responde a un modelo en una sola variable (volviendo al ejemplo médico, se utiliza un único factor de riesgo como dato), aunque pueden manejarse más variables (xj, j= 1, ..., m), en cuyo caso hablamos de regresión logística múltiple. En otro momento Charlie vuelve a echar mano de la teoría de juegos para analizar las motivaciones y estrategias que determinan que personas pudieran ser las más proclives a cometer un acto terrorista. Utilizando los datos que conocen de cada sospechoso, los hermanos asignan a cada uno una probabilidad de llegar a cometer un crimen. En esta ocasión el modelo a utilizar es el mismo que se emplearía en un juego en el que parte de la información es desconocida o se ha perdido. A pesar de ello, un análisis de la situación puede llevarnos a adoptar decisiones realistas. En otra escena Alan, Charlie y Larry están haciendo un sudoku. Todo el mundo a estas alturas sabe en qué consiste este pasatiempo. Los primeros sudokus aparecieron en mayo de 1979 en la revista Dell Péncil Puzzles and Word Games con el nombre de Number Place. Parece ser que fue el arquitecto jubilado Howard Garns, fallecido en 1989, el autor de este entretenimiento. En 1984 llegó a Japón que lo rebautizó como Sudoku, una especie de acrónimo de la frase “las cifras deben quedar solteras”. Su difusión mundial se debe a otro jubilado, el juez neozelandés Wayne Gould, residente en Hong-Kong, que escribió un programa informático que genera sudokus automáticamente. Después, ya sabemos, el boom gracias a los periódicos de medio mundo. Episodio 2.19 – La materia oscura (Dark Matter) Fechas de emisión: Lunes, 12 de Febrero (22:20), Martes 13 de Febrero (17:45), Sábado 24 de Febrero (21:30), Domingo 25 (15:30). Argumento: En un instituto de Secundaria se producen varios disparos, muriendo varias personas. El equipo de Don tratará de encontrar a los asesinos cuyo comportamiento parece obedecer a las reglas de unos juegos de ordenador. Charlie, que había jurado no volver a pisar un instituto desde que se graduó, tendrá que echar una mano. Aspectos Matemáticos: Chips de radio frecuencia (RFID) La única referencia relacionada ligeramente con las matemáticas del capítulo es el de la localización de los estudiantes mediante unos chips RFID implementados en sus tarjetas de identificación escolares. Describamos brevemente en qué consisten. En el capítulo cada alumno tiene uno de estos chips en su tarjeta de estudiante en los que además se incluyen sus datos personales. En varios lugares del instituto hay antenas que envían señales a estos chips cada cierto tiempo. Cuando un alumno se encuentra dentro de la zona de influencia de estas antenas administradoras, el chip RFID se enciende y manda sus datos que son almacenados. El elevado número de alumnos y la frecuencia con que se mandan datos (que puede ser cada segundo) constituyen una cantidad impresionante de datos que es sin embargo fácilmente clasificada y analizada por un programa informático. Esto permite conocer donde se encuentra cada estudiante en todo momento dentro de un rango de influencia concreto. Los receptores pasivos no tienen un sistema propio de energía sino que son “alimentados” por la señal transmitida por el transmisor-receptor. Esta señal es una onda electromagnética con capacidad suficiente para activar el circuito del chip que es alterada por la información que contiene y rebotada al receptor. Estos chips son más baratos (aproximadamente la décima parte del valor de los “activos”). Es previsible que en un futuro no muy lejano todos los objetos tengan un chip de éstos. Es decir, pantalones, zapatos, libros, etc., tendrán un chip en el que constará donde se compró el artículo, cuando y quien lo hizo. Imaginaos: uno entra en una tienda y una voz sintetizada que comience a decir, “Hola, fulanito de tal. Esos pantalones que llevas los compraste hace tres años y va siendo hora de que los cambies. En la planta cuarta está la sección de caballero en la que encontrarás…., y bla, bla, bla”. ¡Qué horror!, ¿verdad? Vayamos a las matemáticas. Supongamos un objeto en el suelo situado en unas coordenadas (x, y). Supongamos que el objeto comienza a moverse. Sus coordenadas camban con el tiempo. Después de t segundos el objeto se encuentra en un punto (x(t), y(t)). Por ejemplo si su posición en el instante t viniera dada por (3t-2, 2t+5), entonces el objeto se está moviendo a lo largo de una línea recta. Al comienzo estaría en el punto (-2, 5) y al cabo de 4 segundos estaría en (10, 13). El camino que recorre el objeto se denomina trayectoria. La descripción de su posición en función del tiempo se llama dar una parametrización. Charlie en el episodio que nos ocupa trata de parametrizar la trayectoria de cada alumno a lo largo del instituto durante los disparos. Utiliza para ello los datos obtenidos por los chips de los carnés de los estudiantes: fija un sistema de coordenadas para cada habitación a partir de un plano del instituto (coloca el origen en un lugar central de cada sala, designa dos pasillos como ejes X, Y), después elige un estudiante cualquiera y toma sus datos del chip desde el receptor que esté más próximo a él en cada momento. Con estos datos, un ordenador calcula las coordenadas del estudiante, lo que da una parametrización de su trayectoria. En http://es.wikiedia.org/wiki/RFID podéis ampliar la información relativa a este tipo de dispositivos. Episodio 2.20 – Disparos y Rosas (Guns and Roses) Fechas de emisión: Lunes 19 de Febrero (22:20), Martes 20 de Febrero (17:45), Sábado 3 de Marzo (21:30), Domingo 4 de Marzo (15:30). Argumento: Una agente del ATF (Siglas correspondientes a Alcohol, Tobacco and Firearms, es decir, se trata de una organización Norteamericana que depende del Departamento del Tesoro, dedicada a estos asuntos, Alcohol, Tabaco y Armas de fuego), Nikki Amstead, aparece muerta en su domicilio en lo que parece ser un suicidio. Su compañero Eric Turner le pide a Don que le ayude a investigar el caso. A Don no parece hacerle demasiada gracia. Conocía a la fallecida demasiado bien… Aspectos Matemáticos: Biomatemáticas: Análisis de ondas sonoras (sónar) y alineación de pruebas de ADN. Producto matricial. Cuando la agente aparece muerta, el sonido del disparo fue registrado por varios instrumentos creando lo que se conoce como “huella acústica” de la habitación y sus ocupantes. De forma análoga a como los murciélagos y otros animales emplean su sónar natural, Charlie será capaz de descubrir a partir de esas grabaciones que algo (o alguien) falta en la habitación. Tal y como se van obteniendo nuevas pruebas, a Charlie cada vez le parece menos verosímil la hipótesis del suicidio. Para aclarar las cosas un poco más, decide utilizar lo que él denomina “test de estrés de Holmes-Rahe modificado”. Este test “mide” el nivel de estrés de una persona a partir de valores obtenidos en situaciones concretas. El resultado es un número. Cuanto más alto es, mayor estrés soporta la persona en su vida. Para explicar cómo funciona alude a las puntuaciones que se dan en los torneos de monopatín: la puntuación dada por los jueces mide la dificultad del salto, la puesta en escena del mismo, etc. Este sistema de puntuación se utiliza también con algunas variaciones en deportes olímpicos como la gimnasia o los saltos de trampolín. Con un ejemplo lo entenderemos mejor. Supongamos que un atleta va a realizar seis ejercicios baremados con un orden de dificultad de 2.3, 3.1, 3.9, 3.6, 2.8 y 3.2, respectivamente. Hay tres jueces que dan las siguientes puntuaciones a cada ejercicio:
La nota final de cada juez vendrá dada por el producto de sus puntuaciones por el nivel de dificultad del ejercicio evaluado. Y hacer estas sumas y productos resulta un tanto engorroso. Para facilitar la labor se utiliza el producto matricial. Colocamos los niveles de dificultad en una matriz 1 x 6 (un vector en este caso) y las puntuaciones de los jueces en una matriz 6 x 3 del siguiente modo: Así obtenemos de forma sencilla (en las competiciones reales, lo hace el ordenador o la calculadora) las puntuaciones totales de cada juez. Todo se basa en una eficaz disposición de los datos. Un ejemplo curioso para mostrar a los alumnos una aplicación de las matrices. Además de recoger los sonidos efectuados antes de la muerte de la víctima, el equipo del FBI toma diferentes muestras de ADN de la habitación. Analizando estas muestras, Charlie tratará de obtener algún dato sobre los familiares del sospechoso. Aunque las muestras de ADN no permiten identificar a una persona en concreto, si que se pueden deducir algunos rasgos como enfermedades congénitas, color del pelo, si tiene pecas, etc. Existen empresas que han conformado índices estadísticos de la información que las cadenas de ADN suministran. Charlie emplea una técnica denominada alineación de secuencias de ADN. Consiste en comparar dos de ellas atendiendo a sus componentes. Es conocido (y si no lo recordamos ahora) que el ADN se compone de cuatro nucleótidos que contienen las bases adenina (A), guanina (G), citosina (C) y tiamina (T). En estado natural, los pares de bases se forman sólo entre A y T, y G y C en forma de doble hélice; por tanto, la secuencia de las bases de una de las dos cadenas se puede deducir de la otra. Dadas dos cadenas de ADN se trata de casar el máximo número de bases posible (sin reordenarlas obviamente). La tarea no es trivial: el ADN del ser humano contiene unos 3 x 109 pares de nucleótidos. Episodio 2.21 – Disparos a discreción (Rampage) Fechas de emisión: Lunes 26 de Febrero (22:20), Martes 27 de Febrero (17:45), Sábado 10 de Marzo (21:30), Domingo 11 de Marzo (15:30). Argumento: Un individuo entra en las oficinas del FBI disparando a diestro y siniestro. Los agentes tratarán de determinar los motivos que le indujeron a comportarse así y su posible relación con un peligroso traficante de armas que se encuentra a la espera de juicio. Charlie está un tanto asustado porque casi le alcanzan los disparos y no quiere ni oír hablar de volver a las dependencias del FBI, lo cual dificulta la resolución del caso. Aspectos Matemáticos: Movimiento browniano, Hipercubos. Lo primero que piensa Charlie sobre el comportamiento del sujeto es que se ajusta a un movimiento browniano. El movimiento browniano es el movimiento aleatorio que se observa en algunas partículas que se hallan en un medio fluido (por ejemplo, polen en una gota de agua). Recibe su nombre en honor a Robert Brown que lo describe en 1827. En 1785, el mismo fenómeno había sido descrito por Jan Ingenhousz sobre partículas de carbón en alcohol. En 1900, Louis Bachelier describió por primera vez el movimiento browniano matemáticamente. Posteriormente, en 1923, Norbert Wiener y Paul Lévy elaboraron el modelo que sigue una partícula que en cada instante se desplaza de manera independiente de su pasado, como si la partícula “olvidara” de dónde viene y decidiese continuamente, y mediante un procedimiento aleatorio, hacia dónde ir. Es pues un movimiento que, a pesar de ser continuo, cambia en todo punto de dirección y de velocidad; tiene trayectoria continua, pero no tiene tangente en ningún punto. En 1945 Albert Einstein dedicó uno de sus artículos a este asunto. En otro instante los hermanos discuten sobre acotación de desigualdades como un procedimiento para intentar localizar a un sospechoso. Conocida la posición del individuo en un momento dado, se trata de acotar la zona cercana de influencia a la que éste podría desplazarse. Su conversación es interrumpida, pero desde el punto de vista matemático, se utilizan diagramas de Venn (círculos en dos dimensiones, y esferas en tres) en muchas ocasiones para acotar o estrechar las posibilidades de búsqueda de algo o alguien. Finalmente hay una conversación entre Charlie y Amita, su alumna doctorando, sobre la cuarta dimensión. En concreto de refieren a un Hipercubo (también conocido como Tesseract). En realidad no son lo mismo. Un hipercubo es el nombre con el que se conoce cualquier objeto de más de tres dimensiones, mientras que tesseract sería el equivalente en cuatro dimensiones de un cubo. O sea un tesseract es un hipercubo de cuatro dimensiones. En el siguiente enlace podéis tratar de imaginar cómo sería mediante la explicación y posterior descarga de un fichero ejecutable. Tenéis que buscar el artículo titulado Hipercubo tetradimensional (hacia el final de la página). |