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.

 

Los números Le Monde-959 (por llamarlos de alguna manera)

Va, algo de precalentamiento: ¿qué números son iguales a la suma de las potencias n-ésimas (n\geq 2) de sus dos divisores más pequeños (incluyendo 1 como divisor)? Pensadlo un rato. Ah, ¿que estáis aquí para leer, no para pensar? Vaaaaale, veamos. Si N es impar, sus dos divisores menores serán 1 y un primo impar p, pero entonces N (impar) no puede ser igual a 1+p^n (par); y si N es par, sus dos divisores menores serán 1 y 2, pero entonces N (par) no puede ser igual a 1+2^n (impar).

Hechos los estiramientos, vamos al grano. En su blog, Xian (alias de Christian Robert, pero le seguiremos llamando Xian, si es lo que quiere) de vez en cuando resuelve “por fuerza bruta” problemas propuestos en Le Monde; con “por fuerza bruta” quiero decir usando un programa de R. Son unas entradas muy interesantes, porque siempre aprendo una función o un truco nuevos. En la entrada del pasado miércoles 20 de abril, Xian atacaba el problema 959, del fin de semana pasado:

Encuentra un natural A que sea igual a la suma de los cuadrados de sus cuatro divisores más pequeños (incluyendo el 1), y un natural B que sea igual a la suma de los cubos de sus cuatro divisores más pequeños. ¿Hay enteros con esta propiedad para exponentes más grandes?

Con lo que nos gusta poner nombres a los objetos, a un número con esta propiedad para un exponente n lo voy a llamar un número Le Monde-959-n. Por ejemplo, Xian encuentra un número Le Monde-959-2 (es decir, un número que es suma de los cuadrados de sus cuatro primeros divisores): 130. En efecto: 130=2\times 5\times 13 y 130=1+2^2+5^2+10^2. También encuentra un número Le Monde-959-5 (que es suma de las potencias quintas de sus cuatro primeros divisores): 17864 (podéis comprobarlo, pero en un rato lo volveremos a encontrar). Y en la solución que publicó ayer Le Monde (y que acaba de añadir Xian a su entrada)  Le Monde afirma que no hay ningún número Le Monde-959-3, y dan un número Le Monde-959-4, 1419874, y otro número Le Monde-959-5, 1015690. Como el programa de Xian es solo una prueba de concepto, solo busca hasta 10^6, por lo que no encuentra el primero. Por lo que refiere al segundo… no es suma de las potencias quintas de sus cuatro primeros divisores: 1015690=2\times 5\times 13^2\times 601 \neq 1+2^5+5^5+10^5.

Naturalmente, uno se puede preguntar si hay más números con esta propiedad. La base de la cacería será la siguiente. Si N fuera un número Le Monde-959-n impar, sus cuatro primeros divisores serían impares y por lo tanto la suma de sus potencias sería par, por lo que no podría ser igual a N. Así pues, todo número Le Monde-959-es par y sus dos primeros divisores serán 1 y 2. Ahora bien, como 1+2^n es impar, para que la suma de las potencias de los cuatro divisores más pequeños sea par, el tercer y el cuarto han de ser de paridades diferentes. La conclusión es que los números Le Monde-959-solo pueden tener una de las dor formas posibles, para algún primo impar p:

A_{n,p}=1+2^n+4^n+p^n o B_{n,p}=1+2^n+p^n+(2p)^n=(1+2^n)(1+p^n)

Esto nos permite buscarlos. Por ejemplo, para n=2, ha de pasar:

  • Si es del tipo A_{n,p}, p ha de dividir a 1+2^2+4^2=21, por lo que p=3 o p=7, y 4 ha de dividir a 1+p^n, que no pasa para ninguno de los dos.
  • Si es del tipo B_{n,p}, p ha de dividir a 1+2^2=5, es decir, p=5 y obtenemos el 130.

Así pues, el único número Le Monde-959-2 es 130. Bien. En general, no hay soluciones del tipo A_{n,p} con n par, porque en este caso 4 nunca divide a 1+2^n+4^n+p^n.

Qué pasa con n=3? Repetimos razonamiento:

  • Si es del tipo A_{n,p}, p ha de dividir a 1+2^3+4^3=73, por lo que p=73, pero entonces 1+2^3+4^3+73^3=389090 no es es divisible por 4
  • Si es del tipo B_{n,p},  p ha de dividir a 1+2^3=9, es decir, p=3, pero entonces 1+2^3+3^3+6^3=252 es divisible por 4, por lo que 6 no es uno de sus cuatro divisores más pequeños.

Así pues, no hay números Le Monde-959-3. Seguimos coincidiendo.

Otro más, y luego ya os dejo con resultados generales. ¿n=4? Ya sabemos que no hay soluciones de la forma A_{n,p}. En una solución del tipo B_{n,p}, p ha de dividir a 1+2^4=17, es decir, p=17, y resulta que 1+2^4+17^4+34^4=1419874=2\times 17\times 41761, por lo que 1419874 es el único número Le Monde-959-4.

Y en general? Vale, os dejo como ejercicio sencillo los tres resultados siguientes:

  1. Si n=4m+2, entonces los números B_{n,5}=1+2^n+5^n+10^n son siempre Le Monde-959-n. Cuando m=0, B_{2,5}=130, cuando m=1, B_{6,5}=1015690 = 2\times 5\times 13^2\times 601. La demostración general (que 3, 4 y 7 no dividen a B_{n,5} y 5 sí) es sencilla.
  2. Si n=4m con m impar (es decir, n=8k+4), entonces los números  B_{n,17}=1+2^n+17^n+34^n son siempre Le Monde-959-n. Cuando m=1, B_{4,17}=1419874, dado por Le Monde; cuando m=3, B_{12,17}=2387003305930334914 = 2\times 17\times 73\times 241\times 1321\times 41761\times 72337 . De nuevo, la demostración general (que 3, 4, 5, 7, 11,  13, 19, 23, 29, 31 no dividen a B_{n,17} y 17 sí) es sencilla, pero algo larga a mano.
  3. Si n es impar pero no múltiplo de 3, entonces A_{n,7}=1+2^n+4^n+7^n son siempre Le Monde-959-n.  Cuando n=5, A_{5,7}=17864, el que encontró Xian; cuando n=7, B_{7,7}=840056 = 2^3\times 7^2\times 2143. La demostración general (que 3 y 5 no dividen a A_{n,7} y 4 y 7 sí) también es sencilla y esta vez corta.

Qué pasa con los otros exponentes? Ya hemos visto que no hay números Le Monde-959-3, y un argumento similar muestra que tampoco hay números Le Monde-959-9. No he sabido demostrar que, en general, no hay números Le Monde-959-con n múltiplo impar de 3, pero tiene toda la pinta (va, conjetura).

¿Y los números Le Monde-959-con n múltiplo de 8? Para n=8 no existe ninguno: 1+2^8=257 es primo y B_{8,257} no funciona; para n=16 sí que existe uno: B_{16,65537}, que no copio aquí porque es un monstruo; para n=24 no existe ninguno; para n=32, existe uno: B_{32,641}; para n=40 no existe ninguno; para n=48, existe uno: B_{32,257}. La pauta es clara, pero tampoco lo he sabido demostrar.

En general, podríamos preguntar

¿Para qué números naturales k\geq 3 y n\geq 4 existen números naturales N que son iguales a la suma de las potencias n-ésimas de sus primeros k divisores?

Para k=3 es fácil (para n par, nunca; para n impar, 1^n+2^n+3^n siempre; ejercicio). El resto, lo dejo para algún fan del Problema de Waring.

Vaya, se me ha terminado la entrada y no hay ninguna imagen. Va, unos gatitos para alegraros el dia

kittens

Y, siempre con el tiempo justo, esta entrada participa en la Edición 7.3 del Carnaval de Matemáticas, cuyo anfitrión es pimedios.

 

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.