Con dos tiradas suele bastar

¿Quieres que nos juguemos el café? Mira, vamos a lanzar un dado por turnos e ir sumando los resultados que vayamos obteniendo. Gana el primero que con su tirada pase del número de caras del dado. Llevo mis dados de Magic en el bolsillo,  vamos a usar el de 20 para añadir un poco de emoción, así que ganará el primero que llegue a 20. ¿Vale? Empiezas tú. Tiras, sacas un 7, no llegas a 20. Tiro yo, saco un 6: 7+6=13, no llego a 20, tira. Sacas un 12: 13+12=25, ganas. ¡Mier…,!  ¡Uy, perdón, eso sí que no me lo esperaba! ¿Al mejor de tres?

(2 horas antes)

Estaba leyendo la autobiografía matemática de John Allen Paulos  y en un momento dado cita un artículo suyo en ABCnews  con apariciones estelares (la primera, literalmente) del número e. Una de ellas es, traduzco (y abrevio):

John Allen Paulos

Escoger números al azar también puede dar lugar a e. Elige un número entero aleatorio entre 1 y 1000. (Digamos que escoges 381.) Elige otro número aleatorio (digamos 191) y súmalo al primero (en este caso, da 572). Continua eligiendo números aleatorios entre 1 y 1000 y sumándolos a la suma de los números aleatorios escogidos previamente. Detente sólo cuando la suma supere los 1000. (Si el tercer número fuera 613, por ejemplo, la suma pasaría de 1000 después de tres selecciones.)

¿Cuántos números aleatorios, en promedio, necesitarás elegir? En otras palabras, si un grupo grande de personas repite este procedimiento, generar números entre 1 y 1000 y sumarlos hasta que la suma pase de 1000 y registrar el número de selecciones que han necesitado para llegar superar el 1000, el número promedio de dichas selecciones sería –lo has adivinado– muy próximo a e.

 

Pues sí, en la página del Wolfram Mathworld sobre la distribución de sumas de copias de una variable uniforme en [0,1] encontraréis la demostración de que si vais tomando números al azar entre 0 y 1 con distribución uniforme y sumándolos, la probabilidad de que la primera elección en la que la suma sea \geq 1 sea la n-ésima es 1/(n(n-2)!) y de que, entonces, la esperanza de esta distribución de probabilidades, es decir, el número promedio de números que tendremos que tomar para superar el 1, es e. Multiplicando por 1000, y quitando partes decimales, obtenéis la aproximación citada por Paulos.

Naturalmente, aunque lanzar un dado de N caras sea escoger un número entero al azar (y equiprobablemente) entre 1 y N, si N es pequeño entonces los decimales que se borran juegan un papel importante. Por ejemplo, con un dado de 6 caras, el número medio de lanzamientos necesarios para sumar 6 o més es un poco más de 2.16, y con un dado de 20 caras para superar el 20 necesitamos en promedio un poco más de 2.52. Con el dado de 100 caras que todos los matemáticos tenemos en casa rondamos el 2.68.

Pero hay otro dato que me interesa en el juego de tirar el dado y sumar hasta superar el umbral: si jugamos con un dado de N caras, más de la mitad de las veces llegaremos a N en la segunda tirada, independientemente de N. Esta probabilidad es muy sencilla de calcular: para pasar de N en la segunda tirada pero no en la primera, tenemos que sacar un k entre 1 y N-1 en la primera tirada y luego en la segunda cualquiera de los k+1 valores que hacen que la suma supere N (por ejemplo, si con un dado de 20 caras en la primera tirada saco un 5, para llegar a 20 en la segunda necesito algo entre 15 y 20). Por tanto, de las N^2 posibles tiradas dobles, en \sum\limits_{k=1}^{N-1} (k+1)=(N+2)(N-1)/2 pasaremos de N sin que en la primera tirada lleguemos a N, y este número es mayor que  N^2/2 si N\geq 3. En concreto, la probabilidad de superar N en dos tiradas de un dado de N caras es de aproximadamente 0.56 si N=4 o N=6; 0.53 si N=12; y 0.52 si N=20.

Así que en el jueguecito del principio, si dejamos empezar al otro, lo más probable es que ganemos en la segunda jugada, independientemente del dado. Y si no, siempre nos queda la cuarta, la sexta…

-Hola, Cesc, te veo muy concentrado

-¡Hola! Sí, estaba haciendo unos cálculos. Oye,  ¿quieres que nos juguemos el café? Mira, vamos a lanzar un dado por turnos…

Esta entrada participa en la Edición 8.5 del Carnaval de Matemáticas cuyo anfitrión es Raíz de 2.

 

Advertisements

¿Cuántas hojas tiene el árbol 2017?

¿Conocéis el chiste aquel de los dos presos que hace mucho tiempo que comparten celda,  y va uno y le pide al otro “Va, cuéntame un chiste”, el otro contesta “El 56” y el primero se parte de risa? Pues últimamente yo estoy en la tesitura de “Va, dame un árbol”, y ya me va bien que me den el 56, pero claro, luego he de saber cuál es. En última instancia, numerar objetos es una manera de ponerles nombre y por lo tanto de poseerlos. Pero entonces es necesario un diccionario que nos permita recuperar los objetos a partir de los números, y si ese diccionario se puede reducir a un algoritmo sencillo, mejor.

En el caso de los árboles (en lo que sigue, por un “árbol” entiendo  un árbol en el sentido de la teoría de grafos y con raíz, que en los dibujos corresponde al nodo superior), hay una numeración muy útil: los números de Matula, que se definen recursivamente de la manera siguiente. Si T es un árbol de un solo nodo, M(T)=1. Si T tiene más de un nodo y T_1,\ldots,T_k son los subárboles que cuelgan de los hijos de su raíz y m_1=M(T_1),\ldots, m_k=M(T_k) son los números de Matula de estos subárboles y p_{m_1},\ldots,p_{m_k} son los primos m_1-ésimo, m_2-ésimo, …, m_k-ésimo, entonces M(T)=p_{m_1}\cdots p_{m_k}.

Veamos un ejemplo. Considerad el árbol de la figura, lo llamaremos T (y como hoy es el día del orgullo friki, uso Comic Sans).

Para calcular su número de Matula, hemos de calcular los de sus subárboles T1 y T2. El de T2 és fácil: 1, porque es un solo nodo (una hoja). El número de Matula de T1 será el producto de los primos correspondientes a los de T3 y T4, así que necesitamos calcular primero los números de Matula de T3 y T4. Veamos: la raíz de T3 tiene 3 hijos y los tres son hojas, por lo que cada uno define un subárbol de un solo nodo; por lo tanto, cada uno de estos subárboles tiene número de Matula 1, y como el primer primo es p_1=2, tenemos que M(T3)=p_1\cdot p_1\cdot p_1=2\cdot 2 \cdot 2=8. Por otro lado,  la raíz de T4 tiene 2 hijos, los dos hojas, por lo que cada uno define un subárbol de un solo nodo, de número de Matula 1. Obtenemos entonces que M(T4)=p_1\cdot p_1=2\cdot 2=4.

Como T3 y T4 son los árboles número 8 y 4, respectivamente, por la recurrencia, M(T1) será el producto del octavo primo, p_{8}=19, y del cuarto primo, p_4=7: M(T_2)=19\cdot 7=133. Y como M(T2)=1, tenemos finalmente que M(T) será el producto del primo en la posición 133, p_{133}=751 y del primer primo, p_1=2. Es decir, M(T)=751\cdot 2=1502.

Este proceso se puede invertir. Dado un número N, lo descomponemos en producto de números primos N=q_1\cdots q_m y buscamos cuál es el número de orden de cada q_i en la lista de todos los primos: digamos que cada q_i es el primo m_i-ésimo. Entonces, la raíz de el árbol T M(T)=N tendrá m hijos, y de ellos colgarán los árboles T_i número M(T_i)=m_i. Naturalmente, si N=1 entonces T es el árbol de un solo nodo, por definición.

Por ejemplo, ¿cuál el es árbol 2017? 2017 es primo, en concreto p_{306}. Por lo tanto el árbol 2017 estará formado por una raíz de la que cuelga un solo hijo, que es la raíz del árbol número 306. Ahora 306=2\cdot 3\cdot 3 \cdot 17. Como p_1=2, p_2=3 y p_7=17, el árbol 306 está formado por una raíz de la que cuelgan 4 hijos, que son raíces de un árbol número 1 (un solo nodo), dos árboles número 2, y un árbol número 7. Os dejo terminar: el árbol número 2 está formado por una raíz con un único hijo que además es una hoja, y el árbol número 7 (=p_4) está formado por una raíz con un único hijo del que cuelgan dos hijos que son hojas. El resultado es el de la figura que sigue.

 

Por lo tanto, cada árbol tiene su número y cada número (natural y a partir de 1) representa un único árbol. Ya los tenemos numerado. Pero además,  muchas propiedades de un árbol se pueden obtener a partir de su número, sin tener que reconstruir el árbol. Por ejemplo, su número de hojas. Es fácil comprobar, siguiendo la reconstrucción de un árbol a partir de su número, que si llamamos N(T) al número de hojas de T e indicamos por T_n el árbol número n, entonces

  • N(T_1)=1,
  • N(T_n)=N(T_m)  si n=p_m
  • N(T_n)=N(T_{q_1})+\cdots+N(T_{q_k}) si n=q_1\cdots q_k y k\geq 2

Por ejemplo, el número de hojas de nuestro árbol T número 2017 es N(T_{2017}) =N(T_{306}) =N(T_{2\cdot 3\cdot 3 \cdot 17}) =N(T_2)+2N(T_3)+N(T_{17})=N(T_2)+2N(T_2)+N(T_{7})=3N(T_2) +N(T_4)=3N(T_2) +2N(T_2)=5N(T_2)=5N(T_1)=5

¡Bien!

Otros muchos índices de un árbol se pueden calcular de manera recursiva a partir de su número de Matula. De hecho, ya os podéis imaginar que todo lo que se pueda calcular recurrentemente de hijos a padres se podrá determinar a partir del número de Matula.  Si os interesa, este artículo de E. Deutsch explica la manera de calcular una trentena de índices.

Esta entrada participa en la edición 8.4 del Carnaval de Matemáticas, cuyo blog anfitrión es matematicascercanas.

 

Carreras de raíces digitales de primos

En su famoso artículo “Prime Number Races” (The American Mathematical Monthly, 2006; encontraréis  la versión española en la Gaceta de la RSME aquí), A. Granville y G. Martin popularizaron las carreras de primos, que ya habían sido introducidas por Knapowski y Turán en una serie de artículos en Acta Arithmetica a mediados de los años 1960. Por una carrera de primos no me refiero a que en alguna fiesta familiar se organize una carrera en la que participen todos los nietos del patriarca. No. En nuestras carreras de primos, se fija un módulo (por ejemplo, 4) y cada participante escoge un resto para ese módulo que sea coprimo con él (por ejemplo, yo escojo el 1 y tú escoges el 3). Entonces, a medida que se va recorriendo la lista de números primos, cada resto que aparece suma 1 al que lo ha escogido. Al final, cuando se llega a la meta prefijada, gana el participante cuyo resto haya aparecido más veces: ¿Que han salido más unos? Gano yo. ¿Más treses? Ganas tú. ¿Empate? Empate.

Los resultados que se conocen sobre carreras de primos son fascinantes, y se remontan al trabajo de Littlewood sobre el Teorema de los números primos. Fijemos algunas notaciones, para abreviar el lenguaje. Denotaremos por \pi(n;q,a) el número de primos \leq n que son congruentes con a  módulo q; supondremos siempre que a y q son coprimos, aunque no lo digamos explícitamente. Recordemos, además, que \pi(n) indica el número de todos los primos \leq n. Por ejemplo, siguiendo con los primos módulo 4, \pi(n; 4, 1) y \pi(n;4,3) son los números de primos menores o iguales a n que son congruentes con 1 y con 3 módulo 4, respectivamente.

El teorema de los números primos para progresiones aritméticas que citaba en un post anterior garantiza que, cuando n\to \infty, la fracción \pi(n; q,a)/\pi(n) tiende a 1/\phi(q) (donde \phi es la función de Euler que nos da el número de restos módulo q coprimos con este). Por ejemplo, a medida que n tiende a infinito, los primos \leq n congruentes con 1 módulo 4 tienden a ser la mitad, y los congruentes con 3 módulo 4 la otra mitad.

Ahora bien, la pregunta relevante para nuestras carreras de primos es ¿cómo se van comportando las cantidades \pi(n; 4, 1) y \pi(n;4,3) a medida que n crece? ¿Quién tiene más probabilidades de ganar una carrera?

Ya en 1835,  Chebyshov (¿ahora se escribe así?) mencionaba en una carta que parecía haber muchos más primos congruentes módulo 4 con 3 que con 1 (el famoso sesgo de Chebyshov). De hecho, la primera vez que \pi(n; 4, 1)>\pi(n;4,3) es en n=26861 y luego no vuelve a pasar hasta n=616841. No obstante, un teorema de Littlewood garantiza que el signo de \pi(n; 4, 1)- \pi(n;4,3) cambia infinitas veces, así que hay infinitas ocasiones en que en las que el 1 gana al 3.

Ahora bien, si la Hipótesis generalizada de Riemann y la Conjetura de Independencia Lineal LI de los ceros de \zeta(x) son verdaderas, Rubinstein y Sarnak demostraron en 1994 que, en un cierto sentido específico, la “probabilidad” de que \pi(n; 4, 3) sea mayor que \pi(n;4,1) es del 99.6%. Más en general, el teorema de Rubinstein y Sarnak dice que

  • si a y b son ambos cuadrados o ambos no cuadrados módulo q, la “probabilidad” de que \pi(n; q,a)>\pi(n; q,b) es 0.5
  • si a no es un cuadrado módulo q y b sí, la “probabilidad” de que \pi(n; q,a)>\pi(n; q,b) es mayor que 0.5 (y puede ser mucho mayor, como vemos para q=4)

Así que, ya sabéis, si queréis jugar a las carreras de primos, procurad escoger un resto que no sea un cuadrado módulo el q escogido.

Para probar, vamos a hacer carreras con las raíces digitales de los primos, que no son más que restos módulo 9, y comparar con el resultado teórico. Compitiendo en la pista, las raíces digitales 1, 2, 4, 5, 7 y 8, que son las coprimas con 9. Fijaos que 1, 4 y 7 son cuadrados módulo 9, y 2, 5 y 8 no. He tomado los tres primeros millones de primos menos el 2 y el 3. ¿En cuántas ocasiones cada una de las raíces digitales ha ido en cabeza de la carrera (posiblemente empatado con otra)? Aquí tenéis la tabla:

tablaRD

Como podéis ver, sobre 2.999.998 puntos de cronometraje, 1 y 4 solo han ido en cabeza 3306 y 7920 veces, aproximadamente un 0.1% y un 0.2% de las ocasiones. El 7 es más curioso, porque ha ido en cabeza un número de veces dos órdenes en magnitud mayor, pese a ser un cuadrado módulo 9. Las raíces 2, 5 y 8 han ido aproximadamente un tercio de las ocasiones en cabeza, 100.000 arriba, 100.000 abajo.

Vale, 1 y 4 no vale la pena que jueguen, no son de la misma liga que los otros. Voy a comparar los otros. Como el gráfico de la competición de los cuatro corredores de golpe es difícil de interpretar, he generado un gráfico para cada par de corredores. Muestro el primero y lo explico, y así el resto se entenderán.

2contra5

Los puntos rojos repersentan el 2 y los azules el 5. En cada momento, el color que está en la línea superior es quien va ganando, y el de la línea inferior, perdiendo. Los puntos centrales son aquellos en los que empatan (que han quedado azules porque son los segundos que he dibujado, y se han superpuesto). El eje de abscisas representa el índice de los primos: va del tercero al que hace 3 millones.

Bueno, aquí vienen el resto de competiciones por parejas. De ellos podéis deducir fácilmente (módulo lo que podáis magnificar las imágenes y afinar las longitudes) en cada momento quién gana. Por ejemplo, en el primo que hace 2.000.000, 5 gana a 2, 2 gana a 7, 8 gana a 2 y 5 gana a 8, por tanto 5 gana.

2contra7

2contra8

5contra7

5contra8

7contra8

Ah, bueno, una última cosa. ¿Cómo quedan al llegar al primo 3.000.000? Pues en primer lugar llega el 8, seguido del 7, seguido del 2, seguido del 4 casi empatado con el 5 y, farolillo rojo el 1. La diferencia entre el número de ochos y el número de unos al terminar la carrera es de 229. La mayor diferencia entre el que va en cabeza y el que va a la cola se da alrededor del primo número 2.271.290, es de 403, y en ese momento el que va ganando es el 8 y el que va perdiendo el 7.

Y hala, esta entrada participa en la edición 7.4 del Carnaval de Matemáticas, cuyo blog anfitrión es ::ZTFNews.

 

Dos de cada tres estudiantes de la UIB, matriculados en carreras con muchos estudiantes. ¿Notición?

Estos días estoy meditando sobre aplicaciones de la paradoja de la amistad en el análisis de redes de interacciones de proteínas. Como Clara Grima ya explicó coj…mente esta paradoja en esta entrada de Cienciaxplora, voy a ahorraros los detalles. En todo caso, y en resumen, se trata del hecho que, para la mayoría de nosotros, nuestros amigos tienen, de media, más amigos que nosotros (y son más felices y más guapos que nosotros, y han ligado a lo largo de su vida más que nosotros y …). Por suerte, esto (normalmente) no tiene nada que ver con nuestra personalidad, sino que es un teorema de teoría de grafos atribuido a Scott Feld, que lo enunció, demostró y analizó en su artículo del 1991 titulado Why your friends have more friends than You do.

En realidad, esta paradoja viene de más lejos, de la llamada “paradoja del tamaño de la clase” que introdujeron el mismo Scott Feld y Bernard Grofman en un artículo de 1977 titulado Variation in class size, the class size paradox, and some consequences for students:

si escogemos al azar un estudiante de un centro, el tamaño esperado del curso en el que está matriculado es casi siempre estrictamente mayor que el tamaño medio de los cursos de su centro, y en todo caso nunca menor.

Además, en muchas distribuciones razonables de números de matriculados por curso, una gran mayoría de los estudiantes están matriculados en cursos más numerosos que la media (lo que les lleva, por comparación, al desánimo y al abandono de los estudios, según los autores; igual se lo podemos explicar a las comisiones de acreditación de los grados: “no es culpa nuestra que abandonen los estudios, es que no saben teoría de grafos y creen que son unos desgraciados por estar en cursos numerosos”).

Aquí viene la demostración. Sean x_1,\ldots, x_n los números de alumnos de los n cursos que ofrece un determinado centro. Entonces:

  • El valor medio de alumnos por curso es \overline{x}=(\sum_{i=1}^n x_i)/n
  • Pero si consultamos todos los estudiantes uno a uno y les pedimos cuántos estudiantes hay en su curso, y calculamos la media de los valores obtenidos, será otro cantar: para cada curso de x_i alumnos, habrá  x_i alumnos que contestarán “x_i”, por lo que cada respuesta  x_i aparecerá x_i veces. La suma total de respuestas será, por lo tanto, \overbrace{x_1+\cdots+x_1}^{x_1} +\cdots+ \overbrace{x_n+\cdots+x_n}^{x_n}=\sum_{i=1}^n x_i^2. La respuesta media por alumno (es decir, el número medio de matriculados en el curso en el que está matriculado un alumno escogido al azar), llamémosle \overline{x}_{al}, se obtendrá dividiendo esta suma por el número de respuestas:  \overline{x}_{al}=(\sum_{i=1}^n x_i^2)/(\sum_{i=1}^n x_i)

Si ahora restamos \overline{x}_{al}-\overline{x}=(\sum_{i=1}^n x_i^2)/(\sum_{i=1}^n x_i)-(\sum_{i=1}^n x_i)/n, un pequeño cálculo algebraico muestra que es igual a la varianza \mathrm{var}(x) de x_1,\ldots, x_n partido por su media \overline{x}. Y ahora es el momento de recordar que la varianza siempre es positiva, y es 0 sólo cuando x_1=\cdots=x_n. Por lo tanto, salvo en este caso, el número medio de matriculados en el curso de un estudiante escogido al azar será siempre mayor que el número medio de matriculados por curso. Y cuánto mayor sea la varianza, es decir, cuánto más variados sean los números x_1,\ldots, x_n, mayor será el cociente entre estas dos medias.

Vale, un experimento. He sacado de aquí los números de matriculados en los 30 grados de la UIB en el curso 2013-14 (los matriculados en dobles titulaciones los he contado en cada una de los grados involucrados). Estos números van de los 1228 matriculados en Administración de Empresas a los 93 matriculados en Matemáticas. He calculado el número medio de estudiantes por grado, \overline{x}, y el número medio de estudiantes matriculados en el grado de un estudiante aleatorio, \overline{x}_{al}. Los resultados (redondeados) han sido \overline{x}=366\overline{x}_{al}=593: un estudiante está matriculado de media en un grado de 593 estudiantes, pero el número medio de estudiantes por grado es de 366. Además, un 66.5% de los estudiantes de la UIB están matriculados en grados con un número de estudiantes mayor que la media. Es raro que algunos periódicos tradicionalmente críticos por defecto con la UIB no lo hayan publicado nunca.

El código R, por si queréis confirmar los números, es muy sencillo.

 ests.UIB=c(1228,1042,1028,623,612,560,497,467,432,412,400,351,339,
252,243,231,228,226,215,180,174,154,169,156,146,140,134,131,116,93)
#Media de alumnos por grado
mean(ests.UIB)
#Media de alumnos por grado desde el punto de vista del alumno
sum(ests.UIB^2)/sum(ests.UIB)
#Porcentaje de alumnos en grados más numerosos que la media
sum(ests.UIB[ests.UIB>mean(ests.UIB)])/sum(ests.UIB)

En cambio no sé cómo usar la paradoja de la amistad para explicar la percepción de los estudiantes de que sus amigos siempre tienen menos tareas que ellos para hacer en casa.

 

El 26 y los capicúas

Qué mejor día para quitar las telarañas a este blog que el 26 de febrero, 262, capicúa.
Aunque en realidad yo quería hablar de otro 26-2 capicúa, el 26^2=676. Resulta que el 26 es el menor número natural no capicúa que elevado al cuadrado da capicúa. El siguiente ya es el 264, que elevado al cuadrado da 69696.

Los números capicúas son muy populares en matemática recreativa, y recientemente se ha demostrado que también son relevantes en aritmética. Justo este pasado mes de agosto, William Banks, de la Univ. de Missouri, demostró que todo número natural es igual a la suma de números capicúas. Me podríais decir: bah, el 1 es capicúa y todo número es suma de unos, mira tú. No es esto. Bueno, sí, tendríais razón, pero Banks demostró algo más concreto: que, por grande que sea el número natural que nos den, siempre podemos encontrar una familia de, como máximo, 49 números capicúas cuya suma sea el número dado.

Hay muchas preguntas sobre potencias capicúas para las que los matemáticos desconocemos la respuesta. Por ejemplo, cuántos números no capicúas hay cuyo cuadrado sea capicúa? Hay infinitos? No se sabe. El más grande que se conoce tiene 28 dígitos, y su cuadrado, 55, y fue descubierto en 2008 por Feng Yuan, un informático aficionado a este tipo de cuestiones del estado de Washington, pero no sabemos si hay otros más adelante.

En cambio, es fácil producir tantos números capicúas con cuadrado capicúa como queráis: por ejemplo, tomad cualquier número formado por un 1, seguido de una secuencia de ceros y acabado con otro 1: 11, 101, 1001, 10001 etc. El cuadrado de un número de estos se obtiene siempre concatenando dos copias del número y cambiando el 11 que aparece en medio por un 2; es un buen ejercicio demostrarlo. Y en particular, como vemos, este cuadrado es capicúa.

Hay otras preguntas sobre números capicúas que permanecen abiertas. Por ejemplo, sólo se conoce un número no capicúa que elevado al cubo dé capicúa, el 2201; no se sabe si hay más. No se conoce ningún número no capicúa que elevado a la cuarta potencia dé capicúa, y no se sabe si existen. Y, para rematarlo, no se conoce ningún número diferente de 1, capicúa o no, tanto da, ninguno, que elevado a 5 o más dé capicúa. Antes de que os pongáis con la calculadora a buscar, tengo que avisaros de que ya se han comprobado todos los números de hasta 14 cifras y todas las potencias hasta 10. Será el tipo de problemas para los que decía Erdös que la matemática actual aún no está preparada?

Esta entrada participa en la Edición 7.1 del Carnaval de Matemáticas cuyo anfitrión es Tito Eliatron Dixit.

Añadido en prensa: Al poco de publicar la entrada me entero por Gaussianos de que  Javier Cilleruelo, de la Universidad Autónoma de Madrid, ha reducido la cota de Banks de 49 a 3: todo número natural es suma de como máximo 3 capicúas.

La simetría también es buena… en el cáncer

Las caras simétricas nos parecen más bonitas. Las simetrías en las decoraciones de la Alhambra y otros edificios árabes nos resultan fascinantes. 196.000 resultados en Google de “symmetry is good”. Bueno, pues resulta que un tipo concreto de simetría también es buena señal en el cáncer.

Para algunos tipos de cáncer, se han publicado sus redes de interacciones de proteínas (PPI) en la base de datos KEGG PATHWAY. Estas redes representan el conocimiento actual sobre las interacciones entre proteínas en células cancerosas. Desde el punto de vista matemático, son grafos no dirigidos relativamente grandes, sin bucles ni aristas múltiples. Una línea de investigación muy popular en biología computacional de sistemas es la reconstrucción automática de este tipo de redes a partir de datos experimentales, y el estudio y comparación de los grafos resultantes.

Una propiedad que se puede estudiar en un grafo es su simetría. Se dice que un grafo es simétrico cuando tiene algún automorfismo diferente de la identidad, y más simétrico es cuantos más automorfismos tiene, ea decir, cuanto más fácil sea intercambiar algunos de sus nodos sin que se modifique la estructura abstracta de conexiones que representa.Es bien sabido que si escogemos al azar (de manera equiprobable) un grafo de n nodos, la probabilidad de que sea simétrico tiende a 0 a medida que n tiende a \infty. En cambio, las grandes redes complejas de la vida real (desde Internet a las redes biomoleculars) tienen grupos de automorfismos muy grandes, como se puede comprobar en la tabla 1 de Symmetry in Complex Networks de B. MacArthur, R. Sánchez-García y J. Anderson. Esto se puede tomar como un síntoma más de que las redes complejas de la vida real son poco aleatorias.

Una manera de medir la simetría de un grafo G de n nodos es mediante el siguiente índice, que cuantifica la fracción  de automorfismos en el conjunto total de permutaciones de sus vértices:

\displaystyle\beta(G)=\left(\frac{|Aut(G)|}{n!}\right)^{\frac{1}{n}}

En un artículo colgado en el arXiv el pasado mes de mayo, P. Hinow, A. Rietman, J. Tuszynski han calculado este índice \beta para las redes PPI de algunos tipos de cáncer, y los han comparado con su probabilidad estimada p de supervivencia a los 5 años (que se puede obtener del Surveillance, Epidemiology, and End Results Program). Su conclusión se resume en el gráfico siguiente:

regrsim

Este gráfico muestra una clara correlación positiva entre la probabilidad de supervivencia y el índice de simetría \beta: a más simétrico, más benigno. El coeficiente de determinación R^2 que obtienen es de 0.52. No es para echar las campanas al vuelo, pero dados por un lado la gran imprecisión en la estimación de la mortalidad para los diferentes tipos de cáncer que se obtiene del SEER, y por otro nuestro desconocimiento del detalle completo de las redes PPI, la correlación que obtienen se puede considerar significativa.

So what? Bueno, es curioso. Cuánto más simétrica es una red PPI, más reemplazables son sus elementos por otras proteínas en la misma red, lo que la vuelve más robusta a fallos cuando alguna proteína se elimina del sistema por ejemplo mediante algún medicamento. Que esta propiedad esté correlacionada positivamente con la probabilidad de supervivencia a 5 años va completamente en contra de nuestra intuición, y muestra que aún nos falta mucho por aprender sobre el comportamiento del cáncer.

Una semana en el Isaac Newton Institute

La semana pasada participamos en el workshop: Mathematical, Statistical and Computational Aspects of the New Science of Metagenomics. Fueron cinco dias intensos, de muchas y buenas charlas de metagenómica, nueva rama del mundo de la biología computacional que estudia el conjunto de genomas de un determinado entorno directamente a partir de muestras de ese ambiente, sin necesidad de aislar y cultivar esas especies.  IMG_7618El workshop, así como el resto de reuniones y sesiones que continuaran a lo largo de las próximas semanas, lo han organizado  Wally Gilks (University of Leeds), Daniel Huson (Universität Tübingen), Elisa Loza (Rothamsted Research), Gabriel Valiente (Universitat Politècnica de Catalunya) y Tandy Warnow (University of Texas at Austin) junto con el Isaac Newton Institute programme Mathematical, Statistical and Computational Aspects of the New Science of Metagenomics.

La idea de este programa es reunir investigadores de distintas ramas de la metagenómica para poner en común sus puntos de vista y discutir sobre el futuro de la metagenómica. Para ello, se ha dedicado la primera semana  de este programa a la explicación y puesta en común de los trabajos realizados por los distintos investigadores, para en las próximas semanas pasar a una lluvia de ideas, discusión y finalmente algunas conclusiones del trabajo futuro a realizar.

Durante la semana pudimos disfrutar de buenas y diversas charlas. Inició la sesión Meyer F. del Argonne National Laboratory (USA), titulada Lessons learned from operating a bit metagenomics resource, en la que pudimos disfrutar de una excepcional descripción de lo que ha sido la investigación en metagenómica por el momento y, sobretodo, de los retos y dificultades que conllevan la necesidad de utilizar bases de datos de gran magnitud.   El segundo día se dedicó enteramente al problema de ensamblaje de secuencias. Diversos conferenciantes mostraron los distintos algoritmos y técnicas usadas para dicho fin, poniendo de manifiesto las dificultades inherentes al ensamblaje dentro del mundo de la metagenómica.

El tercer día lo empezamos con una charla de E. Rubin, del Joint Genome Institut Lawrence Berkeley National Laboratory, (USA). Edward nos impresionó con una charla en la que cuestionó la separación en tres dominios de las especies y animó a los investigadores asistentes a usar las herramientas de la metagenómica para encontrar un nuevo dominio y nuevas especies, principalmente entre las bacterias y archaeas. Durante el resto del día, así como el día siguiente, tuvimos charlas también interesantes sobre metabolismo, proteómica y transcripción de distintas comunidades de microbios estudiadas desde el punto de vista de la metagenómica, con algunas conclusiones muy interesantes sobre los distintos ecosistemas estudiados y algunas aplicaciones médicas.

Tal y como se acostumbra a hacer en los workshops, el tercer día finalizó con una cena de gala, en la que tuvimos el placer de hablar tranquila y distendidamente con algunos de los participantes. La disposición del comedor, una gran mesa ovalada en la que estábamos sentados todos los comensales, posiblemente el hecho de que el comedor fuera la sala de lectura del Cambridge Union Society, e indiscutiblemente, la compañía de los comensales, hicieron que la velada fuera realmente agradable.

La tarde del cuarto día se dedicó a la presentación de distintas herramientas informáticas para la metagenómica, poniendo de manifiesto los retos alcanzados, pero también los objetivos que todavía no se han conseguido.   Finalmente, el último día de este workshop se dedicó, enteramente, a los métodos estadísticos que se han usado por el momento en el campo de la metagenómica. Además de algunas charlas de métodos de aprendizaje automático aplicados a la metagenómica, cabe destacar la charla de S. Holmes, de la Stanford University, en la que también trató cuales son la buenas prácticas de la estadística en bioinformática en general, y metagenómica en particular.

Aunque el workshop finalizó este pasado viernes, ahora quedan unas semanas para la discusión de todos los temas que se han tratado a lo largo de esta semana con el finalidad de obtener algunas conclusion es del trabajo futuro a realizar.mtgw01photo

Este viaje lo hemos hecho Lucia y yo. Además de disfrutar de muchísimas de las charlas y del buen nivel del workshop, también hemos intentado en las tardes-noches disfrutar de la maravillosa ciudad de Cambridge con la visita a algunos colleges, y muy especialmente a la espectacular capilla del King’s College. ¡Una semana francamente interesante!

IMG_8048

¡Las primeras obritas de teatro estadístico, al fin disponibles!

¡Y nosotros sin saberlo! Resulta que ya hace más de un mes que algunas de las obritas de teatro que hemos escrito Patricia Trapero y yo, presentadas entre otros lugares en las JAEM (en castellano) y las JEM (en catalán) del verano pasado, han sido publicadas en formato ebook y se pueden descargar gratis, en catalán y en castellano y con el material complementario, de la página web de Ebooks UIB. Ha sido todo un parto: revisarlas a partir de la experiencia de diferentes representaciones, adaptarlas a ambos idiomas, pasar la revisión lingüística preceptiva, superar problemas técnicos con el formato electrónico… ¡Pero ya están aquí!

JAEMUOM

Mis alumnos de la UOM, representando una de las obras

Por ahora hay cuatro:

  • “Muriel y las ocho tazas de té”, sobre la supuesta capacidad de Muriel Bristol para detectar cómo se ha preparado el té, y cómo Ronald Fisher decidió comprobarlo
  • “El análisis”, típica historieta sobre el teorema de Bayes
  • “El poder de la oración… o no”, sobre la dificultad de diseñar experimentos
  • “Cuando los estadísticos nacen estrellados”, sobre la vida de Chester Bliss, el Frank Spencer de la estadística

y parece que están en la fase final de su periplo previo a publicarse:

  • “Me llamo Francis y soy un adicto”,  monólogos de Francis Galton sobre su adicción a contar (publiqué uno en este blog hace un tiempo)
  • “Pascal Consulting”, adivinad sobre qué.

Las otras dos que presentamos en las JAEM aún tardarán un tiempo, las queremos reescribir completamente.

Números en el fulcro

Una de las últimas incorporaciones a las familias distinguidas de números son los números balanceados (balancing numbers [1]). Se trata de aquellos números naturales tales que la suma de todos los números naturales a su izquierda es igual a la suma de algunos números inmediatamente a su derecha.

bal

Formalmente, n\in \mathbb{N} es balanceado cuando existe algún

r\geq 1 tal que 1+2+\cdots+(n-1)=(n+1)+(n+2)+\cdots +(n+r)

De esta igualdad se deduce que

\displaystyle\frac{n(n-1)}{2}=\frac{r(2n+r+1)}{2}\Longrightarrow \frac{n^2}{2}=\frac{n+2rn+r(r+1)}{2}

y finalmente

\displaystyle{}n^2=\frac{n^2+n+2rn+r(r+1)}{2}=\frac{(n+r)(n+r+1)}{2}

Por lo tanto, y éste es su interés primario, un número n es balanceado cuando es la raíz cuadrada exacta de un número triangular.

Pero a parte de esto, los números balanceados tienen algunas propiedades muy elegantes y relativamente fáciles de demostrar, que los convierten en buenos candidatos para ser protagonistas de problemas sobre combinatoria o inducción.

Por ejemplo, es fácil demostrar  [1] que si denotamos por B_n el n-ésimo número balanceado (siendo los dos primeros B_1=6 y B_2=35, aunque la recurrencia también funciona si aceptamos el 1 como balanceado, y partimos de B_0=1) entonces la sucesión (B_n)_n satisface la ecuación en diferencias

B_{n+2}=6B_{n+1}-B_{n}

de donde se obtiene que

\displaystyle{}B_{n}=\frac{1}{4\sqrt{2}}\left((3+2\sqrt{2})^n-(3-2\sqrt{2})^n\right)

Otras propiedades que se pueden demostrar con facilidad y que son bonitas de proponer como problemas [1,2]:

  • B_{2n}=B_n^2-B_{n-1}^2
  • Si m>n, (B_m+B_n)(B_m-B_n)=B_{m+n}\cdot B_{m-n}
  • B_{\mathrm{mcd}(n,m)}=\mathrm{mcd}(B_n,B_m)

Ah, y antes de que os animéis con un “¿Y si…?”. Ya se han propuesto todo tipo de generalizaciones de los números balanceados, involucrando potencias, progresiones aritméticas, progresiones geométricas,… Buscad en el Google Académico y veréis si vuestra idea ya la ha explotado/publicado alguien.

Esta entrada participa en la edición 5.1, Rey Pastor, del Carnaval de Matemáticas, alojada en el blog Tito Eliatron Dixit.

Referencias

  1. A. Behera, G. K. Panda, “On the square roots of triangular numbers.” The Fibonacci Quarterly 37 (1999), 98-105
  2. G. K. Panda, “Some fascinating properties of balancing numbers”. Fibonacci Numbers and their Applications 10 (2006), edición electrónica