Blogaritmo natural

Archive for the 'matemáticas' Category

Concurso de Mictlan: TJU Contest #10

Posted Abril 26, 2008

Publico mis soluciones a los problemas del pasado concursito en el sitio de la Universidad Tecnológica de la Mixteca - Mictlan: TJU Contest #10, en el orden en que los resolví. En general me gustó el torneo, los problemas estuvieron variados y bien escogidos. Lástima que al final se cayó el servidor y no pude terminar el problema que me quedó faltando.

El primer problema que resolví fue el 2772 - Parallelogram. Consiste en determinar si 4 puntos dados podrían ser las esquinas de un paralelogramo. Utilicé la ecuación canónica $LaTeX - ax + by + c = 0$ de una recta para resolverlo.
Este es el código: 2772.cpp
Después hice 2189 - The key stations: Hallar los puntos de articulación de un grafo no dirigido. Hay un problema casi idéntico en el sitio de la Universidad de Valladolid. Ya lo había hecho, así que conocía el algoritmo y reciclé código. El algoritmo está en el libro “Introduction to Algorithms” de Thomas Cormen y otros.
No me gustó el formato de entrada de este problema. Me dio Accepted al segundo intento, por un estúpido Presentation Error.
Este es el código: 2189.cpp
2028 - Excuses, excuses!. Un problema ad-hoc de strings. Utilicé un mapa para el diccionario y un stringstream para dividir una frase en palabras.
Otro Presentation error más estúpido todavía me dio otros 20 minutos de penalización.
El código: 2028.cpp
Finalmente resolví 1058 - Lifting the stones. Para mi gusto el mejor problema del set. Se resume así: Dado un polígono simple (es decir, que no se intersecta a sí mismo) que representa una lámina de densidad superficial constante, encontrar las coordenadas del centro de masa de la lámina.
Resolví este problema aplicando el Teorema de Green, que relaciona la integral doble de una región con la integral de línea de la curva que la encierra. En otras palabras:

$LaTeX - \int_{C} \vec{F} \cdot \, d\vec{r} = \iint_{R} \left( \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} \right) \, dA$ donde $LaTeX - \vec{F}$ es un campo vectorial de la forma $LaTeX - \vec{F} = < P(x,y) , Q(x, y) >$ .

Ahora bien, la coordenada $LaTeX - X$ centro de masa de una lámina plana está dada por:

$LaTeX - \bar{C}_{x} = \frac{ \iint_{R} \rho \, x \, dA }{M}$ donde $LaTeX - \rho$ es la función de densidad (en este problema una constante que podemos considerar $LaTeX - \rho = 1$ ) y $LaTeX - M$ es la masa neta de la lámina.

Similarmente, la coordenada $LaTeX - Y$ es:
$LaTeX - \bar{C}_{y} = \frac{ \iint_{R} \rho \, y \, dA }{M}$ .

La parte crítica del problema es ver que las integrales dobles que aparecen en los denominadores se pueden expresar como una integral de línea, y esta se puede evaluar conociendo los puntos del polígono porque un polígono simple es una curva cerrada suave a trozos donde cada trozo es una recta.

Sea $LaTeX - \vec{F}$ un campo vectorial con la forma $LaTeX - \vec{F} = < P(x,y) , Q(x,y) > = < 0, \frac{x^2}{2} >$

Derivando parcialmente obtenemos que:
$LaTeX - \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} = x$

Que es justamente la función que queremos integrar.

Aplicando el Teorema de Green llegamos a que:
$LaTeX - \iint_{R} x \, dA = \iint_{R} \left( \frac{\partial Q}{\partial x} - \frac{\partial P}{\partial y} \right) \, dA$

$LaTeX - = \int_{C} \vec{F} \cdot \, d\vec{r} = \int_{C} P \, dx + Q \, dy$

pero como el polígono es una curva suave a trozos podemos expresar esta última integral como la suma de una integral por tramo:

$LaTeX - = \int_{C_1} P \, dx + Q \, dy +\, \cdots \, + \int_{C_n} P \, dx + Q \, dy$

$LaTeX - = \sum_{i=1}^{n} \int_{C_i} P \, dx + Q \, dy$

Ahora sólo hace falta parametrizar la curva $LaTeX - C_{i}$ para evaluar esta integral de línea.
Dado que $LaTeX - C_i$ es una recta que va de los puntos $LaTeX - (x_{i}, y_{i})$ a $LaTeX - (x_{i+1}, y_{i+1})$ la parametrizamos con la función vectorial $LaTeX - \vec{r} = < t , \, m (x - x_i) + y_i >$ donde el parámetro $LaTeX - x_{i} \leq t \leq x_{i+1}$ La primera coordenada de esta función es lo que hemos llamado $LaTeX - x$ y la segunda es lo que hemos llamado $LaTeX - y$ , y $LaTeX - m$ es la pendiente de la recta $LaTeX - C_i$ . Derivando estás funciones vemos que $LaTeX - dx = dt$ y $LaTeX - dy = m \, dt$ .

Entonces nuestra integral de línea en cuestión queda

$LaTeX - \int_{C_i} P \, dx + Q \, dy = \int_{x_i}^{x_{i+1}} 0 \, dt + \frac{x^2}{2} m \, dt$

$LaTeX - = \int_{x_i}^{x_{i+1}} \frac{x^2}{2} m \, dt$

Una integral fácil de evaluar cuyo resultado es

$LaTeX - = \frac{1}{6} m\, \left( x_{i+1}^3 - x_{i}^3 \right)$

Teniendo en cuenta que $LaTeX - m = \frac{y_{i+1} - y_i}{x_{i+1} - x_{i}}$ y aplicando un poco de álgebra, vamos a llegar por fin a la solución:

$LaTeX - \bar{C}_{x} = \frac{ \iint_{R} x \, dA }{M} = \frac{1}{6M} \sum_{i=1}^{n} (y_{i+1} - y_{i}) (x_{i+1}^2 + x_{i+1} x_{i} + x_{i}^2)$

Para la coordenada $LaTeX - Y$ es un proceso casi idéntico, pero me da mucha pereza escribirlo acá.
La respuesta es:

$LaTeX - \bar{C}_{y} = \frac{ \iint_{R} y \, dA }{M} = \frac{1}{6M} \sum_{i=1}^{n} (x_{i} - x_{i+1}) (y_{i+1}^2 + y_{i+1} y_{i} + y_{i}^2)$

Sólo faltan dos detalles para poder codificar una solución aceptada por el juez: Para efectos de este problema, la masa es directamente proporcional al área del polígono. El área se encuentra con el algoritmo explicado en el libro Programming Challenges de Miguel Revilla. El otro detalle es que el teorema de Green nos exige que la curva cerrada esté orientada en sentido antihorario, así que si el polígono original está en sentido horario hay que reversarlo antes de correrle este algoritmo.

Tengo que decir que gran parte de esto salió de la cabezota de Arcila.

De cualquier modo, aquí está el código: 1058.cpp

Ahh por cierto, pudieron ahorrarse el trabajo de leer toda esta vomitadera matemática leyendo esto (Tal vez debí poner este anuncio arriba).

Nota del autor: Buah, acabo de leer todo lo anterior y me parece sumamente aburrido. Necesito bailar un rato.

Irracional

Posted Octubre 20, 2007

Comments(0)

Aquí les presento una prueba que me ha gustado mucho por ser un razonamiento bastante ingenioso. Para algunos lectores este tipo de posts resulta casi una ofensa. Si eres uno de esos, te recomiendo que intenes superar el récord en el juego del conejo. Cómo decía la rectora de mi colegio, “Guerra avisada no mata soldado.” O cómo diría Pseudópodo:

Supongamos que $LaTeX - \sqrt{2}$ es un número racional. En este caso, podría expresarse cómo el cociente de dos enteros.

$LaTeX - \sqrt{2} = \frac{p}{q}$ donde $LaTeX - p, q \in \mathbb Z$ .

Paradoja de la dicotomía

Posted Octubre 14, 2007

Comments(1)

Esta paradoja fue planteada por el filósofo griego Zenón de Elea, 5 siglos antes de la aparición del Barbado. La paradoja plantea lo siguiente:

Un hombre parado en un cuarto no puede caminar hasta la pared. Para lograrlo, tendría que recorrer primero la distancia que lo separa de ella, luego la mitad de la distancia restante, luego la mitad de la distancia restante… El proceso siempre puede continuarse y no tiene fin.

Gráficamente, si la distancia entre la pared y la persona es 1, sería algo así:

Paradoja de la dicotomía

Intituivamente pareciese que la suma de todos estos términos fuera 1, es decir:

$Paradoja de la dicotomía - Zenón$

Este resultado es fácil de probar utilizando cálculo, pues se sabe que $Serie geométrica$ es una serie geométrica, con $Paradoja de la dicotomía - Zenón$ . Además, es bien sabido que:

A una serie de la forma $Serie geométrica$ se le llama serie geométrica con término constante $Serie geométrica$ y razón $Serie geométrica$ . Una serie geométrica diverge si $Serie geométrica$ y converge a $Serie geométrica$ si $Serie geométrica$ .

Aplicando este criterio, se sigue que la serie converge a $Serie geométrica$ , que era lo que queríamos probar.

De este modo, se ve que al caminar sucesivamente la mitad de la distancia recorrida, finalmente se recorre la unidad completa, y la persona logra llegar a la pared.

La bomba de la maleta

Posted Octubre 10, 2007

Comments(3)

“Un hombre que viajaba mucho estaba preocupado por la posibilidad de que hubiera una bomba en su avión. Calculó la probabilidad de que fuera así y, aunque ésta era baja, no lo era lo suficiente para dejarlo tranquilo. Desde entonces lleva siempre una bomba en la maleta. Según él, la probabilidad de que haya dos bombas a bordo es infinitesimal.”

Tomado del libro:

“El hombre anumérico: El analfabetismo matemático y sus consecuencias”, John Allen Paulos.

Increíble manera de multiplicar

Posted Octubre 5, 2007

Comments(3)

En el blog de YouTube Videos están haciendo un concurso para ganar un Halo 3 para Xbox 360. Las reglas son sencillas, sólo hay que escribir un post donde se comente el concurso y se muestre un video de YouTube. Si quieres inscribirte entra a la página del concurso. Aquí va mi participación:

Estos videos me han dejado asombrado por lo ingeniosos que son. Creo que voy a seguir aplicando estos métodos en mi vida diaria. ¡Increíbles!