Jun 21

El problema del trigo y del tablero de ajedrez

Granos de trigo en el tablero de ajedrez.

La mayoría hemos oído alguna vez el problema del trigo y del tablero de ajedrez, (o, como nos dice en la wikipedia, expresado en términos de granos de arroz):

 

 

 

“Si se colocase sobre un tablero de ajedrez (lo suficientemente grande) un grano de trigo en el primer casillero, dos en el segundo, cuatro en el tercero y así sucesivamente, doblando la cantidad de granos en cada casilla, ¿cuántos granos de trigo habría en el tablero al final?”

El problema es muy común cuando introducimos las series geométricas en nuestras clases, pues la solución se plantea como una serie geométrica; en concreto:

$$T_{64}=2^{0}+2^{1}+2^{2}+\cdots +2^{63}=\sum _{i=0}^{63}2^{i}$$

La historia de este problema se envuelve en leyenda, y esta está asociada a la leyenda de Sisa. La leyenda nos lleva al noroeste de la India, cómo no, el lugar del nacimiento del ajedrez; pero lo que hoy traigo es el cómo llegó a nosotros. Hilando la madeja de la historia debemos retroceder a la explosión cultural que supuso la Casa de la sabiduría o Casa del saber, donde bajo el auspicio del califa Mamun (reinó entre 813-833), se intentó reunir el saber científico del momento,  atrayendo a Bagdad a multitud de eruditos para compartir información, ideas y cultura. Uno de los propósitos era traducir libros de diferentes idiomas al árabe.

Entre los grandes sabios que trabajaron nos encontramos con el sabeo Thabit ibn Qurrá (826–901), el traductor más renombrado. El legado de Thabit ibn Qurrá siempre se ha centrado en traducción de los trabajos de Euclides, que sirvió a Gerardo de Cremona para mejorar las traducciones que había realizado Adelardo de Bath. Pero en el siglo XIII, Abu-l ‘Abbas Ahmad ibn Khallikan (1211-1282), nos hizo una observación: los sabios de la Casa de la sabiduría estudiaron el problema que abordamos y encontraron la solución. Sería al-Biruni (973-1048) quién calcularía la solución de la increíble suma de la serie geométrica ideada por Thabit ibn Qurrá como solución del problema del trigo y del tablero de ajedrez, llegando a la conclusión que se necesitarían 18.446.744.073.709.551.615 granos.

Hoy encontramos en muchas referencias a Thabit ibn Qurrá como un estudioso de la serie geométrica, pero no suele decirse que fue con el propósito de resolver problema del trigo y del tablero de ajedrez. Lo más probable es que Thabit ibn Qurrá plantease la solución matemática mediante una suma parcial de la serie geométrica, que al-Biruni calculase el resultado, y que ibn Khallikan, como historiador que era, nos lo recordase, para que no olvidemos que si hemos logrado ver más lejos, es porque nos hemos subido a hombros de gigantes.

Este post forma parte del Carnaval de Matemáticas, que en esta octogésima tercera edición, también denominada X.3, está organizado por @Pedrodanielpg a través de su blog A todo Gauss.

Did you like this? Share it:
Posted in Historia, Personajes | Tagged , | Leave a comment
Mar 28

El pequeño teorema de Fermat

La figura de Fermat es recurrente en este blog, y su pequeño teorema ya nos salió. Hoy daremos un poco más de su historia y la demostración. Empecemos.

Como dijimos Fermat enunciaba, en una carta fechada el 18 de octubre de 16 a Frénicle de Bessy, que, si a es un número entero cualquiera y p es un número primo que no es un factor de a, entonces p debe ser un factor del número $a^{p-1}-1$. Y como era habitual en el no presentó la demostración(te enviaría la demostración, si no temiera que fuera demasiado larga, le escribió el muy truhán).

La primera demostración se publicaría en 1736, por Euler, aunque parece ser que Leibniz la conocía ya en 1683.

No conozco la demostración que ofreció Euler(es muy probable que fuese utilizando la función fi de Euler), pero sí esta que es muy sencilla.

 

Este post forma parte del Carnaval de Matemáticas, que en esta octagésima segunda edición, también denominada X.2, está organizado por Rafael Martínez González a través de su blog El mundo de Rafalillo.

Did you like this? Share it:
Posted in Historia, Personajes | Tagged , | Leave a comment
Ene 29

El teorema de Ceva y la ceviana

Ceva's theorem 1.svg

De 4C – Trabajo propio, CC BY-SA 3.0, Enlace

En geometría del triángulo, el teorema de Ceva establece que dado un triángulo ABC, y los puntos D, E, y F que se encuentran sobre los lados BC, CA, y AB respectivamente, los segmentos AD, BE y CF son concurrentes si y solo si
$${\displaystyle {\frac {AF}{FB}}\cdot {\frac {BD}{DC}}\cdot {\frac {CE}{EA}}=1,}$$

El nombre se lo debemos a Giovanni Ceva, que lo demostró en 1678, en su trabajo  De lineis rectis se invicem secantibus statica constructio.

Este resultado también nos ha dado paso a crear el término ceviana.

Lo más probable es que  Giovanni Ceva desconociese que con anterioridad Yusuf Al-Mutamán ibn Hűd lo había mostrado. Del mismo modo que Al-Mutamán lo deduciría del trabajo de  Thabit ibn Qurra, que previamente había tratado el
Teorema de Menelaus (el dual del teorema de Ceva).

Según Agustí Reventós Tarrida[Affine Maps, Euclidean Motions and Quadrics], el término ceviana fue introducido por Auguste Poulain en 1888, pero no indica referencias de ellos, por lo que me decanto a pensar que sería en su trabajo Principes de la nouvelle géométrie du triangle (1892).

Esta entrada participa en la Edición 7.6 del Carnaval de Matemáticas, que en esta ocasión organiza Gaussianos.

Did you like this? Share it:
Posted in Historia, Personajes | Tagged , , , | Leave a comment
Sep 25

Series de primos

La teoría de número tiene un atractivo especial en las matemáticas, y los primos es parte del encanto. Uno de los retos en los que primero cae uno es el de encontrarlos, conseguir una fórmula que nos de todos los primos, o muchos. ¿La habrá?

Sabemos que hay infinitos primos, y que podemos encontrar series con infinitos primos. Por ejemplo, hay infinitos primos de la forma 4n+3, y la demostración resulta instructiva.

Supongamos que me equivoco y el número de primos que se puede poner como $4n+3$ para ciertos $n$ enteros positivos es finito, y que estos primos son $\{p_1,p_2,\ldots,p_k\}$. Ahora construyamos el número $N=(p_1\cdot p_2\cdots p_k)^2+2$. Como cada $p_i=4n_i+3$ para cierto $n_i\in\mathbb{Z}^+$, resulta que $$p_i^2=(4n_i+3)^2\equiv 3^2(mod\, 4)\equiv 1(mod\, 4).$$ En consecuencia $$N=(p_1\cdot p_2\cdots p_k)^2+2\equiv (1+2) (mod\, 4)\equiv 3 (mod\, 4).$$

Es decir, $N$ es un número de la forma $N=4n_\alpha+3$ mayor que todos los $p_i$ y no divisible por ninguno de ellos. Pero $N$ tiene que tener divisores primos, y como no pueden ser los $p_i$ serán otros de la forma $4n+1$. Entonces $$N=q_1\cdot q_2\cdots q_r,$$ con $q_i=4n_i+1$ para todo índice. Lo que me lleva a que $$N\equiv 1 (mod\, 4).$$ una contradicción, pues no puede ser $N\equiv 3 (mod\, 4)$ y $N\equiv 1 (mod\, 4)$ al mismo tiempo. Esta contradicción surge de supone que el número de primos de la forma $4n+3$ es finito.

Como apreciaréis un planteamiento similar a cómo Euclides demostró la infinitud de los números primos.

Pues bien, podemos demostrar de forma similar que el conjunto de primos para ciertos $n$ de la forma $4n+1$, también es infinito. Y los de la forma $6n+1$ ó $6n+5$ ó $8n+1$ ó $8n+3$ ó $8n+5$, y así un no parar. En general lo podemos formular como un teorema, el teorema  de Dirichlet sobre progresiones aritméticas:

Sea $a,\,d\in \mathbb{N}$ tales que el máximo común divisor $(a,d)=1$, entonces la progresión aritmética $a_{n}=a+n\cdot d$ contiene infinitos números primos.

Este resultado que conjeturó Gauss, fue demostrado por Dirichlet en 1837. La demostración se sale de la teoría clásica de números, para adentrarse en la teoría analítica de números. Dirichlet fue un potenciador de esta rama de la teoría de números. A él también debemos, por ejemplo, el Principio del Palomar.

Una consecuencia que obtenemos de este teorema es la respuesta a la pregunta del principio. ¿Podríamos encontrar un polinomio, $P(x)$, con coeficientes enteros que satisfaga $$P(x) \mbox{ es primo} \forall x\in\mathbb{Z}^+?$$

La respuesta es no. Supongamos que sí, que existiese $P(x)$ primo, para todo $x$>0, entonces $P(1)=p$ es primo. Para algún $k>0$, $P(1+k\cdot p)$ será primo  y $P(1+k\cdot p)\equiv P(1) (mod\, p) \equiv 0 (mod\, p)$. Es decir, $P(1+k\cdot p)$ es primo y congruente con 0 modulo $p$, luego $P(1+k\cdot p)=p$ para todo entero $k>0$ anterior. Como el Teorema de Dirichlet nos dice que hay infinitos $k$ que lo cumplen, seguiría que la ecuación $P(x)-p=0$ tiene infinitas soluciones y eso no es posible, un polinomio de grado finito tiene finitas soluciones. Otra contradicción.

Como veis, hay un mundo infinito de contradicciones. Qué pena que no aprendamos de ellas.

Este post forma parte del Carnaval de Matemáticas, que en esta septuagésima novena edición, también denominada 9.3, está organizado por @juanfisicahr a través de su blog Esto no entra en el examen.

Did you like this? Share it:
Posted in Historia, Personajes | Tagged , , | 1 Comment
Ago 05

Euler contra Diderot

El pasado 28 de julio, apareció una entrada de Carlo Frabetti en la sección El Juego de La Ciencia del diario El País, que rezaba el mismo título: Euler contra Diderot. Su lectura es muy instructiva y me llamó la atención el problema que nos deja a los lectores. en determinado momento nos cuenta que Euler le dijo a Diderot: “Mi mujer escribió un número entero de menos de treinta cifras terminado en 2; yo borré el 2 del final y lo puse al principio, y el número resultante era el doble del que había escrito mi mujer. ¿Qué número escribió?”. Ahí arranca un interesante problema de la teoría de números. Independientemente de la originalidad o certeza de este reto, nos plantea un problema que podemos resolver con la herramientas de una teoría de números básica. Veámoslo.

Consideremos que el número que buscamos es $x$. Si lo expresamos en base decimal, será: $$d_n10^n +d_{n-1}10^{n-1}+\ldots+d_110+d_0=x.$$ El enunciado del problema nos dice que $d_0=2$, en consecuencia $x$ es par y se puede poner como $x=2y$. Además, por el enunciado, colocando el 2 en primer lugar (recordemos que seguimos teniendo las mismas $n+1$ cifras), resultará el doble del primero; es decir, $$2\cdot 10^n +d_{n}10^{n-1}+d_{n-1}10^{n-2}+\cdot+d_210+d_1=2x=4y (1)$$

Precisamente el hecho de que las cifras sean las mismas, salvo el orden, juega a nuestro favor. Por la propiedad de la divisibilidad del 3 y las congruencias $$2y=d_n10^n +d_{n-1}10^{n-1}+\ldots+d_110+2\equiv [d_n+d_{n-1}+\ldots+d_1+2](mod\, 3)$$ y $$4y=2\,10^n +d_{n}10^{n-1}+d_{n-1}*10^{n-2}+\ldots+d_210+d_1\equiv [2+d_n+d_{n-1}+…+d_1](mod\, 3).$$ Observemos que ambos términos de la congruencia son el mismo sumando $[d_n+d_{n-1}+\ldots+d_1+2]$, en consecuencia, $$2y\equiv 0(mod\, 3).$$

Ya tenemos la primera pista del número que buscamos: es un múltiplo de 6 que termina en 2.

Esta linea se puede continuar, aunque nos lleva a un camino peligroso. Me explico. Si consideramos el enunciado, $$2\,10^n +d_{n}10^{n-1}+d_{n-1}*10^{n-2}+\ldots+d_210+d_1=2(d_n10^n +d_{n-1}10^{n-1}+\ldots+d_110+2).$$

Si restamos nos dará: $$(2-2d_{n})\,10^n +(d_{n}-2d_{n-1})10^{n-1}+\ldots+(d_2-2d_1)10+(d_1-2d_0)=0$$

Lo que nos permite aventurar que nuestro número termina en 42, aún diría más, en 842, resultado que nos lo enseña la sucesión de diferencias: $d_1-2d_0=0;d_2-2d_1=0$. Sin embargo, debemos llevarnos cuidado, puesto que los números $d_i$ son dígitos entre 0 y 9, y en la siguiente,  $d_3-2d_2=0$, nos crea un problema un poco más difícil de entender, que lo utilizado hasta ahora. Dejemos esta línea, para afrontar otra más productiva y con la misma facilidad de entender. No sin antes, mostrar que si miramos al final de la recursión nos llevaría a $2-2d_{n}=0$, que nos indica que $d_n=1$ y, aún más, $d_{n-1}=0$. Así que esta línea nos da la pista de que el número que buscamos es de la forma: $$10\cdots\cdots\cdots\cdots 842.$$ Curioso, ¿verdad? No sabemos la cantidad de cifras, solo que es menor de 30 (por el enunciado).

Hasta aquí, a mis alumnos de Informática les sugiero que afronten el problema con una solución a fuerza bruta. Si utilizamos R y la librería de grandes enteros gmp, únicamente necesitamos un procedimiento de fuerza bruta que busque múltiplos de 6 que empiecen por 10 y terminen por 842, menores de 30 dígitos. Un problema finito.

Pero Euler no disponía de ordenador (salvo que su celebro fuese uno), con lo cual tenemos que seguir probando con la teoría de números, o en este caso un sencillo proceso de aritmética.  Sabemos (algoritmo de la división) que cualquier entero positivo, y nuestro $x$ en particular, que termine en 2 se puede escribir como: $x=10q+2.$ El enunciado no dice que el doble termina en el penúltimo dígito de $x$, luego $$x=10q+2\to 2x=2(10q+2)$$ Pero también, $$2x=2\cdot 10^{n}+q.$$

Veamos esto con un ejemplo. Supongamos el número $456872$, si quitamos el último 2 y lo pasamos al principio tendremos el $245687$. $456872=10 \cdot 45687+2$ y $245687=2 \cdot 10^{6}+45687$. En nuestro caso el equivalente a $q$ es $45687$.

Por tanto, de $2x=2(10q+2)$ y $2x=2\cdot 10^{n}+q$, obtenemos que $$20q+4=2\cdot 10^{n}+q$$ lo que nos lleva a $$2(10^n-2)=19q$$

Lo hemos escrito así para poder utilizar las propiedades de los números primos. En la ecuación diofántica que tratamos de resolver (como sabemos que tiene solución), es necesario que $19$ divida a $(10^n-2)$, por ser $19$ primo. Así que buscamos un número divisible por $19$ de la forma $(10^n-2)$. Esto es un problema de restos potenciales, estamos buscando resolver la ecuación $$10^a\equiv 2(mod\, 19).$$

De nuevo podemos utilizar R para obtener que el número $a$ que buscamos es $17$; $$10^{17}\equiv 2(mod\, 19).$$

En realidad, $$10^{17m}\equiv 2(mod\, 19),$$ para cualquier natural $m$ valdría, pero el enunciado nos dice que el número en cuestión es menor de 30 digítos, y $10^{17\cdot 2}$ supera los treinta. Por tanto la ecuación $$2(10^n-2)=19q$$ queda como $$2(10^{17}-2)=19q,$$ es $$2\cdot 99999999999999998=19q.$$

Dividiendo por 19 y multiplicando por 2, tendremos $$q=10526315789473684.$$ Pero recordad que el número que buscamos es $x=10q+2$, por tanto $$x=10q+2=105263157894736842.$$ Y ya está. Bonito número, ¿verdad? Observar que cumple las primeras propiedades que observamos: comienza por 10 y termina por 842, además de ser divisible por 6.

Did you like this? Share it:
Posted in Ocio | Leave a comment
May 24

Problème des ménages

Conservando su título original propuesto por el matemático francés François Édouard Anatole Lucas (1842-1891), en Théorie des nombres, Gauthier-Villars, Paris, 1891, el problema pretende contar el número de formas en las que puedes sentar a una mesa redonda $n$ parejas de comensales de forma que no coincida junta una pareja.

Por ejemplo, consideremos 3 parejas, $A_1A_2$, $B_1B_2$ y $C_1C_2$ y las sentamos en una mesa circular de esta forma:

pretendiendo no sentar a nadie al lado de su pareja. La pregunta sería: ¿de cuántas formas podemos sentarlas sin que coincidan  $A_1A_2$ o $B_1B_2$ o $C_1C_2$ al lado?

Un problema equivalente había sido formulado, independientemente, por el matemático escocés Peter Guthrie Tait, que estaba estudiando la teoría de nudos, en On knots, i, ii, iii, in Scientific Papers, pages 273-347. Cambridge Univ. Press, Cambridge, 1898.

La primera fórmula explícita que daba el número fue publicada por el francés Jacques Touchard en 1934,
$$M_{n}=2\cdot n!\sum _{{k=0}}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(n-k)!.$$
Aunque no dio su prueba. Tendríamos que esperar a 1943 para que Kaplansky (Solution of the problème des ménages. Bull. Amer. Math. Soc., 49:784-785) diese una demostración.

A partir de aquí se han obtenido otras fórmulas, como la de Wyman & Moser de 1958(On the problème des ménages, Canadian Journal of Mathematics, 10 (3): 468–480, doi:10.4153/cjm-1958-045-6, MR 0095127).

En Non-sexist solution of the ménage problem, podéis encontrar la de Kenneth P. Bogart and Peter G. Doyle, que lo resuelve utilizando el principio de inclusión-exclusión.

Did you like this? Share it:
Posted in Historia | Leave a comment
May 02

John Graunt y las tablas de mortalidad

Graunt Observations.jpg


De John Grauntexternal free, Dominio público, Enlace

Encontrar el comienzo de una disciplina es agrupar diversos acontecimientos que llevaron al nacimiento formal. La Estadística, como vocablo es posible que surgiese de la palabra alemana statistik, que Godofredo Achenwall introdujo en 1749 para tratar el análisis de datos acerca del estado.

Desde le principio de la escritura hemos compilado datos que podrían considerarse acerca del estado, o al menos, acerca de las necesidades del regidor del momento. Por tanto, estadística se hizo antes de que así lo llamásemos, y se escribió antes de que así lo entendiésemos. Sin embargo, podríamos aventurarnos a fechar el inicio en la publicación del primer tratado que entraría dentro de las publicaciones científicas de estadística, hablo de Natural and Political Observations Made upon the Bills of Mortality (1662) de John Graunt.

En esta obra , John Graunt plasma el trabajo del análisis de los datos de las tasas de mortalidad de Londres en la Inglaterra de Carlos II, intentando con ello avisar de la aparición y propagación de la peste bubónica. Los boletines de mortalidad  (Bills of Mortality) que se publicaban, le sirvieron como base documental para sus investigaciones.

Más información en:

Did you like this? Share it:
Posted in Historia, Personajes | Tagged , | Leave a comment
Dic 09

Un recuerdo para Lotfi A. Zadeh

LotfiZadeh Con unos meses de retraso traemos a pimedios el fallecimiento de Lofti A. Zadeh, padre de la lógica difusa. Famoso por introducir en 1965 la teoría de conjuntos difusos o lógica difusa, una teoría que creo para introducir la incertidumbre de una manera diferente a la planteada por la teoría probabilística existente en la década de los 60. En esta teoría, planteada en el artículo Fuzzy sets. Information and Control. 1965; 8: 338–353, introduce en concepto de conjunto difuso, o borroso, (Fuzzy set), que más tarde T. Takagi y M. Sugeno implementarían para diseñar sistemas de control, que se apellidaron difusos, comienzos de toda la bibliografía sobre modelado para control de procesos.

Veamos un ejemplo de como entender la diferencia entre la probabilidad y la lógica difusa.

Su legado científico es inmenso en todo el mundo y en particular en España, como nos enseña Ramón López de Mántaras, Director del Instituto de Investigación en Inteligencia Artificial del CSIC, en el obituario que escribió el 8 de sep. 2017 en el mundo.

Si queréis saber más sobre este investigador y su trascendente trabajo, el profesor E. Trillas publicó un detallado artículo sobre él y su influencia en Lotfi A. Zadeh: On the man and his work.

Esta entrada participa en la edición 8.6 del Carnaval Matemático, cuyo anfitrión es, en esta ocasión, Matemático Soriano.

Did you like this? Share it:
Posted in Actualidad, Historia, Personajes | Tagged , , , | Leave a comment
Oct 13

La serie de Brook Taylor

Taylor - Methodus incrementorum directa et inversa, 1715 - 811460.tif

De Taylor, Brook – Este archivo está disponible en biblioteca digital BEIC y fue subido como parte de la sociedad con BEIC., Dominio público, Enlace

Leo la entrada de Café y Teoremas y no puedo dejar de sonreír: “La llamada serie de Taylor no es tan mediática como Juego de Tronos, pero resulta fundamental en el cálculo matemático y, con ello, en el resto de ciencias e ingeniería.” Y tiene mucha razón. Las series matemáticas nacieron mucho antes que las series televisiva, aunque la trascendencia de la últimas supere exponencialmente a las primeras.

Las serie de Taylor es una suma infinita de potencias enteras de polinomios que permiten aproximar funciones más complejas. Y esta fue publicada por primera vez en el trabajo Methodus incrementorum directa et inversa de 1715 de Brook Taylor, el músico, pintor, jurista y gran matemático al que Pedro Tradacete dedica su entrada en Café y Teoremas: Brook Taylor.

Como muchos logros del XVIII, no fue el único en visualizar este tipo de series. En el siglo anterior James Gregory publicó varias series que se deducen de esta. Y años después, otro escocés, trabajaría con las series de Taylor en un trabajo de 1742, Treatise of fluxions, donde introduce la llamada serie de Maclaurin, que permite evaluar funciones. Newton y Leibniz también trabajaron con la serie de Taylor, y es posible que Taylor la aprendiese de los trabajos de Newton, pero fue Brook Taylor quien primero trabajó con ella como función y enseñó el camino. Aunque no sería hasta 1772 cuando Lagrange incidió en su importancia.

Algo si hay en común en las dos series: Juego de Tronos y la serie de Taylor, ambas han hecho historia.

Did you like this? Share it:
Posted in Historia | Tagged | Leave a comment