viernes, octubre 29, 2004

Más Matemática Discreta

Aunque no es el tema principal de este weblog las matemáticas (si os gustan podéis ir al weblog de Tío Petros), voy a hacer un par de comentarios sobre teoría de grafos:
  • Grafo Euleriano: en el que se pueden recorrer todas las aristas sin pasar más de una vez por cada una.
  • Grafo Hamiltoniano: en el que se pueden recorrer todos los vértices sin pasar más de una vez por la misma arista.
ahora viene la pregunta estelar, que todos recordamos con gran cariño y emoción:

¿Qué relación hay entre los grafos eulerianos y hamiltonianos?

jueves, octubre 14, 2004

miércoles, octubre 13, 2004

El holocausto palestino

Este post va a ser relativamente corto, sólo quiero llamar la atención sobre las técnicas y métodos que usan los Israelíes para combatir el terrorismo.

Levantar muros, crear guetos, realizar incursiones de exterminio... creo que sólo les faltan los campos de concentración para completar la lista de las cosas que el pueblo judío sufrió durante la época del nazismo en Alemania. Además, sabiendo cómo es esta gente de práctica, seguro que además de jabón y botones le sacan muchos más usos al tema.

Señor Spielberg, ¿para cuando una película sobre ésto? ah, claro, que aquí no hay ningún Oskar Schiendler.

En fin, echaremos ésto al saco del olvido, como ocurrió con el holocausto armenio y la guerra civil española.

Por último, una mención a Dani, que estaba impaciente por que publicase algo sobre el tema.

lunes, octubre 11, 2004

El juego de los palotes

Como los minutos musicales no triunfan, vamos a por una pedantería del tito fortran. Hace unos días estaba tirado viendo la tele, con un resacón fino, y pillé empezada una serie de dibujos animados en la que por lo visto los protagonistas se enfrentaban a acertijos matemáticos y de lógica.

El problema que se trataba en el fragmento que yo vi era un concurso en un juego que posiblemente conozcáis. Se trata del juego en el que se disponen una serie de fichas (palotes, chinos, pelotillas de papel o de mocos, lo que sea) y los jugadores han de ir retirando de forma alternada un número de fichas, comprendido entre un máximo y un mínimo establecidos de antemano. El que coge la última ficha pierde. La variante más típica del juego creo que es con 20 fichas, pudiendo coger como máximo 3 y como mínimo 1.

El episodio estaba bastante bien, ya que los protagonistas encontraban la fórmula general mediante un razonamiento recursivo a partir del caso más simple en el que tenían la certeza de ganar. Resulta alentador pensar que alguien se ha preocupado de intentar inculcar una forma de pensar ordenada a los niños mediante los dibujos animados.

Recuerdo una ocasión en la que un amigo me retó a jugar, ya que él conocía la forma de ganar en el caso expuesto anteriormente (20 fichas, mínimo 1 y máximo 3). Una lástima para él no haber visto esos dibujos, que supongo que todavía no los habían creado (fue hace bastante tiempo y la serie parece actual). De nuevo lástima para él que yo me hubiese aburrido en clase de Matemática Discreta y hubiese encontrado la solución general para cualquier configuración del juego, con lo cual pude vacilarle a mi gusto propiniéndole distintas variantes y ganando siempre.

Así que aquí vamos, a ver cuál es la solución general, de un modo un poco más riguroso que en la serie de dibujos, pero partiendo más o menos de la misma base.

Para ganar en el juego, hemos de conseguir que en un movimiento nuestro, el número de fichas restantes sea mayor que cero (del contrario habremos perdido) y menor que el mínimo de fichas a retirar. De esa manera obligaremos al contrario a retirar la última ficha.

Por simplicidad, vamos a tratar primero con el caso en el que el mínimo es 1 y el máximo es M. Al comienzo del juego hay N fichas. Nuestro objetivo es dejar 1 ficha exactamente para el movimiento del contrario.

Esto se puede conseguir siempre que en el tablero queden como mucho M+1 fichas, ya que M es el máximo que podremos retirar. Si quedan R fichas, con M+1 >= R > 1 deberemos retirar un número de fichas S = R - 1. Este movimiento es legal, puesto que si restamos 1 en la desigualdad anterior, tenemos que M >= S > 0.

Por otra parte, como suponemos que nuestro rival no es lerdo, debemos intentar impedir que sea él el que se encuentre en tal disposición, por lo que en nuestro turno deberemos intentar que el número de fichas restantes R para su turno, sea mayor que M+1, ya que desde esa situación puede ganarnos retirando S fichas. De hecho, deberemos procurar, siempre que las fichas sean suficientes, dejarle en M+2 fichas, ya que en su turno, retire las que retire, se cumplirá la primera situación.

Aquí es donde entra el razonamiento recursivo. A partir de una situación sencilla en la que tenemos la certeza de ganar, hemos llegado a otra situación más compleja en la que también podemos ganar. Se puede seguir este razonamiento hasta la situación de juego inicial, pero si hay muchas fichas puede hacerse pesado. Así que vamos a recurrir a un poco de aritmética modular para simplificar el asunto.

Un hecho bastante obvio es que en dos turnos consecutivos (adversario y propio), hay un número de fichas que siempre se puede retirar, sea cual sea el movimiento del adversario. Éste número es M+m (siendo m el número mínimo de fichas que se pueden retirar). Debemos aprovechar ésto en nuestro beneficio, y lo haremos, del siguiente modo:

Como nuestro objetivo es dejar una sola ficha y tenemos la seguridad de que cada 2 turnos podemos forzar la situación para que se hayan retirado M+m fichas, hemos de conseguir que queden: [1 + k * (M+m)] fichas, siendo k un número entero mayor o igual que 0. En esa situación, habremos ganado la partida en 2*k+1 turnos.

Dicho de otra forma, hemos de asegurarnos de que cuando movamos, las fichas restantes sean congruentes con 1 bajo módulo (M+m). Esto es que el resto de dividir R entre M+m sea 1.

Conclusión: si el resto de dividir N entre (M+m) está entre 1 y m, que empieze el otro. Si es mayor que m, entonces empieza jugando y consigue que con tu movimiento R mod (M+m) esté entre 1 y m. Tras haber conseguido ésto, puedes mover siempre M+m menos lo haya movido el contrario en el turno anterior.

Espero que os haya resultado interesante...

viernes, octubre 08, 2004

Indegueto

An des nou frai
On de colan grei chicago mon
Beibi benis charlis mornis in de gueto
(in de guetoooo)

An de jar mama crai
Cosi ni fi guan sidosidoní
Mogritien grin mon fuin de gueto
(in de guetoooooo)

Pipol yo on gre taim
De chili jil pi jar
E jil grou bi on de yon man dei

To que lo que yu an mi
Ai güi chublai chu sí
De güi simpli tenangüen an glor de onde güei

Güede guelten
An de güelgui jinquiliti brui
Renibusprisistriti guaibolosusin in de gueto

An de jan gai ben
So si estarer chu ruanes trit
Naili chus trui fuil gi fans fuis in de gueto

De cual nei ende presi on de yon man bri que al güei
E ji sei cal estili car quil tru ruanes trui far jinon mama crai
Ar de croun dan de roanes tris yur man feis dan duisti fuin de gueto...

An de youn man dai

On de col an grei chicago mon de liti beibis charlis is born in de gueto
An des mama crai
(in de guetooooooo)

El Principe Gitano

Ahí está el temazo. Ahora a ver quién es capaz de sacar lo que realmente decía la letra original (no vale tirar de discografía de Elvis, ni de google, eh?). Sólo se puede escuchar la canción de El Principe Gitano y, por supuesto, ver esta transcripción.

jueves, octubre 07, 2004

All I Want

Day after day
Your whole life's a wreck
The powers that be just breathe down your neck
You get no respect
You get no relief
You gotta speak up and yell out your peace

So back off your rules
Back off your jive
Cause I'm sick of not living
Just stayin' alive
Leave me alone
I'm not asking a lot
Don't want to be controlled
It's all I want
It's all I want
It's all I want
It's all I want

How many times is it gonna take
Before someone around you hears what you say
You try being cool
You feel like a lie
You've played by the rules
Now it's their turn to try

So back off your rules
Back off your jive
Cause I'm sick of not living
Just stayin' alive
Leave me alone
I'm not asking a lot
Don't want to be controlled
It's all I want
It's all I want
It's all I want
It's all I want

I've said it before
I'll say it again
If you could just listen
then it might make sense

So back off your rules
Back off your jive
Cause I'm sick of not living
Just stayin' alive
Leave me alone
I'm not asking a lot
Don't want to be controlled
It's all I want
It's all I want
It's all I want
It's all I want

The Offspring, 1997

(efectivamente, ésto es una paranoia del tito fortran).

lunes, octubre 04, 2004

Los últimos días del Edén

Me suena que el título del post se lo he robado a una película, pero el caso es que no recuerdo haberla visto ni saber de qué va. El motivo por el que lo pongo es porque se han acabado la vacaciones, así que ahora vamos a recapitular un poco.

¿En qué he gastado el tiempo durante este verano? pues básicamente en dejarme crecer el pelo... y poco más. Apenas he salido de mi casa. No me he pasado ningún videojuego. No he estudiado. No me he emborrachado. No me he sacado el carné de conducir. Podría seguir mucho tiempo enumerando las cosas que no he hecho.

Resumiendo, que me he tocado los huevos enormemente. De hecho creo que de las pocas cosas de provecho que recuerdo haber hecho una es escribir este weblog. Y tampoco es que sea de mucho provecho.

De lo más emocionante han sido las últimas semanas. He tenido 7 exámenes en este Septiembre y he aprobado 6, lo cual no está nada mal. Por desgracia la única asignatura que he suspendido era la que me quedaba de 3º, lo cual me lo pone muy difícil para pasar a 5º, así que tendré que ir a suplicar a la subdirección de la titulación o yo qué sé. También me ha dado la vena artística: he hecho algunos dibujos y también he aprendido a usar las viejas cámaras de fotos SLR de mi padre; una Nikon FE-N y una Canon FTb.

Pero no nos pongamos en plan intimistas, que no es el estilo de este weblog. Como las batallitas del tito fortran están ganando posiciones en la encuesta, voy a contar lo que ha pasado este último fin de semana de vacaciones... habíamos estado planeando una escapada playera unos cuantos compañeros de clase, pero como suele pasar siempre, la mayoría se rajaron antes cuando estábamos a punto de confirmar el alojamiento. Así que hicimos pacto de cohesión el núcleo fuerte y decidimos irnos de pingo al pueblo de uno de nosotros, sin contar con nadie más que con nuestros testículos y una botella de whisky.

Así que el viernes estábamos dispuestos para salir zumbando, y así lo hicimos. Llegamos al pueblo sobre las 20:00 y fuimos a comprar algo para cenar. Adquirimos las típicas pizzas, lasañas y canelones para microondas, que siempre dan mucho juego. Cenamos y nos ponemos a jugar a la play, que también da mucho juego. En los juegos de coches no tengo nada que hacer, así que disimuladamente sugiero unas pachangas al Tekken 3, donde fundo bastante más. Salimos a dar una vuelta y volvemos a viciar. Cuando estamos hasta las narices, nos vamos a dormir. Hay por ahí una PC-World del 97, que hojeo para ver si me entra sueño, pero lo que nos entra a todos es la risa. Por aquellos tiempos, los artículos de esa revista nos parecían muy sofisticados y profesionales... ahora mismo nos resulta tan divertido como un tebeo de Mortadelo y Filemón.

A la mañana siguiente suena una alarma a las 9:30, que es rápidamente sofocada a base de hostias. Seguimos durmiendo hasta por lo menos las 13:00. No recuerdo muy bien qué es lo que comimos, pero seguro que para beber acabamos con la fanta de limón y tuvimos que recurrir al licor de mora. Intento dormir un rato la siesta mientras mis colegas se vician a un juego de rallies en la playstation y berrean de la emoción. A las 18:00 nos vamos al río cercano. Pese a que da un poco de reparo porque no hay una "playita" en condiciones para acceder, dos de nosotros nos acabamos metiendo en el agua y nadamos un poco, mientras el tercero nos tiraba piedras desde la orilla (hijo de puta...). Cuando salimos damos una vuelta por los alrededores mientras tramamos nuestros planes para la dominación mundial.

Volvemos a la casa justo a tiempo para cenar y ver Terminator 2, la versión extendida. Los cachos nuevos parecen pegotes bastante mal puestos. ¿A qué cojones venía lo de quitarle el chip al chuarche?. Después más playstation. Yo me voy a dormir un poco antes.

A la mañana siguiente, debido a mi adelantamiento a la hora de acostarme, soy el primero en despertarse y joder a los demás. Me pongo a darles toques a los móviles. Cuando deciden que ya les he molestado lo suficiente, se levantan, recogemos y nos vamos.

Decidimos pararnos a comer en Toledo. En cuanto encontramos un sitio para aparcar, nos vamos a la oficina de turismo a por un plano de la ciudad. Las chicas de allí nos vieron demasiada cara de guiris y nos preguntaron que de dónde éramos. Nos garabatearon un poco el plano marcándonos cuáles eran los sitios interesantes para visitar, tras lo cual el plano acabó en la mochila y no le volvimos a prestar atención.

Subimos hacia el casco antiguo y nos encontramos una tienda de kebaps. Dos decidimos comernos unos para ir haciendo boca hasta que encontremos algún sitio más sustancioso para comer. Entramos allí y el aspecto del establecimiento era de acojone. Poca luz. Una televisión emitiendo una película supuestamente turca. Dos tíos detrás del mostrador con pintas muy extrañas. Unos chavales igual de extraños sentados en la barra. Y todos hablando en... ¿árabe? o lo que sea que hablen los turcos. Entran 3 tíos más, seguramente del mismo grupo étnico. Nos atienden. Pedimos un par de kebaps de ternera. Yo hago como que miro la película y sonrío. Al cabo del rato nos los sirven, pagamos y nos vamos.

Seguimos nuestra escalada hacia el centro del casco antiguo de la ciudad y observamos curiosos que no hacen más que subir cochazos (bmw, jaguar, porsche...) y bajar tartanas. Arriba debe haber una panda de jinchos muy peligrosa, así que nos comemos los kebaps antes de que nos los manguen. Llegamos a una plaza bastante céntrica y encontramos una templo del arte culinario. Un sitio donde la tradición y la cultura ancestrales se unen con el saber hacer y un buen gusto exquisitos, para dar lugar a los mejores platos que jamás haya probado un paladar humano. Qué cojones, que encontramos un McDonalds. Así que ahí nos paramos a comer.

Después de cebarnos bien, nos deleitamos en ver lo bien que se bajan las cuestas que uno ha subido con anterioridad. Sobre todo cuando la gravedad ayuda más que nunca, gracias a esas ingentes cantidades de grasas ingeridas. Nos paramos en un mirador, pero el paisaje no está como parar tirar muchas fotos, ya que unas cuantas grúas estropean la panorámica. Nos sentamos un rato (por motivos obvios) y de paso hacemos un pequeño concurso apostando sobre si dos tías que hay cerca se van a dar un muerdo o no.

Volvemos al coche y proseguimos nuestro camino de regreso hacia Madrid. En esos momentos suenan las canciones más frikis del cd que está puesto: "in de gueto", del Príncipe Gitano; "maldito duende", versionada por Raphael; "pobre principito", de Mamá Ladilla... después de reirnos un rato intentando "pegarle el latigazo" al coche del chófer de Sadam Hussein, llegamos a Madrid y por decisión unánime nos vamos a mi casa a viciar al Counter-Strike. Primero pasamos por casa de mis colegas, para dejar equipajes y recoger ordenadores. Cuando llegamos a mi casa, están de visita algunos familiares, ya que es el cumpleaños de mi madre. Saludamos y después de estar un rato en el patio echando unas canastas nos subimos a la buhardilla.

Inexplicablemente, después de jugar un rato bastante breve, nos damos cuenta de que apenas hay ganas de seguir viciando. Cenamos lo que sobró de la barbacoa que habían hecho al medio día. Subimos otra vez, y al rato bajamos a ver los finales alternativos de "28 Días Después". Efectivamente, saber que al día siguiente hay clase está minando la moral de la tropa.

A la 1:45, decidimos irnos a dormir. Mis colegas deciden que es lo suficientemente pronto como para volver a sus casas. Recogen y se van. Yo me voy a dormir. Me levanto y escribo ésto. Buenas noches.