Gaussianos » Curiosidades

Los puentes de Königsberg: el comienzo de la teoría de grafos

Comenzamos esta semana con una entrada dedicada a un problema clásico pero no por ello falto de interés: los puentes de Königsberg. Clásico porque es un problema muy conocido y estudiado; interesante porque está considerado como el comienzo de la topología, y, en particular, de la teoría de grafos.

El artículo consta de cuatro partes: descripción del problema y encuadre histórico del mismo, iniciación a la teoría de grafos, resolución del problema y aplicación a la resolución del problema del sobre y similares.

Los puentes de Königsberg

Königsberg (actualmente Kaliningrado, Rusia) era una ciudad de Prusia del siglo XVIII. El problema que nos ocupa tiene como protagonista a un río, el río Pregel, que cruzaba la ciudad, a dos islas que se encontraban en el mismo y a siete puentes que comunicaban las dos partes de la ciudad con las mismas. Concretamente la situación era como se describe en la imagen ( $A$ y $B$ son las dos partes de la ciudad y $C$ y $D$ las dos islas):

Königsberg y sus puentes

(Imagen tomada de Historias de la Ciencia)

El problema consistía en comenzar en un punto, pasar por los siete puentes sin repetir ninguno y volver al punto de partida. Antes de seguir leyendo podéis intentarlo vosotros mismos, aunque os recomiendo que no le dediquéis demasiado tiempo.

Iniciación a la teoría de grafos

Un grafo es básicamente un conjunto no vacío (al menos contiene un elemento) de puntos llamados vértices y un conjunto de líneas llamadas aristas cada una de las cuales une dos vértices. Se llama lazo a una arista que une un vértice consigo mismo. Se dice que dos vértices son adyacentes si existe una arista que los une.

Se dice que un grafo es simple si para cualesquiera dos vértices existe a lo sumo una arista que los une. En otro caso se denomina multigrafo.

Si $v$ es un vértice de un grafo, se denomina grado de $v$ al número de aristas que inciden en el mismo (por convenio de considera que un lazo cuenta dos veces al determinar el grado de su vértice).

Se dice que un grafo es conexo si no puede expresarse como la unión de dos grafos de vértices disjuntos. Os dejo un ejemplo:

Grafo conexo y grafo no conexo

Un camino de longitud n es una sucesión de vértices, $v_i$ , y aristas, $a_j$ , de la siguiente forma: $v_0,a_1,v_1, \ldots ,v_{n-1},a_n,v_n$ . Se dice que un camino es cerrado si $v_n=v_0$ , es decir, el vértice inicial y el final son el mismo. Se dice que es simple si todas sus aristas son distintas. Se llama trayectoria a un camino simple en el que todos sus vértices (salvo probablemente el inicial y el final) son distintos y se denomina circuito a una trayectoria cerrada con al menos una arista.

Se llama camino euleriano a un camino simple que contiene todas las aristas del grafo y se denomina circuito euleriano a un camino euleriano cerrado. Se dice que un grafo es euleriano si contiene un circuito euleriano.

Resolución del problema

Para empezar, ¿quién resolvió el problema? Pues como ya sabéis los que conocíais el problema y como habréis intuido los que no lo conocíais fue Leonhard Euler quien dio solución a este asunto. La idea genial de Euler fue representar la ciudad de Königsberg como un grafo en el que las cuatro partes de la misma eran los vértices y los siete puentes eran las aristas:

Königsberg representada por un grafo

Por tanto el problema de los puentes de Königsberg pasa a ser un problema de teoría de grafos cuya solución publicó Euler en su artículo Solución de un problema relativo a la geometría de posición.

Según las definiciones que hemos visto en el punto anterior lo que queremos saber es si este grafo en euleriano, es decir, si contiene un circuito euleriano (es decir, un camino que contiene a todas las aristas del grafo sin que ninguna se repita y que comienza y termina en el mismo vértice). Vamos a demostrar el siguiente resultado:

Teorema:

Un grafo $G$ es euleriano y sin vértices aislados $\Leftrightarrow$ $G$ es conexo y el grado de todos sus vértices es par.

Demostración:

$\Rightarrow )$ Si $G$ es euleriano entonces contiene un circuito euleriano y como no tiene vértices aislados entonces cualquier par de vértice $u$ y $v$ están conectados por la parte del circuito que va de $u$ a $v$ . Por tanto $G$ es conexo.

Por otra parte, como $G$ es euleriano contiene un circuito euleriano, es decir, un camino simple y cerrado que contiene a todas las aristas. Por tanto por cada arista que llegue a un vértice debe haber otra que salga del mismo y en consecuencia el grado de cada vértice es un número par.

$\Leftarrow )$ Partimos de que $G$ es conexo y todos sus vértices tienen grado par.

Si el número de aristas de $G$ es 1 ó 2 el resultado es inmediato. Procedemos por inducción: supongamos que $G$ tiene $n$ aristas y que el resultado es cierto para los grafos que cumplan las condiciones y tengan menos de $n$ aristas.

Usando que todo grafo en el que todos sus vértices tienen grado mayor o igual que dos posee un circuito (¿por qué?) tenemos que el nuestro contiene un circuito, dikgamos $C$ . Si $C$ contiene todas las aristas de $G$ , entonces $C$ es un circuito euleriano y hemos terminado. En caso contrario sea $G_1$ el grafo obtenido al suprimir de $G$ las aristas de $C$ y suprimir después los vértices que han quedado aislados. Puede que el grafo haya quedado dividido en subgrafos no conectados entre sí; cada uno de ellos es una componente conexa de $G_1$ .

Por haber eliminado las aristas de un circuito todos los vértices de $G_1$ tiene grado par. Por la hipótesis de inducción, cada componente conexa $G_{1i}$ de $G_1$ contiene un circuito euleriano.

Como en cada componente conexa $G_{1i}$ debe haber al menos un vértice $v_i$ de $C$ podemos obtener un circuito euleriano en $G$ (que es lo que queríamos conseguir) del siguiente modo:

Partimos de un vértice cualquiera de $C$ (que recordemos que no era un circuito euleriano). Recorremos $C$ hasta llegar a un vértice $v_i$ de una componente conexa $G_{1i}$ de $G$ . Recorremos esta componente conexa a través del circuito euleriano que hemos visto que debe contener y continuamos recorriendo $C$ hasta que nos encontremos con un vértice de otra de las componentes conexas, realizando entonces la misma operación. Repetimos el procedimiento hasta llegar al vértice de partida, obteniendo así un circuito euleriano.

c.q.d.

Observemos ahora el grafo que habíamos obtenido de la ciudad de Königsberg y calculemos el grado de todos sus vértices. Hay tres vértices con grado $3$ y un vértice con grado $5$ . Es decir, no hay ninguno con grado par. Por tanto, según el teorema anterior, este grafo no contiene un circuito euleriano, esto es, no podemos comenzar en un punto de la ciudad y recorrer cada uno de los puentes sólo una vez y terminar en el punto de partida.

El problema del sobre y similares

Supongo que muchos de vosotros os habréis encontrado con el típico problema de recorrer todos los segmentos de un dibujo sólo una vez sin levantar el lápiz del papel. En esos problemas los vértices inicial y final no tiene que ser el mismo, es decir, puedo comenzar en el vértice que quiera y terminar en ese mismo o en cualquier otro, pero debo pasar por todas las líneas una y sólo una vez sin levantarme del papel. El más típico es el sobre:

Sobre cerrado

El siguiente resultado es un corolario del teorema anterior y nos ayudará a analizar todos estos problemas:

Corolario:

Un grafo $G$ contiene un camino euleriano $\Leftrightarrow$ $G$ es conexo y tiene como máximo dos vértices de grado impar.

La demostración os la dejo a vosotros para que la penséis.

Un camino euleriano es precisamente lo que buscamos cuando queremos resolver estos problemas. Por tanto lo único que tenemos que hacer es calcular el grado de cada vértice. Si tenemos más de dos vértices de grado impar el recorrido no será posible; por el contrario, si tiene sólo dos vértices o ningún vértice con grado impar entonces sí se podrá recorrer de esa forma (no puede haber sólo un vértice con grado impar ya que el número de vértices de grado impar es par, ¿por qué?). En el caso de nuestro sobre tenemos cuatro vértices con grado impar y por tanto no podremos recorrer todas las aristas sólo una vez sin levantar el lápiz del papel.

Por contra, si tenemos el sobre abierto:

Sobre abierto

sí podremos recorrerlo así ya que ahora sólo hay dos vértices con grado impar, los dos de abajo. De hecho se sabe que para recorrer todas las aristas sólo una vez sin levantar el lápiz del papel debemos comenzar en uno de los vértices de grado impar y terminar en el otro.

Con estos resultados ya no habrá problema de este tipo que se os resista.

Escrito por ^DiAmOnD^, 5 de Mayo de 2008 en Curiosidades, Topología
10 comentarios

Composiciones de números y números de Fibonacci

Vamos a comentar una propiedad curiosa que me mandó fede por mail hace tiempo:

Podemos expresar un número, por ejemplo el $3$ , como suma de números de varias formas diferentes:
$3=1+1+1,3=2+1,3=1+2,3=3$
(admitimos sumas con un solo sumando).

Una de estas sumas se llama partición del número si consideramos que el orden de los sumandos no importa. La suma se llama composición cuando el orden de los sumandos importa. Según ésto el número de particiones de $3$ es 3 y el número de composiciones de $3$ es 4. En general, el número de composiciones de $N$ es $2^{N-1}$ .

Las teoría de particiones (de números) es una famosa rama de la combinatoria y de la teoría de números. Las composiciones no tienen tanta fama (no parece que haya tanto que decir de ellas), pero tenemos el siguiente resultado curioso:

Si multiplicamos los sumandos de cada composición de un número $N$ y sumamos todos los productos, el resultado es el $2 \cdot N$ -ésimo número de la sucesión de Fibonacci $F(N)$ ( $N=1,1,2,3,5,8,13 \ldots$ ). Por ejemplo, para $N=3$ tenemos que $1 \cdot 1 \cdot 1 + 1 \cdot 2 + 2 \cdot 1 + 3 = 8$ , que es igual a $F(2 \cdot 3)=F(6)$ .

Curiosa e interesante propiedad de las composiciones de números y los números de Fibonacci. Os dejo un par de enlaces con otras curiosidades de estos números publicadas ya en Gaussianos:

Escrito por ^DiAmOnD^, 2 de Mayo de 2008 en Curiosidades, Números enteros
3 comentarios

Yin-yang matemático

El otro día Hugo, de Sólo otro blog infame, me mandó la siguiente imagen, que encontró aquí, que me ha parecido muy curiosa:

Yin-yang matemático

He intentado representar la situación con el programa Mathematica 5.0 pero no he sido capaz. No encuentro ni siquiera la manera de que me resuelva la inecuación y por tanto mucho menos de que me represente los puntos que la cumplen. A ver si alguien sabe cómo hacerlo con ese programa.

Escrito por ^DiAmOnD^, 14 de Abril de 2008 en Curiosidades
12 comentarios

Número normal

Como en algunos comentarios en ciertos artículos (por ejemplo, en algunos de números irracionales cebra) vi que no estaba demasiado claro qué era un número normal voy a intentar explicarlo en esta entrada.

Un número normal es un número real cuyos dígitos, en cualquier base, siguen una distribución uniforme, esto es, todos los dígitos son igualmente probables, todas las parejas de dígitos son igualmente probables, todas las ternas son igualmente probables…Cuando queremos referirnos a una base concreta $b$ diremos que el número es cuestión es normal en base $b$ . El concepto de número normal fue introducido por Émile Borel en 1909.

A la vista de esta definición podemos sacar varias cosas:

1.- En un número normal podemos encontrar todos los patrones posibles entre números; por ejemplo, si nos ceñimos a base 10, un número normal en base 10 contendrá en algún lugar de su expansión decimal a cualquier número natural que podamos pensar.
2.- Todo número normal debe ser necesariamente irracional, ya que si un número es racional tendrá un período y eso impide que haya equiprobabilidad.
3.- No todo número irracional es normal, ya que hay números irracionales en los cuales no aparece cualquier patrón de número naturales. Por ejemplo, la constante de Liouville

$\displaystyle{\sum_{j=1}^\infty 10^{-j!} = 0.110001000000000000000001000 \ldots}$

es un número irracional pero, evidentemente, no presenta todos los patrones posibles.

Después de la definición y de las observaciones iniciales viene la pregunta: ¿existen números normales? Y en ese caso, ¿cuántos hay? Vamos con las respuestas:

Sí, existen números normales. De hecho, casi todos los números reales son normales. El casi todos significa que el conjunto de los números reales no normales tiene medida de Lebesgue cero. Este resultado también fue demostrado por Borel, aunque su demostración es no constructiva. Fue Waclaw Sierpinski quien dio el primer ejemplo de número normal (no he podido encontrar de qué número se trata; si alguien lo sabe que lo comente). Por tanto hay muchísimos números normales. Sería lógico pensar entonces que es sencillo encontrarlos…nada más lejos de la realidad. Se conocen algunos, de otros se conjetura que lo son, hay más conjeturas sobre ellos, pero ni mucho menos es sencillo comprobar que un número irracional es o no es normal.

Vamos con un par de números de los que se conoce su normalidad:

1.- El número de Champernowne: $0,1234567891011121314151617181920212223 \ldots$

Este número se obtiene concatenando todos los números naturales. Se sabe que es normal en base 10, pero no se sabe si lo es o no en otras bases.

2.- La constante de Copeland-Ërdos: $0,23571113171923 \ldots$

Este número se obtiene concatenando todos los números primos en base 10. En 1945 Copeland y Ërdos demostraron que este número es normal en todas las bases.

3.- La constante de Chaitin $\Omega$ : que es la probabilidad de que un programa elegido al azar detenga correctamente a una maquina de Turing determinada.

Podemos definirlo también de la siguiente forma:

Sea $P$ el conjunto de todos los programas que se detienen y sea $|p|$ el tamaño en bits de un programa $p$ . Entonces:

$\displaystyle{\Omega = \sum_{p \in P} 2^{-|p|}}$

No podemos determinar todos sus dígitos ya que es un número no computable. Pero sabemos que los primeros dígitos de su expresión en base 10 son:

$\Omega=0,0078749969978123844 \ldots$

Uno de los temas más interesante sobre los números normales es si ciertas constantes famosas como $\pi,e,\sqrt{2}$ ó $ln(2)$ son números normales. Aunque se cree firmemente que lo son todavía no se ha podido demostrar ni refutar este hecho.

También existe, como en todos estos temas, una conjetura que de ser cierta sería un resultado ciertamente fuerte. EN este caso es la siguiente:

Todo número irracional algebraico es normal.

No se ha podido encontrar ningún contraejemplo de esta sentencia, pero tampoco se conoce ningún número irracional algebraico que sea normal. Si esta conjetura fuera cierta tendríamos de añadido que $\sqrt{2}$ es normal, al ser un número irracional algebraico.

Y para terminar os dejo un resultado sobre números normales relacionado con el análisis matemático:

Un número $x$ es normal en base $b$ si y sólo si

$\displaystyle{\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{k=0}^{n-1}e^{2 \pi i m b^k x}=0}$ , $\forall m\in\mathbb{Z}$ , $m\geq1$

Fuentes:

Normal number en la Wikipedia (inglés)
Las matemáticas de Oz, de Clifford A. Pickover
Constante de Chaitin en la Wikipedia (español)

Escrito por ^DiAmOnD^, 17 de Marzo de 2008 en Curiosidades, Pi
11 comentarios

Números irracionales cebra

Los números irracionales son los números reales que no pueden expresarse en forma de fracción. Por tanto estos números tienen infinitos decimales en los cuales no hay un patrón que se repita indefinidamente. A partir de esta definición uno podría pensar que por norma general un número irracional no presentaría patrones de tipo racional en sus, digamos, cien primeros dígitos. Si consideráramos esos supuestos patrones como rayas los números irracionales que tuvieran esa propiedad serían los que denominaríamos números irracionales cebra.

Pues los hay, claro que sí. Vamos a ver algunos de ellos:

$\sqrt[3]{\cfrac{7^3 \cdot 10^{51} +7^5}{11^3}}$

cuyo desarrollo es el siguiente:

$\begin{matrix} 63636363636363636, \\ 36363636363636363636363636363636 \\ 46 \\ 757575757575757575757575757575757575757575757575 \\ 587 \\ 80808080808080808080808080808080808080808080808 \\ 5429534231200897867564534231200897867564534231200746900086045641 \ldots \end{matrix}$

y continúa sin presentar ningún otro patrón más en los siguientes dígitos.

$\sqrt{\cfrac{9}{169} \cdot 100^{199} + \cfrac{38 - 17 \cdot 199}{169}}$

en cuyo desarrollo se repiten los patrones $230769$ , $410256$ , $213675$ , $296$ , $590693257359924026$ y $914529$ . Como el plugin de $\LaTeX$ no lo coge entero os dejo parte del número:

23076923076923076923076923076923076923076923076923076923076923076923076923076\
923076923076923076923076923076923076923076923076923076923076923076923076923076\
92307692307692307692307692307692307692307692,3076923076923076923076923076923076\
923076923076923076923076923076923076923076923076923076923076923076923076923076\
923076923076923076923076923076923076923076923076923076923076923076923076923076\
923076880192307692307692307692307692307692307692307692307692307692307692307692\
307692307692307692307692307692307692307692307692307692307692307692307692307692\
307692307692307692307692307692307692307692307692307692307692307692307692307692\
307692307692307692307692307692307692307692307692307692307692307692307692307692\
307692307692307692307692307692307692307692307692307692307692307692307692307692\
307692307692267845352564102564102564102564102564102564102564102564102564102564\
102564102564102564102564102564102564102564102564102564102564102564102564102564\
102564102564102564102564102564102564102564102564102564102564102564102564102564\
102564102564102564102564102564102564102564102564102564102564102564102564102564\
102564102564102564102564102564102564102564102564102564102564102564102564102564\
102564102564102564028515177617521367521367521367521367521367521367521367521367\
521367521367521367521367521367521367521367521367521367521367521367521367521367\
521367521367521367521367521367521367521367521367521367521367521367521367521367\
521367521367521367521367521367521367521367521367521367521367521367521367521367\
521367521367521367521367521367521367521367521367521367521367521367521367521367\
521367521367521367521367349358039460358796296296296296296296296296296296296296\
296296296296296296296296296296296296296296296296296296296296296296296296296296\
296296296296296296296296296296296296296296296296296296296296296296296296296296\
296296296296296296296296296296296296296296296296296296296296296296296296296296\
296296296296296296296296296296296296296296296296296296296296296296296296296296\
296296296296296296296296296295848784960867828340159069325735992402659069325735\
992402659069325735992402659069325735992402659069325735992402659069325735992402\
659069325735992402659069325735992402659069325735992402659069325735992402659069\
325735992402659069325735992402659069325735992402659069325735992402659069325735\
992402659069325735992402659069325735992402659069325735992402659069325735992402\
659069325735992402659069325735992401411631478229137974926549145299145299145299\
145299145299145299145299145299145299145299145299145299145299145299145299145299\
145299145299145299145299145299145299145299145299145299145299145299145299145299\
145299145299145299145299145299145299145299145299145299145299145299145299145299\
145299145299145299145299145299145299145299145299145299145299145299145299145299\
145299145299145299145299145299145299145295502483621567819214350213427904400126\
622348844571066793289015511237733459955682177904400126622348844571066793289015\
511237733459955682177904400126622348844571066793289015511237733459955682177904\
400126622348844571066793289015511237733459955682177904400126622348844571066793\
289015511237733459955682177904400126622348844571066793289015511237733459955682\
177904400126622348844571066793289015511237733448955138216136572710142188954230\
060277513981217684921388625092328796032499736203439907143610847314551018254721\
958425662129365833069536773240476944180647884351588055291758995462699166402870\
106573810277513981217684921388625092328796032499736203439907143610847314551018\
254721958425662129365833069536773240476944180647884351588055291758995462699166\
402870106573810277513981217684921388625092328796032465665074224987344807026819\
335100970652266305558486628445476182101696504988686058644906381531895…

Otro irracional cebra es el siguiente:

$\sqrt{\cfrac{9}{64} \cdot 100^(155)+\cfrac{92-22 \cdot 155}{64}}$

en cuyo desarrollo podemos ver repeticiones de $9$ , $6$ , $2$ , $1481$ y $209876543$ entre otros. Éste tampoco lo coge entero el plugin de $\LaTeX$ . Os dejo parte del número:

37499999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999999999\
9,99999999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999999308\
749999999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999999999999\
999999999999999999999999999999999999999999999999999999999999999999999993628979\
166666666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666666666666666\
666666666666666666666666666666666666666666666666666666666666666666549227515972\
222222222222222222222222222222222222222222222222222222222222222222222222222222\
222222222222222222222222222222222222222222222222222222222222222222222222222222\
222222222222222222222222222222222222222222222222222222222222222222222222222222\
222222222222222222222222222222222222222222222222222222222222219516228458304398\
148148148148148148148148148148148148148148148148148148148148148148148148148148\
148148148148148148148148148148148148148148148148148148148148148148148148148148\
148148148148148148148148148148148148148148148148148148148148148148148148148148\
148148148148148148148148148148148148148148148148148148148078315469080642168209\
876543209876543209876543209876543209876543209876543209876543209876543209876543\
209876543209876543209876543209876543209876543209876543209876543209876543209876\
543209876543209876543209876543209876543209876543209876543209876543209876543209\
876543209876543209876543209876543209876543209876543207945669633660002864583333\
333333333333333333333333333333333333333333333333333333333333333333333333333333\
333333333333333333333333333333333333333333333333333333333333333333333333333333\
333333333333333333333333333333333333333333333333333333333333333333333333333333\
333333333333333333333333333333333333333333333333277402362075594214664673353909\
465020576131687242798353909465020576131687242798353909465020576131687242798353\
909465020576131687242798353909465020576131687242798353909465020576131687242798\
353909465020576131687242798353909465020576131687242798353909465020576131687242\
798353909465020576131687242798353909465020574456321607915493392344201442472565\
157750342935528120713305898491083676268861454046639231824417009602194787379972\
565157750342935528120713305898491083676268861454046639231824417009602194787379\
972565157750342935528120713305898491083676268861454046639231824417009602194787\
379972565157750342935528120713305898491032205313523108387418797769921815462581\
92348727328151196463953665599756134735558603871361073007…

Y los que a mí me parecen más sorprendentes, los generados por la siguiente fórmula:

$f(n)= \sqrt{\cfrac{9}{121} \cdot 100^n+\cfrac{112-44 \cdot n}{121}}$

Por ejemplo, $f(30)$ es así en sus primeras cifras:

$\begin{matrix} 272727272727272727272727272727, \\ 2727272727272727272727272727 \\ 08 \\ 969696969696969696969696969696969696969696969696969696969 \\ 08 \\ 280134 \\ 680134680134680134680134680134680134680134680134 \\ 676012928095772 \ldots \end{matrix}$

Aumentando el valor de $n$ encontramos números cada vez más increíbles.

Os animo desde aquí a que intentéis encontrar números irracionales cebra distintos a éstos. Y si puede ser alguna fórmula para generarlos como la anterior mucho mejor.

Fuente: Las Matemáticas de Oz, de Clifford A. Pickover

Escrito por ^DiAmOnD^, 3 de Marzo de 2008 en Curiosidades
35 comentarios

La paradoja de Smale o cómo evertir una esfera

La topología diferencial es una rama de las Matemáticas complicada pero muy interesante. Probablemente la principal razón por lo que es complicada es porque trata temas poco intuitivos, difíciles de ver. Y bajo mi punto de vista puede llegar a ser interesante precisamente por la misma razón: nos demuestra que ciertas cosas que en principio creeríamos imposibles son matemáticamente ciertas.

El artículo que nos ocupa trata precisamente de uno de estos temas: la paradoja de Smale. Esta paradoja dice algo así:

Es posible evertir (dar la vuelta a) una esfera homeomorfa a $\mathbb{S}^2$ (es decir, una esfera en tres dimensiones, la de toda la vida) sin romperla. Es decir, partiendo de una esfera es posible transformarla en otra que cumple que la parte interior del borde de la primera es la exterior de la segunda, y viceversa, sin necesidad de efectuar ningún corte en la superficie de la misma.

Vamos, que podemos darle la vuelta a la superficie de una esfera sin tener que romperla.

Sorprendente, ¿no? Uno intenta pensar cómo puede ser el tema y no ve manera de hacerlo sin hacer algún corte. Como dije antes, no es nada intuitivo el asunto. Esa es la razón por la que se le llama paradoja: aun cuando físicamente parece imposible matemáticamente sí es posible.

Hemos dicho que no podemos cortar la esfera, pero sí podemos estirarla todo lo que queramos y además se permite que la esfera se interseque a sí misma. Teniendo en cuenta esto la primera opción que se nos podría ocurrir es empujar el hemisferio sur de la esfera hacia arriba para que atraviese el hemisferio norte, quedando entonces del revés. Pero esto no soluciona el tema, ya que la cosa quedaría más o menos así:

Intento de eversión

Como vemos no queda como nosotros queríamos. Obtenemos un saliente en el ecuador de la esfera que es imposible eliminar sin cortar la misma. Intento fallido.

Bueno, entonces…¿cómo se hace? Pues esta es una solución:

Impresionante, ¿verdad? Yo me quede boquiabierto la primera vez que vi este vídeo.

Bueno, ¿y a quién se le ocurrió todo esto? Pues la primera persona que consiguió demostrar que se puede evertir una esfera fue Steve Smale en su tesis doctoral en 1957 El problema de su demostración (como de muchas otras) es que sólo era de existencia, esto es, sólo aseguraba que se podía hacer, pero no era constructiva. En 1961 se publicaba el primer método de construcción por parte de Arnold Shapiro y a mediados de los 70 William Thurston (¿os acordáis de la conjetura de geometrización?) daba un método distinto y más general.

De todas formas hemos dejado el asunto todavía en el aire. En el vídeo que aparece anteriormente se ve la eversión pero es cierto que no queda demasiado claro. En el vídeo que aparece a continuación se aclaran bastantes cosas. La explicación está bastante bien (está en inglés, pero es muy visual y se entiende más o menos; de todas formas si queréis el guión lo podéis encontrar aquí) y, entre otras cosas, explican por qué es imposible evertir la esfera $\mathbb{S}^1$ (es decir, una circunferencia en dos dimensiones) pero si es perfectamente factible hacerlo con $\mathbb{S}^2$ . Aquí os lo dejo:

Y si todavía queréis más información, en The Optiverse podéis encontrarla. Tenéis imágenes, vídeos, explicaciones y respuesta a preguntas sobre el tema. El vídeo principal, The Optiverse, fue galardonado con el primer premio del VideoMath Festival, concurso de vídeos relacionados con las Matemáticas, organizado por el ICM’98, en Berlín. Muestra un nuevo método de la eversión de la esfera y sus creadores son John M. Sullivan, George Francis y Stuart Levy.

Y aún más. En este enlace podéis descargar un programa mediante el cual podéis ver la eversión de una esfera mediante el método de Thurston. Moviendo el ratón de izquierda a derecha y viceversa se ve cómo se pasa de un estado a otro; combinando con las teclas Alt y Shift podéis girar la esfera, acercarla o alejarla; y con otras combinaciones de teclas y ratón podéis ver la esfera desde dentro, quitarle trozos para verla mejor…Muy completo.

Para terminar, muchas gracias a La Singularidad Desnuda, que al publicar el otro día un post sobre el tema me recordó que yo tenía información sobre el mismo y me animó a hablar de ello.

Fuentes:

La eversión de la esfera en Matemáticas en Red.
La eversión de la esfera en La Singularidad desnuda.
Smale’s Paradox en la wikipedia (inglés).

Escrito por ^DiAmOnD^, 12 de Noviembre de 2007 en Curiosidades, Geometría
11 comentarios

The matching problem o cómo no formar ninguna pareja

Imaginemos que nos encontramos alguna de esta situaciones y nos planteamos la pregunta que viene en cada una de ellas:

Un profesor manda un trabajo para casa a un grupo de alumnos. Ellos entregan los mismos al profesor y cuando éste los va a devolver corregidos lo hace aleatoriamente. ¿Cuál es la probabilidad de que ninguno de los alumnos reciba su propio trabajo?
En una fiesta hay un cierto número de hombres ataviados con sombrero. Dejan los mismos en una sala y al término de la celebración cogen su sombrero de forma aleatoria. ¿Cuál es la probabilidad de que ninguno de los hombres lleve su propio sombrero?
Vamos a enviar felicitaciones de Navidad a nuestros familiares. Rellenamos las tarjetas por un lado y los sobres por otro y luego metemos las tarjetas en los sobres aleatoriamente. ¿Cuál es lo probabilidad de que ninguna de las tarjetas acabe en el sobre que le corresponde?

Todos estos ejemplos son casos en los que podemos aplicar el, al parecer, llamado The Matching Problem, aunque también he visto que lo llaman Montmort’s matching problem en honor a Pierre Raymond de Montmort, matemático francés nacido en 1678.

Bueno, vamos al tema. Para empezar, creo que se ve bastante claro que todos los casos son equivalentes. Entonces, ¿cuál diríais que es la probabilidad que se nos pide? Lo primero que uno podría pensar es: depende del número de alumnos, hombres y familiares que haya en cada caso. Es decir, que lo normal sería pensar que esa probabilidad depende del número de individuos que tenga la población. Pues no es así. La probabilidad es siempre la misma. Bueno, no exactamente. En realidad la probabilidad se acerca a un número concreto conforme el número de individuos se acerca a infinito. Curioso, ¿no?

Y ahora la pregunta es: ¿cuál es esa probabilidad? Pues bueno, teniendo en cuenta que si llamamos $N_n$ a la variable aleatoria que nos indica el número de emparejamientos válidos de entre $n$ se puede llegar a que su función de probabilidad es la siguiente:

$\displaystyle{P(N_n=k)=\cfrac{1}{k!} \cdot \sum_{j=0}^{n-k} \cfrac{(-1)^j}{j!}}$ con $k=0,1, \ldots ,n$

la probabilidad de que no se haya formado ninguna pareja válida nos la da la probabilidad de que $N_n$ sea igual a ${0}$ . Es decir:

$\displaystyle{P(N_n=0)=\sum_{j=0}^{n} \cfrac{(-1)^j}{j!}}$

¿Os suena esta suma? Seguro que a muchos sí. Hacemos límite cuando $n \to \infty$ y obtenemos lo que queremos:

$\displaystyle{P(N_n=0)=\sum_{j=0}^{n} \cfrac{(-1)^j}{j!} \xrightarrow{n \to \infty} \cfrac{1}{e}}$

Es decir, que la probabilidad de que no se forme ninguna pareja válida se acerca a $\cfrac{1}{e}$ tanto más como grande sea $n$ . Al parecer con $n=5$ ya nos queda una buena aproximación. Lo sorprendente es que cuanto más grande sea $n$ mejor es la aproximación a $\cfrac{1}{e}$ . Y digo yo: ¿cuánto vale ese número? Pues algo así como $0.367879441$ . Es decir, que en una situación de este tipo no se forma ninguna pareja válida aproximadamente el $36,8$ % de las veces. Y ese tanto por ciento se va acercando cada vez más a $\cfrac{1}{e} \cdot 100$ conforme aumenta el valor de $n$ .

Realmente curioso el asunto. ¿Esperabais que la probabilidad fuera más alta o más baja?

Fuentes:

Matching Problem en Math Fun Facts
The Matching Problem en Università di Firenze
The Matching Problem en The University of Alabama in Huntsville

Escrito por ^DiAmOnD^, 30 de Octubre de 2007 en Curiosidades, Estadística, Otras constantes
8 comentarios

La factorización de Fermat

Hace unos días veo este post en Futility Closet:

Mersenne once wrote to Fermat asking whether $100895598169$ were a prime number.

Fermat replied immediately that it’s the product of $898423$ and $112303$ , both of which are prime.

To this day, no one knows how he knew this. Has a powerful factoring technique been lost?

Traducido quedaría algo así:

Mersenne escribió una vez a Fermat preguntándole si $100895598169$ era un número primo.

Fermat respondió inmediatamente que es el producto de $898423$ por $112303$ , ambos primos.

A día de hoy nadie sabe cómo lo supo. ¿Se ha perdido una potente técnica de factorización?

Pues sí, al parecer no se sabe a ciencia cierta cómo factorizó ese número tan grande en tan poco tiempo. Lo que sí se conoce es un método de factorización ideado por Fermat, aunque yo dudo que fuera el que usó para este caso. Pasemos a explicarlo.

El método de factorización de Fermat

La cuestión es factorizar un cierto número $n$ . La idea de Fermat es la siguiente:

Si $n$ es igual a la diferencia de dos cuadrados, digamos $n=x^2-y^2$ , entonces $n$ puede factorizarse de forma muy sencilla de forma evidente: $n=(x+y)(x-y)$ .

Como $x^2$ debe ser mayor que $n$ se tiene que $x$ debe ser mayor que $\sqrt{n}$ . A partir de ésto ya podemos adentrarnos en el método de factorización de Fermat:

Dado un número entero positivo $n$ que queremos factorizar tomamos un entero positivo $x$ mayor que $\sqrt{n}$ (podemos calcular una aproximación de esa raíz cuadrada a ojo o con el método normal y después elegir $x$ ). Calculamos $x^2$ y le restamos $n$ . Si obtenemos un cuadrado hemos terminado. Si no es así tomamos $x+1$ , calculamos $(x+1)^2$ , restamos $n$ y si hemos obtenido un cuadrado se acaba. Procedemos de la misma forma hasta encontrar un cuadrado.

Vamos a ver un par de ejemplos de aplicación del método:

Vamos a factorizar el número $13837$ . Su raíz cuadrada está entre $117$ y $118$ . Tomamos $x=118$ . Pero $118^2-13837=87$ , que no es un cuadrado. Tomamos ahora $x=119$ . Ahora $119^2-13837=324=18^2$ . Por tanto despejando $n=13837$ de esta expresión tenemos su factorización:
$13837=119^2-18^2=(119+18)(119-18)=137 \cdot 101$
Vamos ahora con un número más grande, el que utilizó Fermat para probar la efectividad de su método: $2027651281$ . Su raíz cuadrada está entre $45029$ y $45030$ . Comenzamos con $x=45030$ . Veamos qué resultados obtenemos:
$45030^2-2027651281=49619$ , que no es un cuadrado.
$45031^2-2027651281=139680$ , que no es un cuadrado.
$45032^2-2027651281=229743$ , que no es un cuadrado.
$45033^2-2027651281=319808$ , que no es un cuadrado.
$45034^2-2027651281=409875$ , que no es un cuadrado.
$45035^2-2027651281=499944$ , que no es un cuadrado.
$45036^2-2027651281=590015$ , que no es un cuadrado.
$45037^2-2027651281=680088$ , que no es un cuadrado.
$45038^2-2027651281=770163$ , que no es un cuadrado.
$45039^2-2027651281=860240$ , que no es un cuadrado.
$45040^2-2027651281=950319$ , que no es un cuadrado.
$45041^2-2027651281=1040400=1020^2$ .

Por tanto ya tenemos la factorización:

$2027651281=45041^2-1020^2=(45041+1020)(45041-1020)=44021 \cdot 46061$

Como podemos ver el método está muy bien si la diferencia entre los factores del número no es muy grande pero no es demasiado eficiente si los dos factores están muy alejados el uno del otro, ya que en ese caso la cantidad de cálculos que deberíamos realizar sería enorme. Esa es la razón por la que yo pienso que Fermat no usó este método para factorizar el número $100895598169$ y me temo que siempre nos quedará la duda de qué método utilizó Fermat para realizar esta factorización. De todas formas el método es interesante ya que hasta en nuestros tiempos ha servido como motivación para la búsqueda de nuevos métodos de factorización.

Escrito por ^DiAmOnD^, 5 de Octubre de 2007 en Aprenda como, Curiosidades, Historia, Números enteros
5 comentarios

Curiosidades del número 252

En Gaussianos ya hemos visto alguna vez que ciertos números poseen cualidades, digamos, curiosas (por ejemplo el 142857 y el 153). Vamos a ver algunas del número $252$ que nos comenta merfat en Tres Decas y a contestar a alguna de sus preguntas:

Es un número palíndromo o capicúa
Escrito en una calculadora o en un reloj digital se lee igual si lo giramos 180º
Es el menor número que puede escribirse a la vez como suma de 3, de 7, de 8 y de 9 números naturales consecutivos:
$252=83+84+85$
$252=33+34+35+36+37+38+39$
$252=28+29+30+31+32+33+34+35$
$252=24+25+26+27+28+29+30+31+32$
Es suma de 6 números primos consecutivos:
$252=31+37+41+43+47+53$
Su cuadrado es también muy curioso:
$252 \cdot 252=63504=144 \cdot 441=12^2 \cdot 21^2$
En el post original merfat nos reta a que escribamos el $252$ como suma de 4 cuadrados de dos formas distintas. Vamos a expresarlo como suma de 4 cuadrados de varias formas más:
$252=1^2+7^2+9^2+11^2$
$252=2^2+4^2+6^2+14^2$
$252=2^2+2^2+10^2+12^2$
$252=1^2+1^2+9^2+13^2$
$252=1^2+1^2+5^2+15^2$
$252=4^2+6^2+10^2+10^2$
$252=6^2+6^2+6^2+12^2$

Así a bote pronto no se me ocurren más. Si tenéis alguna vosotros escribidla en un comentario.

Y dejo una de las preguntas de merfat para vosotros: ¿qué ángulo forman las manecillas del reloj cuando éste marca las 2:52?

Escrito por ^DiAmOnD^, 10 de Septiembre de 2007 en Curiosidades, Números enteros
34 comentarios

Cadaeic Cadenza

El usuario 2pir ha propuesto este artículo en Menéame. Si queréis menearlo entrad aquí: Cadaeic Cadenza en Menéame.

Este artículo me lo inspiró agcp26 en este comentario en el post Mnemotecnia y Pi.

No, no me he equivocado en el título. ¿Qué es el Cadaeic Cadenza? Para empezar vamos a ver una cosa curiosa:

Mediante la asociación A=1, B=2, C=3, D=4, E=5, F=6, G=7, H=8, I=9 obtenemos lo siguiente:

C A D A E I C
3 1 4 1 5 9 3

Poniendo una coma decimal después del primer 3 tenemos… $3,141593$ . Es decir, obtenemos el número $\pi$ redondeado a seis decimales. Curioso, ¿verdad? ¿Casualidad? Veremos más adelante que no.

Para la palabra cadenza he encontrado esta posible explicación: Cadenza en MSN Encarta.

(Sigue leyendo …)

Escrito por ^DiAmOnD^, 6 de Septiembre de 2007 en Curiosidades, Pi
9 comentarios

Posts más antiguos