Gaussianos

Matemáticas y naturaleza

El matemático juega a un juego en el que él mismo inventa las reglas, mientras que el físico juega a un juego en el que las reglas son proporcionadas por la naturaleza; pero a medida que pasa el tiempo se hace cada vez más evidente que las reglas que el matemático encuentra interesantes son las mismas que las que ha escogido la naturaleza.

Paul Adrien Maurice Dirac

Boletín 136 de la RSME

¿Estáis de acuerdo?

Escrito por ^DiAmOnD^, 7 de Mayo de 2008 en Citas matemáticas
11 comentarios

Conjetura sobre combinaciones lineales de enteros y números primos

Sebastián me manda por mail a gaussianos (arroba) gmail (punto) com una conjetura sobre números primos que se le ha ocurrido a él mismo. No sabe si es cierta o falsa. Os la propongo como problema para ver qué sacamos en claro:

Sea $n$ un número par. Para todo $k\in\mathbb{N}$ tal que $2 \le k \le \textstyle{\frac{n}{2}}$ existen una o más combinaciones lineales de enteros de la forma:

$a_1 \cdot p_1+a_2 \cdot p_2+ \ldots +a_m \cdot p_m=n$

con $a_i \ge 0$ , $a_1+a_2+ \ldots +a_m=k$ y $p_1,p_2, \dots ,p_m$ todos los números primos menores o iguales que $n$ .

Ejemplo:

$n=10, \cfrac{n}{2}=5$

$p_1=2,p_2=3,p_3=5,p_4=7$

$2 \cdot 5=10 \Rightarrow a_1=0,a_2=0,a_3=2,a_4=0, \displaystyle{\sum a_i=2}$

$1 \cdot 3+1 \cdot 7=10 \Rightarrow a_1=0,a_2=1,a_3=0,a_4=1, \displaystyle{\sum a_i=2}$

$1 \cdot 2+1 \cdot 3+1 \cdot 5=10 \Rightarrow a_1=1,a_ 2=1,a_3=1,a_4=0, \displaystyle{\sum a_i=3}$

$2 \cdot 2+2 \cdot 3=10 \Rightarrow a_1=2,a_2=2,a_3=0,a_4=0, \displaystyle{\sum a_i=4}$

$5 \cdot 2=10 \Rightarrow a_1=5,a_2=0,a_3=0,a_4=0, \displaystyle{\sum a_i=5}$

Pregunta 1: ¿Esta conjetura es cierta o es falsa?
Pregunta 2: ¿Podemos obtener la conjetura de Goldbach como caso particular de esta conjetura?

Vamos a ver si le sacamos jugo al asunto.

Escrito por ^DiAmOnD^, 6 de Mayo de 2008 en Juegos
6 comentarios

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
9 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

La llave

La Matemática es la llave de oro que abre todas las ciencias.

Víctor Duruy

Fuente: INFINITUM. Citas matemáticas

¿Estáis de acuerdo?

Escrito por ^DiAmOnD^, 30 de Abril de 2008 en Citas matemáticas
10 comentarios

Encontrando la suma a partir del divisor

Os dejo aquí el problema de la semana:

Sea $a$ un número natural. Probar que existe otro número natural $b$ tal que para todo natural $n$ se verifica que:

$a$ divide a $1^n+2^n+3^n+ \ldots +b^n$ .

A por él.

Escrito por ^DiAmOnD^, 29 de Abril de 2008 en Juegos
5 comentarios

La hipopede de Eudoxo

Inauguramos una nueva categoría en el blog llamada Curvas famosas con esta colaboración de fede enviada a gaussianos (arroba) gmail (punto) com. Espero que os resulte interesante.

Eudoxo de Cnidos

Eudoxo de Cnidos fue un filósofo, astrónomo, matemático y médico griego, pupilo de Platón. Nada de su obra ha llegado a nuestros días; todas las referencias con las que contamos provienen de fuentes secundarias. Nació en Cnido, actualmente en Turquía, sobre el 400 a.C.

Sus aportaciones principales son la invención de la esfera astronómica y aportes para comprender el movimiento de los planetas (en astronomía) y su trabajo de la teoría de la proporción y cálculo de ciertos volúmenes mediante el método de exhaución creado por él mismo (en matemáticas). En este artículo vamos a hablar sobre una curva que él mismo introdujo: la hipopede.

La hipopede de Eudoxo

hipopede2 Supongamos una esfera con centro $O$ que gira alrededor de un eje $ON$ . Sea un punto $M$ en esa esfera que gira y sea $P$ un punto de intersección de los círculos máximos perpendiculares a $ON$ y $OM$ . Si mientras gira la esfera un punto $H$ parte de $P$ y se mueve por el círculo máximo perpendicular a $OM$ a la misma velocidad angular que la esfera y en sentido contrario, ese punto $H$ describe una curva con forma de 8 en el espacio.

Según cuenta Simplicio, comentarista de Aristóteles del siglo VI, e interpretó Schiaparelli, Eudoxo llamó hipopede a esa curva.

Si $R$ es el punto del espacio en que coinciden en su movimiento $P$ y $H$ , el ángulo $POR$ es siempre igual al ángulo $POH$ .

Schiaparelli observó que la hipopede es la intersección de la esfera con un cilindro tangente interiormente a la esfera en el punto $R$ y que también es la intersección de la esfera con un cono cuyo eje es tangente a la esfera por $R$ y paralelo a $ON$ , y dio una demostración elemental de estos hechos, pero la prueba que sigue es más sencilla.
dhesfera2

Suprimimos el giro de la esfera, pero dejamos que $H$ se siga moviendo por su círculo máximo (círculo $PBS$ de la figura), alejándose de $P$ . Si al mismo tiempo que $H$ sale de $P$ salen de $P$ dos puntos $R$ y $T$ moviéndose por el círculo máximo perpendicular a $ON$ (círculo $PAS$ de la figura) en sentidos opuestos y a la misma velocidad angular que $H$ sobre su círculo, el plano en que están $H$ , $R$ y $T$ en cada instante será siempre paralelo al plano tangente a la esfera en $P$ .

Ese plano corta a la esfera en un círculo de diámetro $RT$ y por tanto el ángulo $RHT$ es recto. Entonces el ángulo $HTR$ es complementario del ángulo $HRT$ . Si $FR$ es perpendicular al plano $PAS$ , el ángulo $FRH$ también es complementario del ángulo $HRT$ , y entonces los ángulos $FRH$ y $HTR$ son iguales.

Pero el ángulo $HTR$ inscrito en el círculo de diámetro $RT$ es la mitad del ángulo central para el mismo arco, que es el ángulo entre los planos $PAS$ y $PBS$ .

Por tanto el ángulo entre las rectas $FR$ y $HR$ es constante. Y como los triángulos $HRT$ , en sus diferentes posiciones, son semejantes, la razón $\textstyle{\frac{RC}{RT}}$ es constante, donde $C$ es el pie de la perpendicular desde $H$ sobre $RT$ .

Ahora, si hacemos girar la esfera alrededor del eje $ON$ a la misma velocidad angular que el punto $R$ y en sentido contrario, el punto $R$ quedará fijo en el espacio en la posición que ocupaba $P$ y el punto $H$ describirá la hipopede. Como el ángulo entre $FR$ y $HR$ es constante, $HR$ es generatriz de un cono con eje $FR$ , y como $\textstyle{\frac{RC}{RT}}$ es constante, el punto $C$ describe una curva que es el resultado de aplicar una homotecia con centro $R$ a la curva que describe el punto $T$ , es decir, describe un círculo. Y como la hipopede se proyecta sobre ese círculo, está en un cilindro.

Como corolario obtenemos que la curva intersección de un cilindro con un cono cuyo eje sea una generatriz del cilindro es una hipopede de Eudoxo y por tanto una curva esférica.

En la reconstrucción por Schiaparelli de la teoría astronómica de las esferas homocéntricas de Eudoxo, el movimiento del planeta sobre la hipopede que producen las dos esferas más interiores (de las 4 que usa para cada planeta) sirve para explicar las retrogradaciones planetarias, es decir los retrocesos transitorios que se observan en las trayectorias de los planetas vistos desde la Tierra moviéndose sobre el fondo de estrellas fijas.

Escrito por ^DiAmOnD^, 28 de Abril de 2008 en Curvas famosas
8 comentarios

Geometría curiosa

La suposición de que la suma de los tres ángulos de un triángulo es menor de $180^\circ$ conduce a una geometría curiosa, completamente diferente a la nuestra, pero totalmente consistente, que he desarrollado a mi entera satisfacción.

Carl Friedrich Gauss

Fuente: INFINITUM. Citas matemáticas

Y la suposición de que esa suma es mayor de $180^\circ$ también. En el quinto postulado podéis ver algo sobre el tema. Y aquí otra cita sobre este tema.

Escrito por ^DiAmOnD^, 23 de Abril de 2008 en Citas matemáticas
2 comentarios

Producto con cosenos

Semanas difíciles estas últimas por varias cosas. De todas formas pronto volverán a aparecer con la frecuencia habitual artículos más largos y elaborados. Mientras tanto os dejo con el problema de la semana:

Para cada natural $n \ge 3$ calcular:

$\displaystyle{\prod_{k=1}^{\lfloor \frac{n-1}{2} \rfloor}} \left (3+2 cos(\cfrac{2k \pi}{n}) \right )$

El límite superior del producto es la parte entera de $\textstyle{\frac{n-1}{2}}$ .

A por él.

Escrito por ^DiAmOnD^, 22 de Abril de 2008 en Juegos
6 comentarios

La belleza del binomio

El binomio de Newton¹ es tan bello como la Venus de Milo. Lo que hay es poca gente que se dé cuenta de ello.

Fernando Pessoa

Fuente: Microsiervos

Creo que Fernando Pessoa tiene razón. Con la identidad de Euler probablemente pase lo mismo, igual que con otras fórmulas e identidades matemáticas. ¿Qué otros ejemplos significativos se os ocurren?

¹: Recuerdo la fórmula del binomio de Newton:

$\displaystyle{(a+b)^n=\sum_{r=0}^n {n \choose r} a^{n-r} b^r}$

Escrito por ^DiAmOnD^, 16 de Abril de 2008 en Citas matemáticas
19 comentarios

Posts más antiguos