Otro concurso online de problemas matemáticos

He recibido una invitación para participar en otro concurso de problemas para freakies matemáticos: Cerebra. Se celebrará los sábados 21 y 28 poco después de comer hora española.

Voy a ver si me apunto, porque los últimos fines de semana he estado sufriendo demasiado mientras espero a que salga el problema del proyecto Euler.

Resulta que minutos antes de que se publique el problema y empiece la carrera para resolverlo, todos los matemáticos programadores ociosos del planeta se pasan por ahí y empiezan a pinchar frenéticamente en el botón de refrescar para ser los primeros en tener el enunciado, y la página recibe tal bombardeo que entre todos le hacemos involuntariamente un ataque de denegación de servicio. Sí, los freakies somos un horda. Como últimamente pasa una hora antes de poder ver el problema, la cosa está perdiendo su gracia. En fin, paciencia.

Problema real

Os voy a proponer un problema real de matemáticas financieras.

Érase que se era una empresa con graves problemas. Varios inversores compraron participaciones con una diversidad de condiciones, de forma que no está muy claro cuánto vale esta empresa, pero hay que buscar más socios e inyectar más dinero con la esperanza de que aguante hasta que acabe la crisis y empiece a ganar dinero.

Total, que los ejecutivos de esta empresa van a hablar con unos qataríes y les proponen que compren la mitad de la empresa por una cantidad de dinero X. Los qataríes dicen que están de acuerdo, pero exigen a los actuales propietarios de la empresa que se rasquen los bolsillos como sea y pongan otros X euros. Debe de ser un buen trato, porque los propietarios, que posiblemente sí que saben lo que vale la empresa, se ponen muy contentos y dicen que las negociaciones están muy avanzadas.

¿Cuánto vale la empresa ahora? (es decir, antes de que los qataríes compren la mitad)

El problema es curioso porque parece que faltan datos... pero no.

http://www.expansion.com/accesible/2011/12/16/catalunya/1324068132.html

Estadísticas

Otra encuesta que hacen en Telemadrid y les sale el 78%. Para mí que siempre preguntan a los mismos 9, y hay 2 de la oposición.

Otro descubrimiento maravilloso que no lo es

¿Habéis oído hablar de Aidan Dwyer? Lo mismo no, dejadme que os copie unos titulares de la prensa española:

• ABC: "Un niño de 13 años puede revolucionar la energía solar" (23 de agosto de 2011)
• RTVE.es: "Un niño de 13 años crea un sistema que mejora la energía solar en un 20% gracias a Fibonacci" (24 de agosto de 2011)
• La Crónica: Joven de 13 años crea "árbol solar" que genera más energía que paneles (21 de agosto de 2011)

La historia viene a ser ésta. Un chico tiene que hacer un proyecto de ciencias, se da un paseo por un bosque para pensar, y se le ocurre cómo sacar más energía de los paneles solares al observar cómo están orientadas las hojas de los árboles. Tras inspirarse en la naturaleza, recupera un modelo matemático del siglo XIII de Leonardo de Pisa alias Fibonacci, lo usa para construir un modelo de árbol con células fotovoltaicas orientadas en diversas direcciones, y comprueba que funciona mejor que los paneles tradicionales.

Impresionante, ¿no? Veamos qué resortes nos toca esta noticia para que estemos dispuestos a creernos algo que parece demasiado bueno para ser verdad:

• El adolescente genial e inocente.
• Culto a la naturaleza.
• Reaprovecha conocimientos antiguos.
• Es una idea fácil de entender.
• Es algo útil.
• Es un tema de moda.
• Jolín, si es que hasta Fibonacci, el matemático mencionado, es "amistoso"; se le suele vincular con la razón áurea, un número relacionado con el arte, nada que ver con matemáticas aburridas. O sí, claro.

Seamos sinceros, los científicos tienen/tenemos un problema de imagen; al público le parecen unos listillos pedantes que se gastan cantidades enormes de dinero en cosas que no se entienden, y nos encanta que les enmienden la plana. Cualquier artículo que diga que un experto se lo tiene que replantear todo deja un buen sabor de boca.

Así que cuando leemos sobre un chaval que ha descubierto que cambiando la orientación de los paneles solares se puede producir desde un 20% hasta un 50% más de energía, lo queremos creer. Seguro que a los expertos en energía solar nunca se les ha ocurrido eso de orientar los paneles, qué coño sabrán ellos.

Pero lo que revela el incidente es el pésimo nivel de nuestros periodistas científicos. Aquí nadie habla con un experto antes de publicar una noticia que a todos nos hace desconfiar. Me pregunto durante cuánto tiempo habrá gente que al ver paneles solares orientados paralelamente piense que están mal montados y que se hace así porque hay una conspiración para que la energía fotovoltaica no funcione bien.

(Cambiando de tema, los paneles fotovoltaicos de tercera generación ya tienen una eficiencia del 45%. Vale que son carísimos y que en la práctica lo que se sigue usando son los paneles de primera generación, que sólo aprovechan alrededor del 8% de la luz, pero esto va mejorando poco a poco.)

El fallo de Aidan fue medir el voltaje de su árbol, en vez de su potencia (queremos los paneles solares para generar energía, no voltios). Resulta que, al usar un voltímetro sin carga, lo que estaba midiendo en realidad era el voltaje de la célula mejor orientada. La mayoría de sus células estaban peor orientadas que con el método tradicional, pero lo más probable es que alguna de ellas estuviese muy bien orientada hacia el sol, y era esta célula la que determinaba el voltaje medido (mientras no se usase la electricidad para nada). Aquí lo explican bastante bien, aunque está en inglés.

Es posible que ahora Aidan esté avergonzado al ver que todo el planeta se dedica a explicar por qué hizo mal su proyecto, pero yo apostaría a que está cabreado con el primer periodista que empezó esta avalancha mediática de verano: "Mira que ya le dije que mi profesor de ciencias me había explicado el error, pero ese capullo quería un titular que vendiese". Pasa de todos, Aidan, tu idea era buena y merecía mirarse.

El motor de agua

Hace poco tuve una charla con alguien que todavía cree en el motor de agua. A mí me sonaba que esto estuvo de moda allá por la crisis energética de los 70, cuando yo era muy niño, y apenas recordaba nada, así que por pura curiosidad estuve googleando un poco para enterarme. Y bueno, he encontrado tantas cosas absurdas que me entraron ganas de escribir un articulito organizándolas.

Para no confundirnos, aclaremos que un motor de hidrógeno es un motor de explosión que usa hidrógeno en vez de gasolina; y que una célula de hidrógeno produce electricidad pero no es un motor. Las células de hidrógeno y los motores eléctricos son muchos más eficientes que los motores de explosión. Estas cosas funcionan, pero no son motores de agua. Un motor de agua usaría agua como combustible, no hidrógeno.

Primera sorpresa: sigue habiendo en Internet bastante gente que habla del motor de agua como si pudiese funcionar, pero no hay absolutamente ningún debate. Si visitas una página "en contra" del motor de agua, se hablará de química y de entropía. Pero en las páginas "a favor" sólo hay conspiranoia sobre las empresas petroleras, y de la más chusquera.

La segunda sorpresa ha sido descubrir que en realidad ha habido cientos de inventores del motor de agua, cualquiera diría que esta tecnología cuenta con una poderosa industria antes de existir. Veamos algunos casos de errores, estafas, manipulaciones, y otras confusiones:

• Entre los conspiranoicos hay ganas de hacer creer que esto del motor del agua es tan sencillo que ya se inventó en 1807 (lástima que eso sea un motor de hidrógeno). He aquí una buena lista con 31 inventores que supuestamente inventaron motores de agua, pero yo he buscado un poquito sobre los primeros, los del siglo XIX, y no he visto que inventasen nada por el estilo (parece que el motor de agua se convirtió en el Santo Grial de la ciencia durante el siglo XX). También es curioso que haya tanta gente convencida de que las referencias de Julio Verne (1828-1905) al hidrógeno les justifican.
• Albert Elder von Filek le vendió a Franco el secreto de la gasolina en polvo 1 2. Aparecieron cosas en el BOE y en los periódicos, hasta que se dieron cuenta de que aquéllo era un timo y enchironaron al austríaco. En realidad, hay formas de producir gasolina sintética a partir de carbón, como el proceso Bergius, pero son ruinosamente ineficientes, y Filek no pretendía usar carbón, sino agua.
• Stanley A. Meyer se convirtió en el prototipo de inventor asesinado por las fuerzas del mal. Un día estaba comiendo cuando de repente se puso a gritar "¡Me han envenenado! ¡Me han envenenado!". Y pocos minutos después moría de un aneurisma cerebral. Dejando al margen la cuestión de cómo un veneno podría causar un aneurisma, Meyer tenía un buggy en el que decía haber instalado una célula de combustible de su invención. El problema es que él fue la única persona que consiguió hacer funcionar su invento, y un tribunal le condenó a devolver 25.000 dólares a unos inversores; por si hubiese dudas, la sentencia decía "gross and egregious fraud".
• Francisco Pacheco, Bolivia 1943, y otros cuantos inventores. Entre otras cosas inventó una cortadora de césped que no funcionaba, evidencia indiscutible de que producía tanto hidrógeno que se ahogaba.
• Jean Chambrin Francia 1975 y Paul Pantone EEUU 1998, el segundo condenado por fraude.
• Wang Hongcheng China 1984, inventó la forma de convertir agua en un líquido inflamable. Ya me contarán por qué un país pobre, comunista, y dependiente de energía ajena le condenó a 10 años de cárcel en vez de explotar su invento (o cualquier otro invento occidental).
• Cuando Martin Fleischmann y Stanley Pons anunciaron el descubrimiento de la fusión fría en 1986, aparecieron varios fraudes de tipos diferentes.
• Ramar Pillai India 1996, descubrió que el agua mezclada con un orujo de hierbas puede impulsar motos.
• Patrick Kelly, Idaho 2006, consiguió convencer a unos inversores para que le dejasen 400.000$ con los que desarrollar un motor de agua, pero lo que hizo fue gastárselos en ponerse una fuente en su casa y financiar la tarjeta de crédito de su hija de 12 años.
• John Kanzius EEUU 2007. Estaba buscando un remedio contra el cáncer cuando descubrió que si se irradia una muestra de agua con una cantidad brutal de ondas de radio, algunas moléculas de agua se rompen y el hidrógeno y el oxígeno se vuelven a recombinar, formando una llama. La idea básica no es demasiado original, inyecta mucha enegía de alguna forma en el agua y acabará saliendo algo de energía en otra forma.
• Daniel Dingel, Filipinas 2008, cuando le mandaron a la cárcel por estafar 380.000$ dijo que le quitasen lo bailado (tenía 82 años).
• Mohotti Arachchilage Thushara Priyamal Edirisinghe, Sri Lanka 2008, estafador profesional que engañó a un montón de incautos, y a uno de ellos le quitó más o menos 1.104.693,72 rupias.
• Tareq Abu-Hamed, Universidad de Minnesota 2008, sigue investigando lo del boro, ver más abajo.
• Genepax Japón 2008, ya han construido un coche de demostración, pero les está costando encontrar inversores, quizás porque no explican cómo funciona.
• Stone Charles Luther Europa 2009.
• Jordi Freixas Mataró 2010. Añade agua al combustible para mejorar el rendimiento del motor, con lo que recuerda al motor de Chambrin; lo de "motor de agua" lo dice el periodista porque tiene que usar un títular corto, y así vamos creando leyendas.
• Masahide Ichikawa Japón 2011, ha inventado una motocicleta que funciona con agua de mar. Supuestamente usa un calentador de energía solar para evaporar el agua, con lo que se deposita sodio metálico, y al mezclarlo con agua se genera hidrógeno.
• Otros nueve inventores de rarezas sobre agua y energía. También está la sonoluminiscencia, pero, como siempre, se inyecta más energía en los ultrasonidos que la que sale en forma de luz ultravioleta.

Ya me he cansado. Pero de verdad, creo que no exagero cuando digo "cientos".

Mención aparte merece Arturo Estévez Varela, el "inventor en España" del motor de agua, en 1971. La verdad es que, tras haberle visto en videos, me cae bien este extremeño, porque no engañó demasiado a nadie; por ejemplo, explicaba que su invento no era un motor de agua, sino un generador de hidrógeno, y que el hidrógeno se usaba luego en un motor de explosión convencional. Hacía sus demostraciones usando una moto y un botijo; primero bebía del botijo para demostrar que contenía agua, luego llenaba con él el depósito de la moto, echaba sus pastillas con el aditivo secreto de forma que todo el mundo le viese echarlas, y hala, a correr. Si después de esto alguien insistía en pensar que aquello era un motor de agua, pues allá él.

No es que Estévez fuese un modelo de transparencia; nunca explicó qué eran esas pastillas negras que echaba en el generador. La opinión generalizada es que era boro, que reacciona con el agua para producir óxido de boro e hidrógeno, con lo cual en vez de motor de agua lo que habría inventado sería, si acaso, un motor de boro. No es que esto sea malo, el problema es que el motor de boro no puede competir con los motores de gasolina por las siguientes razones:

1. El precio del boro. Cito de http://www.lamentiraestaahifuera.com/2010/01/07/el-absurdo-motor-de-agua/: "El problema es que se necesitan 45 litros de agua y 19 kg de boro para producir 5 kg de hidrógeno que proporcionarían una autonomía semejante a la de un tanque de 40 litros de gasolina o gasoil. El precio de esos 19 kilos de boro rondaría los 95.000$ (unos 68.000€) mientras que el equivalente en gasoil sería unos 40€". En realidad se puede encontrar boro en diversas formas. Imaginemos que el generador de hidrógeno pudiese funcionar con boro amorfo (pero esto lo digo yo, porque Estévez usaba pastillas negras en vez de polvo marrón, y vista la diferencia de precio debía de tener una buena razón). El caso es que el kilo de boro amorfo se puede conseguir por 1,40€ si compras un mínimo de 20 toneladas; así que en vez de importar dos litros de petróleo que cuestan unos 0,34€ cada uno en origen (el resto son impuestos), pasaríamos a importar un kilo de boro que cuesta 1,40€ en origen. Pues vaya.
2. La contaminación. El óxido de boro contamina bastante más que la gasolina 1 2; el problema es que forma ácido bórico, un conocido insecticida. Actualmente dedicamos un 45% de todo el petróleo a producir gasolina; eso son 5.700 millones de litros al día, que podíamos sustituir por unos 11 millones de toneladas de boro al día, que producirían unos 35 millones de toneladas de óxido de boro al día.
3. Las reservas mundiales de boro son 10 millones de toneladas, así que nuestros coches podrían funcionar durante un día antes de acabar con todo el boro del planeta.
4. El coste energético de producir boro es mayor que la energía que libera. Además, la mayor parte de la energía se convierte en calor al oxidarse el boro, al motor llega menos de la mitad de la energía.

Así pues, usar boro en vez de gasolina no es rentable ni económica ni energética ni medioambientalmente; además, es inviable e insostenible, no hay suficiente boro. Si hiciese falta buscaríamos más depósitos de bórax, pero suele ocurrir que la extracción en minas pequeñas es más cara que en las minas grandes (las que explotamos ahora). Y podríamos encontrar formas de reciclar el óxido de boro para producir boro, pero cualquier procedimiento que haga esto gastará al menos tanta energía como la que se produce al oxidar el boro; ¿de dónde sacaríamos esta energía? De hecho, si tuviésemos esta energía, probablemente sería más eficiente usarla en coches eléctricos. Aquí explican por qué hacerlo con aluminio y galio sería mejor que con boro, aunque tampoco esto funciona.

Muchas páginas conspiranoicas dicen que don Arturo "desapareció sin dejar el menor rastro", pero en la primera página de resultados de google se encuentra un video de uno de sus hijos explicando que murió con 82 años. Parece ser que fue el mismo Franco quien, tras un estudio del Colegio de Ingenieros Industriales, le dijo a Estévez que dejase de hablar del asunto, porque "ya se había hecho bastante el ridículo". Estévez, que venía de una familia de posibles pero se había gastado nueve millones de pesetas de la época en su invento sin que nadie le hiciera mucho caso, desapareció de la vida pública. A lo largo de su vida registró unas 100 patentes, pero ninguna de ellas estaba relacionada con el invento que le hizo famoso.

Tercera sorpresa, los conspiranoicos no tienen ni idea de lo que es una patente:

• Las patentes, como su propio nombre indica, son documentos públicos; es decir, si está patentado no es secreto, y si es secreto no está patentado. Por ejemplo, he aquí las patentes de Meyer: 5149407, 4936961, 4826581, 4798661, 4613779, 4613304, 4465455, 4421474, 4389981; todas ellas son variantes cada vez más enrevesadas de la idea de separar el agua en hidrógeno y oxígeno por electrólisis, y luego volver a juntarlos para obtener energía, así que no valen nada, pero supuestamente hay gente capaz de matar para ocultar estos documentos.
• Las patentes caducan al cabo de 20 años; a partir de entonces, todo el mundo puede hacer lo que quiera con ese invento.
• Se puede patentar una idea, sin tener que construir nada ni demostrar que funciona. Es decir, el que algo esté patentado no quiere decir que funcione.
• El que un invento tenga una patente vigente no quiere decir que no puedas hacerte uno en casa para investigar; simplemente quiere decir que si vas a explotarlo comercialmente tienes que ponerte de acuerdo con el inventor.
• Hay oficinas de patentes que aceptan todo sin leerlo. Si quieres patentar algo impatentable, bien porque es la rueda y no la has inventado tú, o bien porque es algo tan ridículo como la forma de balancearse en un columpio, lo único que tienes que hacer es ir a la oficina de patentes adecuada.

Cualquier persona que diga algo del tipo de "los malos compraron la patente y la escondieron" refiriéndose a algo que ocurrió antes de 1990 no está haciendo un gran esfuerzo por ser objetivo: las patentes no se pueden ocultar, así que cualquiera puede ir a la oficina de patentes más cercana y pedir una copia de la patente, que podrá usar libremente porque ya han pasado los 20 años (ojo, tendrá que darle datos suficientes a los trabajadores de la oficina, decirles "busco un invento fabuloso" no será suficiente).

Para acabar, mencionaré mis razones para pensar que nunca ha existido un motor de agua:

• Si empiezas con agua y acabas con agua, los principios de la termodinámica aseguran que no puedes obtener energía. Un motor que usase sólo agua y acabase produciendo agua sería un móvil perpetuo.
• Si fuese posible lo sabríamos; ¿alguien se cree que algo tan sencillo que supuestamente ya se hacía en el siglo XVIII se pueda guardar en secreto en los tiempos de Wikileaks? Por un lado nos dicen que hay personas redescubriendo el motor de agua cada año, pero por otro lado ninguno de estos genios sabe manejarse en Internet.
• Hay bacterias que viven de extraer energía de reacciones químicas realmente exóticas, pero todavía no ha aparecido una bacteria que extraiga energía simplemente del agua. Quizás la única forma de hacerlo es usar el hidrógeno en un reactor de fusión.
  
• ¿Cómo es posible que haya asociaciones ecologistas como Greenpeace que se dedican a chinchar todo lo que pueden a las empresas petroleras, y sin embargo no se ocupan de resucitar el motor de agua?



• Si las malvadas empresas petroleras se estuviesen tomando tantas molestias para ocultar el motor de agua, ¿cómo es que han dejado que el 21% de la energía generada en España sea eólica y el 5% fotovoltaica? ¿A lo mejor no saben que los coches eléctricos se podrán recargar con energía eólica? ¿Cómo se explica que los países comunistas tampoco tengan sus motores de agua?

Enlaces a páginas de problemas

El País está vendiendo una enciclopedia de matemáticas. En total son 30 libros, y cada semana aparece un título nuevo en los kioskos. Para promocionar esta oferta, cada semana ponen "el desafío" en la portada de El País Digital y sortean una enciclopedia entre todos aquellos que manden una solución correcta (las soluciones aparecen los martes y los problemas los jueves). Ahora en agosto han interrumpido este ritmo, simplemente han dejado de una vez los problemas de cinco semanas y ya se corregirán los deberes en septiembre. Conseguir la enciclopedia sería un problema, porque a ver dónde la uardo, pero los problemas son realmente bonitos y están muy bien seleccionados, echadles un ojo aquí.

Por otro lado, me han pasado la dirección de una página con problemas chulos: Acertijos y enigmas de ingenio. A continuación os copio los tres problemas que más me han gustado (posiblemente porque eran nuevos para mí).

• Un pastelero recibe tres cajas de caramelos opacas. Una de anís, otra de menta, y la tercera con una mezcla de las dos. Todas etiquetadas con su respectivos nombres. Más tarde recibe una llamada del proveedor diciendo que todas las cajas están mal etiquetadas. ¿Cuántos caramelos de cada caja deberá sacar como mínimo el pastelero para saber cuál es el contenido real de las cajas?
• El señor Norberto Ferrero padece una extraña enfermedad (conocida como " sindrome de Ferrero ") que hace que todos los días deba tomar dos pastillas, una del tipo A y otra del tipo B. Estas pastillas son exactamente iguales en peso, color, sabor, olor, tamaño, forma.. de modo que es imposible distinguirlas externamente y, sin embargo, es vital que Norberto se tome una pastilla de cada tipo cada día. Por eso, el señor Ferrero, muy organizado él, guarda las pastillas del tipo A en un pastillero marcado con la letra A y las pastillas del tipo B en un pastillero marcado con la letra B. Cada día, echa una pastilla del tipo A y otra del tipo B en su mano y se las traga. Pero hoy, después de echar la pastilla del tipo B, ha echado por accidente dos pastillas del tipo A en su mano, de modo que tiene 3 pastillas y no puede distinguir cual de las tres es la del pastillero B. Para colmo de males, Norberto no quiere simplemente tirar las pastillas y coger otras dos, pues son unas pastillas muy caras. ¿Qué debe hacer para tomar ese día y los días siguientes una pastilla de cada tipo sin equivocarse y sin desperdiciar ninguna? Pensadlo, no es un juego de palabras ni una tontería y aunque parezca imposible se puede hacer.
• El señor y la señora Mancha celebraron una fiesta en sus casa, a la que asistieron otras cuatro parejas. Cuando llegaron a la fiesta, algunos de los invitados (incluyendo a los señores Mancha ) estrecharon su mano con otros, pero naturalmente nadie le dio la mano a su pareja. Durante la cena, el señor Mancha preguntó a cada una de las otras 9 personas con cuántas había estrechado su mano. Sorprendentemente recibió 9 respuestas distintas. ¿A cuántas personas estrechó la mano la señora Mancha? ¿Y el señor Mancha?

Mathmania

En el momento de escribir estas líneas se está celebrando Mathmania, uno de los eventos de Codefest. Se trata de resolver en 5 horas el mayor número de problemas del mismo estilo que los del Proyecto Euler, es decir, son problemas que exigen saber tanto matemáticas como programar. En esta ocasión lo organiza IT-BHU, que no sé muy bien qué es, pero suena a departamento de Informática de alguna universidad, y hay premios que suman en total 30.000 rupias (unos 400 euros). Es curioso ver cómo a la cabeza de la competición van los mismos personajes que lideran los marcadores de la página del proyecto Euler; vaya abuso de los europeos (con permiso de Ucrania).

Yo me apunté, pero al final voy a pasar... otro año será.

Venus y la Luna

Venus y la Luna este anochecer, fotografiados desde la azotea de mi casa con una cámara cutre. La Luna parece estar en cuarto creciente, pero es un efecto de la sobreexposición necesaria para que se pueda ver Venus junto a ella. A la derecha, la misma Luna nueva sin sobreexponer.

Un dato sobre esta sobreexposición. El radio de la órbita de Venus es 0,72 veces el terrestre, de forma que la superficie de la Luna recibe la mitad de luz que la de Venus (0,72²). Sin embargo, el ángulo sólido subtendido por la Luna es unas 4.000 veces mayor que el de Venus, y esta diferencia de brillo hace que sea medio complicado meter a los dos en una misma foto.

Problema de geometría con cuatro puntos para el lector: ¿por qué es posible fotografiar a Marte cerca de una Luna llena, y sin embargo es imposible hacer lo mismo con Venus?

Suicidio homeopático

Hoy he participado en un acto de protesta contra los productos de una gran empresa farmacéutica multinacional, de esas que, en vez de buscar remedios contra enfermedades como la malaria, se dedica a comercializar remedios innecesarios en países occidentales.

Oh, pero no estoy hablando de una empresa que venda medicinas para lucrarse, sino de una que vende sacarosa a precio de medicina y va de "alternativa"; me refiero a Boiron, una farmacéutica especializada en homeopatía.

Parte del problema es que cada cual entiende una cosa diferente por "homeopatía"; y no, no es lo mismo que "medicina natural" o "plantas medicinales". La homeopatía es una pseudociencia muy concreta, basada en estos tres principios:

1. Aquello que causa los síntomas de una enfermedad, la cura. Por ejemplo, el insomnio se cura con cafeína.
2. Diluir mucho una sustancia en agua hace que su efecto sea más fuerte.
3. El agua guarda memoria de qué ha contenido.

Para más detalles, sugiero leer el artículo de la Wikipedia.

No sé muy bien cómo se ha organizado la protesta a nivel internacional; un colectivo llamado 10²³ (por el
número de Avogadro) promovió el evento, consistente en tomarse una sobredosis de medicamentos homeopáticos a las 10:23. Yo me enteré por una lista de escépticos. La convocatoria en Barcelona consistió en quedar en la fuente de Canaletas y tomarnos cada uno una caja entera de pastillas para dormir, en concreto Sedatif PC. Asistimos unos veinte suicidas y dos cámaras de TV3; ha sido una risa, nos hemos metido puñaos de pastillas en la boca, y por no pasar nada, no se han producido ni casos de somnolencia.

La cajita de 20 pastillas me ha costado 7,70 euros, o 20 céntimos la pastillita (al loro con el precio, las medicinas que funcionan son más baratas).

Leerse el breve prospecto es revelador. Cada pastilla de 300 miligramos tiene 225 mg de sacarosa, 72 de lactosa, una cantidad no divulgada de estearato de magnesio c.s.p., y 6 CH de varias hierbas. Cada CH consiste en diluir un volumen de un pricipio activo en 100 volúmenes de agua; como son 6, las hierbas de este preparado están diluidas en una parte en un billón, es decir, cada pastilla contiene unos 0,0000000000003 gramos de Aconitum napellus y otras cinco hierbas.

Para hacerse una idea de lo que es esto; el río Ebro tiene un caudal de 600 m³/s; si cada hora le echásemos dos centímetros cúbicos de Aconitum napellus, lo convertiríamos todo enterito en medicina homeopática. Esta es la razón por la que está prohibido que haya hierbas en los ríos.

Bueno, sigamos leyendo el prospecto:

• ¿Qué cura? Pues no es muy concreto que digamos; dice algo sobre trastornos emocionales, de ansiedad, y del sueño, pero ya está. Vamos, que si tienes insomnio, somnolencia, apnea o narcolepsia, tú te lo tomas y él ya averiguará qué quieres que te haga.
• ¿Qué efectos tiene? No se mencionan.
• ¿Contraindicaciones? "No se han descrito."
• ¿Efectos adversos? "Si se observa cualquier reacción no descrita en este prospecto, consulte con su médico o farmacéutico." Bueno, no sé de qué reacciones habla, porque el prospecto no menciona ninguna.
• Para suicidas: "Si usted ha tomado SEDATIF PC Comprimidos más de lo que debe, consulte inmediatamente a su médico o farmacéutico". Bueno, tan urgente no será, porque me he tomado veinte veces la dosis recomendada, y para más gracia ni me ha hecho falta un café después de comer. No aparece en ningún sitio ni un teléfono de urgencias, ¿es esto legal? No creo que se produzcan muchas intoxicaciones (a menos que seas intolerante a la lactosa, claro).

Las pastillas son dulces, lo de la sacarosa y la lactosa debe de ser verdad. Por lo demás, caca.

Para el futuro: hablando con los otros suicidas, parece que estábamos de acuerdo en que meterse con la homeopatía está bien, pero que ahora mismo la prioridad debería ser defender las vacunas. Podríamos empezar dando más publicidad a los brotes de paperas en Canadá.

Enlaces sobre el suicidio masivo del 5 de febrero de 2011:

• Barcelona
• Madrid
• Convocatoria de Sevilla
• Países donde se han organizado suicidios homeopáticos

Proyecto Euler

La principal razón por la que este blog está tan descuidado es que hay demasiadas tentaciones en la web. Mi último vicio es el proyecto Euler, http://projecteuler.net/, un sitio en el que van planteando problemas de matemáticas y programación que son bonitos, originales, con respuestas relativamente asequibles, y además corregibles.

Una cosa que tiene, buena y mala a la vez, es que puedes abrirte una cuenta y el sitio recuerda qué problemas has resuelto y te pone en una serie de tablas de clasificaciones; quiénes han resuelto más problemas, quienes los han resuelto antes, quienes participan en qué países...

El lado competitivo hace que el sitio sea adictivo, siempre te quedas con ganas de resolver un problema más para avanzar uno o dos puestos en alguna tabla. Pero es que esto tiene su lado ridículo. El viernes pasado me mandaron un mensaje avisándome de que el domingo a las dos de la madrugada hora española saldría el próximo problema. Cuando se me ocurrió mirarlo, el domingo a mediodía, ya lo habían resuelto unas cien personas. No sé, quizás es un pelín excesivo... pero claro, cada cual puede escoger hasta qué punto involucrarse.

Premio a Donald Knuth

Este blog tiene dos ídolos: Martin Gardner y Donald Knuth, que ayer apareció en los periódicos.

El matemático Donald E. Knuth gana el Premio Fundación BBVA Fronteras por convertir la programación informática en ciencia.

El Código de la Biblia

El 20 de diciembre va a ser el día del escepticismo, en rememoración de la muerte de Carl Sagan en 1996. El primer día del escepticismo se celebró el año pasado, y digamos que el acontecimiento no trascendió mucho.



Personalmente, los "días del X" siempre me han fastidiado un poquito, pero es que parece que cada vez hay más pseudociencias por todas partes. ¿Es esto simplemente paranoia? Creo que no; échese una ojeada, por ejemplo, a http://amazings.es/2010/12/19/experimentos-y-tendencias-en-google-labs/#comment-15379.

Así pues, quería escribir una entrada sobre el tema en este blog, y estaba pensando en qué batallita contar, ya que no hay muchas pseudociencias relacionadas con la programación. Y entonces me he acordado de la historia de El Código Secreto de la Biblia.

El origen de la historia es antiquísimo, siempre ha habido chiflados haciendo numerología con la Biblia; esos rollos de la cábala y el 666. En varias ocasiones me he topado con innumerados que creían que al ser yo matemático podría aclararles cosas como por qué las fechas importantes de su vida contienen un siete. Pista: si naciste en 1967, como yo, aproximadamente la mitad de las fechas de tu vida contienen un siete. Si tienes 3 fechas, lo más probable es que una de las cifras 3, 4, 5, 6, 7 o 8 aparezca en todas ellas; por no hablar del 9, que aparece en todas las fechas del siglo XX. Si tienes 9 fechas y te permites descartar tres "anomalías", lo más probable es que puedas quedarte con seis fechas con una cifra en común.

Cuando apuntas a la luna, el tonto se queda mirando el dedo.

Cuando señalas un número, el innumerado sólo ve cifras.

Cuando el cabalista mira una palabra, sólo ve letras, y esto es un misterio enormemente sofisticado que requiere muchos años de estudio.

Uno de las técnicas avanzadas de la cábala consiste en tomar una letra de, por ejemplo, cada siete letras de un texto, y buscar formas de conseguir formar nuevas palabras. Esto es bastante fácil en hebreo, porque las vocales no se escriben. Por ejemplo, la frase "ESTO NO TIENE SENTIDO, BURRO" se escribiría "STNTNSNTDBRR"; si empiezo en la segunda letra y tomo una letra de cada tres obtengo "TNTR", que obviamente me sugiere que estoy haciendo una ToNTeRía.

Generaciones enteras de cabalistas se quedaron ciegas buscando mensajes ocultos de esta forma en el Pentateuco (los cinco primeros libros de la Biblia, escritos por Moisés). Cuando aparecieron los primeros ordenadores en los años 60, varios matemáticos israelíes los usaron para buscar cosas, y claro, las encontraron; pero siendo matemáticos se abstuvieron mucho de decir que aquello significaba algo en concreto.

Esta situación de "laicismo matemático" no iba a durar mucho.

Primero fue el Rabí Weissmandl quien empezó a decir cosas poco prudentes; por ejemplo, afirmaba haber demostrado que la Biblia era la palabra de Dios, ya que nadie podría haber ocultado todos esos mensajes sin tener un ordenador. Y también descubrió cuál de las versiones del Pentateuco es la auténtica, ya que contenía un mayor número de ocurrencias cercanas de palabras como "martillo" y "yunque", y otros criterios similares. Lo gracioso es que otras personas usando el mismo procedimiento no llegaron a los mismos resultados; ¿quizás hay que hacerle una ceremonia de purificación a los ordenadores para que los programas funcionen correctamente?

Y luego apareció un periodista norteamericano aficionado a los misterios llamado Michael Drosnin que tenía muchas ganas de crear polémica. Drosnin habría sido simplemente un chiflado más si no fuese porque avisó en 1994 al primer ministro Isaac Rabin de que se produciría un atentado contra él; y, efectivamente, Rabin fue asesinado en 1995.

He aquí su hallazgo en la Biblia: http://www.2012supplies.com/what_is_2012/bible_code_2012.html.



Bien, no parece demasiado impresionante, especialmente si tenemos en cuenta que el nombre del asesino fue descubierto después del asesinato, y que hay que tomar una letra de cada 4.772 para conseguir las cuatro letras de Rabin.

Drosnin nunca se lo ha pensado mucho a la hora de publicar predicciones inquietantes; por ejemplo, en su primer libro sobre el código de la Biblia, en 1997, anunció que la civilización sería destruida en una guerra nuclear en 2000, y que luego Los Angeles sería rematado por la caída de un meteorito gigante en 2006. Pero cuando publicó su segundo libro, en 2002, la fecha del fin del mundo había sido desplazada a 2012. Drosnin, que es ateo, también ha leído en la Biblia que la Biblia fue escrita por unos extraterrestres, que enterraron un obelisco de acero cerca del Mar Muerto con la clave para descifrar la Biblia. Uno pensaría que Drosnin ya la ha descifrado pero, curiosamente, a pesar de ello hizo un viaje para encontrar el obelisco, sin éxito.

La lista de predicciones de Drosnin es muy larga, pero hasta la fecha sólo contiene una profecía cumplida, la de Rabin. También se le ha criticado por hacer varias trampas, como deletrear palabras usando mezclas creativas de hebreo clásico, hebreo moderno, y hasta abreviaciones del estilo de los SMS. Tras enzarzarse en una larga serie de disputas, en una famosa ocasión le espetó a un escéptico "a ver si encuentras predicciones de asesinatos en Moby Dick". Pues escuchado y hecho. Tras muchas horas de CPU invertidas en la búsqueda, se ha encontrado una bonita colección de profecías ocultadas por Herman Melville a mediados del siglo XIX en lo que simplemente parecía una novela. Unas cuantas de ellas se pueden ver en http://cs.anu.edu.au/~bdm/dilugim/moby.html; mi favorita es esta predicción de la muerte de Trotsky, que fue asesinado con un punzón de hielo.



Bueno, pensé que esta batallita encajaría bien en un blog con problemas de combinatoria.

Olimpiadas matemáticas II

A ver si resucito este blog ahora que vuelvo a tener algo de tiempo libre...

Un tal Harazi encontró una solución especialmente breve para el problema de la entrada anterior.

Como los enlaces dejan de funcionar con una facilidad pasmosa, repito aquí el argumento de Harazi. Empieza tomando un primo p tal que p-1 sea múltiplo de 4. Entonces p divide a algún número de la forma n²+1. La gracia está en ver que n puede ser pequeño; en concreto, podemos suponer que n<p/2, simplemente porque si p divide a n²+1 entonces también divide a (p-n)²+1. Sea k=p-2n>0; entonces p divide a 4(n²+1)=(p-k)²+4, de forma que también divide a k²+4 y por tanto k≥raiz(p-4). Por tanto, p=2n+k≥2n+raiz(p-4) y ya casi hemos acabado; para obtener la desigualdad final, p≥2n+raiz(p-4)≥2n+raiz(2n+raiz(p-4)-4), que es mayor que 2n+raiz(2n) si p es suficientemente grande.

Otras páginas relacionadas con este problema (encontradas por Roberto): solución 2 comentarios otro problema parecido.

Problema de las olimpiadas matemáticas

Olimpiadas matemáticas

Un amigo mío, Roberto, es doctor ingeniero aeronáutico y profesor, así que lleva una vida matemática interesante. Para él, los aviones no son cosas que vuelan, como para el resto de los mortales, sino cilindros que de metal que se van deformando. Hace mucho tiempo, a raíz de los atentados del 11S, tuvimos una charla sobre si un edificio que se está hundiendo puede girar sobre sí mismo; esencialmente, un edificio es una cosa que está hecha para aguantar su peso en una dirección concreta (la vertical), pero no en otras direcciones, de forma que lo normal es que si lo pones en una postura rara se deshaga por su propio peso. Podría parecer que lo que le gusta a Roberto es retorcer cosas con gente dentro, pero su inclinación natural es más bien evitar este tipo de cosas, por eso es ingeniero en vez de banquero. Bueno, el caso es que hace poco recibí por correo una bonita serie de fotos de un edificio volcado pero no roto, y acordándome de esta charla, se la reenvié.

El comentario de Roberto al ver estas fotos vino a ser algo así como "esto es lo que ocurre cuando haces un edificio con estructura muy dura y cimientos muy blandos". En realidad, sus palabras no fueron éstas, los ingenieros se cuidan mucho de pronunciar la palabra "duro" en vano.

Bueno, el caso es que aprovechando el intercambio de correos, Roberto me contó que había estado haciendo los problemas de la Olimpiada Matemática de 2008, y se le había resistido el tercero:

Demostrar que existen infinitos números n tales que n²+1 tiene un factor primo mayor que 2n+raíz(2n).

Es un problema muy chulo, porque está claro que es verdad, pero todos los ataques directos fallan frustrantemente, así que hay que dar un rodeo. A continuación voy a contar mi solución, que empieza siendo bonita pero acaba de una forma muy fea, la verdad, pero lo mismo quieres dejar de leer en este punto e intentar resolver el problema tú mismo.

Solución

Sea p un primo congruente con 1 módulo 4 lo suficientemente grande (luego veremos que basta que sea mayor que 29). Entonces p=a²+b², donde a y b son primos entre sí (de lo contrario p no sería primo), y por tanto existen dos números u y v tales que a*u+b*v=1. Entonces

p*(u²+v²) = (a²+b²)*(u²+v²) = (a*u+b*v)²+(b*u-a*v)² = 1+(b*u-a*v)²

Así que tomamos n=b*u-a*v y ya tenemos un n tal que n²+1 es un múltiplo de un primo p bastante grande para n. Demostrar que la cota p>2n+raíz(2n) se cumple es un poco feo porque iremos por casos; seguro que hay una forma inteligente de hacer esto rápidamente, pero yo no la he encontrado. Dejémosla por un momento para después y "acabemos" el problema. Para cada p construimos un n como antes. Observemos que todos estos n son diferentes entre sí; precisamente porque cumplen la cota, sabemos que su mayor factor primo es p, de forma que a cada p le corresponde un n diferente. Pero claro, hay infinitos p, de forma que también hay infinitos n como pide el problema.

Bien, pues ya hemos acabado, salvo por el detalle de demostrar la cota, cosa que haremos por casos.

El primer caso que tenemos que considerar es a=1 o b=1 (en el siguiente párrafo veremos por qué). Esto es fácil; si a=1, lo que haré es tomar u=1 y v=0, y por tanto n=b*u-a*v=b, con lo cual la desigualdad es cierta porque p = 1²+b² > 2b+raíz(2b) = 2n+raíz(2n) si b≥3, es decir, si p≥11.

Bien, ya podemos suponer que a>1 y b>1. Empezamos tomando u≅a^-1 (mod b) y v≅b^-1 (mod a), cosa que no podríamos hacer si a=1 o b=1, y por tanto 0≤u<b, 0≤v<a, y a*u+b*v≅1 (mod a*b). Como 0≤a*u+b*v<a*b+b*a=2*a*b, entonces o bien a*u+b*v=1, o bien a*u+b*v=a*b+1. En este segundo caso tiene que ocurrir que o bien u≥b/2 o bien v≥a/2, pero no pueden cumplirse ambas desigualdades, porque a*u+b*v sería demasiado grande; si se cumple la primera, lo que hago es escoger u=mod(a^-1,b)-b, y entonces ya se cumple a*u+b*v=1.

Así pues, ya podemos suponer que |u|≤b/2 y |v|≤a/2, y que u²+v²≤(a²+b²)/4. Pero me hace falta ajustar más.

Para eliminar el caso u=b/2 (los casos u=-b/2, v=a/2, v=-a/2 se hacen igual), tenemos que a*u+b*v=1 implica b*(a+2v)=2, con lo cual b es un divisor de 2. El caso b=1 ya lo vimos antes, así que podemos suponer que b=2. Entonces u=1, v=(1-a)/2, n = b*u-a*v = 2*1-a*(1-a)/2 = (a*a-a+4)/2, p=a²+b²=a²+4, y entonces p>2n+raíz(2n) se reduce a

a²+4 > a²-a+4 + raíz(a²-a+4)

a > raíz(a²-a+4)

a² > a²-a+4

que es cierto para a>4, es decir, para p≥5²+4=29. Por cierto, la desigualdad es muy ajustada; para p=29 sale a=5, b=2, u=1, v=-2, n²+1=29*5=145 luego n=12, y por tanto

29 = p > 2n+raíz(2n) = 24+raíz(24) = 28,8989

Así que ahora podemos suponer que |u|<b/2 y |v|<a/2; como estos cuatro números son enteros, esto quiere decir que |u|≤(b-1)/2 y |v|≤(a-1)/2; pero claro, no puede ocurrir que a y b sean impares a la vez, porque entonces el primo p=a²+b² sería par; luego sabemos que el caso |u|=(b-1)/2 y |v|=(a-1)/2 a la vez no puede ocurrir. Por tanto:

u²+v² ≤ (b-1)²/4 + (a-1)²/4 -1/4

donde el último 1/4 lo quitamos porque acabamos de ver que el caso u²+v²=(b-1)²/4+(a-1)²/4 no puede ocurrir. Como a+b≥raíz(a²+b²),

u²+v² ≤ (b²-2b+1+a²-2a+1-1)/4 ≤

≤ (a²+b²+1-2raiz(a²+b²))/4 = (raíz(a²+b²)-1)²/4

Bien, ya falta poco; recordemos que a²+b²=p y que p*(u²+v²) = n²+1, así que

p*(raíz(p)-1)²/4 = p*(raíz(a²+b²)-1)²/4 > p*(u²+v²) = n²+1

(p-raíz(p))² > 4n²+4 > 4n²

p-raíz(p) > 2n

raíz(p-raíz(p)) > raíz(2n)

p-raíz(p) + raíz(p-raíz(p)) > 2n + raíz(2n)

Como p>p-raíz(p), -raíz(p) + raíz(p-raíz(p)) es un número negativo, y por tanto

p>2n+raíz(2n)

Y vaya chasco de solución; con lo bonitos que eran los dos primeros párrafos...

Figuras autoparticionables I

Teníamos que hacer en el trabajo, para una editorial, algún ejercicio sobre sómo el área de una figura aumenta como el cuadrado de su perímetro, y me acordé de una cosa que me imagino que debí de leer en algún libro de Martin Gardner vete tú a saber cuándo.

La idea es que con dos escuadras se puede construir una escuadra mayor, cuyos lados son raiz(2) veces mayores que los lados de la escuadra original; y, esto ya es menos conocido, con tres cartabones se puede hacer un cartabón cuyos lados son raiz(3) veces mayores que los lados del cartabón original.

¿Hay más cosas así? Tras pasar unas cuantas horas emborronando folios, la respuesta es que sí, pero hay pocas figuras que sean realmente originales.

La primera solución trivial es que, para todo todo par de números a y b, se pueden juntar a*b rectángulos de lados raiz(a) y raiz(b), girados 90 grados, para obtener un rectángulo cuyos lados son raiz(a*b) veces mayores que el original.

Hay una solución de éstas que no es muy familiar, el caso a=1 y b=2; es la que usamos al partir por la mitad un folio DIN A4 y obtener dos cuartillas DIN A5 semejantes al original (ver http://es.wikipedia.org/wiki/Formato_de_papel).

Cuando multiplicamos el perímetro por un número entero, como 2 en vez de raiz(2), hay montones de soluciones. Para empezar están todos los rectángulos, rombos, y romboides con bases de igual longitud. Además, todos los triángulos se pueden descomponer en cuatro triángulos semejantes en una forma; los triángulos rectángulos pueden hacerlo en dos formas; y el cartabón puede hacerlo en cuatro formas distintas.

Y luego hay un puñado de soluciones medio interesantes, de las que hemos encontrado cuatro (en realidad, las dos últimas ya las conocía, seguro que están en algún libro de Martin Gardner).

Tengo que acabar aquí porque este blog sólo deja poner cinco imágenes por entrada.

Figuras autoparticionables II

Vamos a ver ahora un par de soluciones no triviales. Ojeando el libro de matemáticas del que tenía que hacer los problemas me encontré con un teorema que me imagino que alguna vez conocí pero conseguí olvidar absolutamente. Resulta que si tienes un triángulo rectángulo y trazas su altura, lo partes en dos triángulos que son semejantes al original. Es decir, en este dibujo

los triágulos ACB, ADC y CDB son semejantes. Esto viene muy bien para encontrar más soluciones de nuestro problema, porque basta con que nos aseguremos de que dos catetos encajan un número enteros de veces en la altura para que todos los ángulos coincidan maravillosamente; si se echan las cuentas, sale que podemos encontrar soluciones para todos los valores de a²+b². Por ejemplo, he aquí una solución en la que juntamos 13=2²+3² triángulos para obtener uno semejante 13 veces mayor:

En el lado izquierdo hay 4=2² triángulos, y en el lado derecho otros 9=3² triángulos. ¿No es precioso? He pintado de azul claro dos triángulos orientados de forma diferente a los demás para mostrar que en realidad ahí hay un montón de soluciones, tenemos unas cuantas formas de reorientar los triángulos; de hecho, si hubiese muchos triángulos de 2x3, podríamos girar 90º bloques cuadrados de tamaño 6x6, o girar rectángulos dentro de rectángulos; también podríamos mezclar los triángulos del lado derecho con los del lado izquierdo.

Más soluciones, pero bastante menos bonitas. Sean r, s y t tres números enteros (a ser posible mayores que 0 para no obtener soluciones triviales), y sean a, b y c tres números tales que

Entonces con 2r(s+2t) figuras L como las de la izquierda se puede construir una figura semejante como la de la derecha:

Un ejemplo. Para construir una L que se pueda juntar en grupos de 6, primero buscamos r, s y t tales que 6=2r(s+2t); por ejemplo, r=s=t=1. Luego buscamos b y c tales que b/c=s/t, podemos escoger b=c=1, y finalmente a = raiz(3/2). Nuestra solución es:

De esta forma se pueden generar soluciones no triviales para todos los números pares salvo 2 y 4.

Figuras autoparticionables III

Las siguientes soluciones son muy vistosas pero un pelín triviales.

El número de figuras que se juntan es 36, 16 y 4, todos ellos cuadrados, lo que viene a decir que no son demasiado originales. El truco es el mismo en los casos: encontrar una figura formada por triángulos equiláteros o cuadrados tal que al unirla consigo mismo, rotada 2, 3 o 4 veces, forme un triángulo equilátero o un cuadrado, que al repetirlo forma la imagen original ampliada. Las fichas marcadas en azul indican un truco para obtener más soluciones; también podríamos cambiar la orientación de las fichas dentro de cada triángulo o cuadrado, con lo cual parece que tenemos un montón de soluciones.

¿Que cómo se encuentran figuras así? Bueno, empezamos con un triángulo equilátero dividido de la forma obvia en, digamos, 36 triangulitos. Se escoge uno cualquiera de ellos y se tachan los dos triangulitos sobre los que cae al rotarlo 120º y 240º alrededor del centro del triángulo. Se escoge otro triangulito de entre los que quedan libres y se tachan los dos rotados. Y así hasta que no quedan triangulitos libres. En ese momento se han cogido 12 triangulitos que forman una figura que al ser rotada cubre todo el triángulo.

Yo he escogido una figura con forma de serpiente, por aquello de que parece que los motivos escherianos requieren animales, pero ¿de cuántas formas se puede hacer esto? El primer triangulito se puede escoger de 36 formas; el segundo de 33; el tercero de 30... Como el orden en que se escogen los 12 triangulitos no afecta el resultado, tenemos que dividir por 12!, y como la mayoría de las figuras resultantes no tienen ninguna simetría, hay que dividir por casi 6 para eliminar duplicados, con lo cual podemos obtener cerca de 88.500 soluciones en un triángulo dividido en 36; si lo dividiésemos entre 100...

(Observación: el que 36·33·30·...·3 / 12! sea igual a 3¹² tiene una bonita interpretación combinatoria: el efecto de la rotación es dividir los 36 triangulitos en 12 clases de equivalencia de 3 triangulitos, y tenemos que escoger un triangulito de cada clase.)

Cuando esto mismo se hace con un cuadrado, podemos eliminar el cuadradito a 180º de distancia, o los tres cuadraditos a 90º.

Pero, además de jugar con rotaciones, podemos usar simetrías axiales; el triángulo equilátero tiene tres ejes de simetría, y el cuadrado cuatro, con lo cual tenemos mucho campo para jugar. Pero los ejes de simetría parten la figura y las soluciones que salen no son demasiado bonitas.

Dejo como ejercicio para el lector encontrar la forma en que las siguientes figuras sirven para hacer soluciones repitiendo el original 8, 9, 16, 16, 16, 16, 36, 36 y 36 veces, de izquierda a derecha y de arriba abajo. No hará falta decir que las más interesantes son la primera, porque 8 no es un cuadrado, y la última, por lo curioso del agujero, que además hace que haya un montón de soluciones diferentes según el orden en que se "abotonen" los agujeros.

Todo esto está muy bien, ¿pero hay alguna solución en la que una figura se repita 7 veces, aparte del rectángulo trivial? Yo la he buscado hasta aburrirme, y estoy dispuesto a apostar un café a que no existe.

Solitario de rayas IX: Análisis del primer acotador

Para decirlo claro, el primer acotador no ha acelerado mucho la exploración del grafo. Comparemos el tiempo requerido para ir llegando a algunos puntos del árbol, los records, que son los datos que se guardan:

Record	Sin acotador	Primer acotador	Aceleración
82 líneas	141 s	170 s	-21%
89 líneas	390 s	456 s	-17%
anchura 16	1,45 h	1,51 h	-4%
98 líneas	10,26 h	10,06 h	2%
anchura 17	12,77 h	12,52 h	2%
110 líneas	2,09 días	2,09 días	0%

Es interesante ver cómo la aceleración va aumentando. Creo que lo que ocurre aquí es que cuando el récord es alto, prácticamente da igual qué cota se haya obtenido, va a servir para podar la rama. Veamos unos datos; en la siguiente tabla, las dos primeras columnas indican cuántas veces se había alcanzado un cota al llegar al récord de las 82 líneas (2,8 minutos), y el porcentaje de estas cotas que permitieron podar su rama. Las dos últimas indican lo mismo, pero al llegar al récord de 110 líneas (2,1 días).

cota	récord 82		récord 110
	n	% podas	n	%podas
0	570158	100%	729359516	100%
1	294770	100%	374383109	100%
2	91457	100%	146709781	100%
3	82384	93%	97683991	100%
4	54667	84%	58612396	100%
5	31394	75%	29856109	100%
6	11964	59%	13630824	99%
7	8677	58%	5863876	99%
8	5058	67%	2183517	99%
9	5943	50%	727533	97%
10	2032	37%	287890	97%
11	1992	18%	136358	95%
12	3117	16%	60526	92%
13	554	19%	9386	82%
14	163	10%	1496	63%
15	20	5%	76	38%
16	0	-	2	100%
966	311722	21% sobre total	426817220	23% sobre total
total	1476072	76%	1886323606	77%

Por ejemplo, antes de llegar al récord de las 82 líneas, hubo 20 ocasiones en que al calcular la cota se llegó a la conclusión de que se podían añadir como mucho 15 rayas más, y en sólo una de estas 20 ocasiones (el 5%) se pudo podar la rama. Pero después de explorar un número de vértices 1000 veces mayor, se obtuvo esta cota 76 veces, y de ellas el 38% permitieron podar su rama. Más llamativo todavía es el caso de la cota 16; sólo se obtuvo dos veces, pero ya avanzado el cálculo, y las dos cotas sirvieron para podar sus respectivas ramas. Vemos que todos los porcentages de podas aumentan, confirmando que, avanzada la búsqueda, la misma cota tiene mayor probabilidad de resultar en un poda, con lo cual aceleramos un poquito.

Pero si podamos tanto, ¿cómo es que no aceleramos muchísimo más? Bueno, es que en realidad no podamos tanto; el porcentaje de veces en que se poda una rama no sube apenas, pasa del 76% al 77%. Esto se debe a que en realidad aumenta el porcentaje de ocasiones en las que no se puede obtener una cota, en cuyo caso se devuelve la "cota de error" 966; este error pasa de ser un 21% del total de acotaciones a 23%.

Es decir, en el 23% de los casos el primer acotador pone demasiados puntos y acaba desbocándose. Nunca se han puesto 17 puntos sin que la cota se disparase hasta el infinito. Es verdad que no pasa gran cosa por no poder conseguir una cota ocasionalmente, pero es que este 23% es un desastre, y encima se produce con más frecuencia en las ramas gruesas, cuando hay más rayas que añadir. Éste es el problema, que en vez de podar ramas gruesas (digamos, de profundidad 40) lo que estamos haciendo es arrancar ramitas (cota 16 como mucho), y por esto no llegamos a acelerar de verdad.

(Podar ramas de cota 16 podría parecer mucho, porque así a ojo podría pensarse que contienen del orden de 2¹⁶ vértices; el problema es que incluso si siempre podásemos estas ramas, podríamos acelerar el programa en un factor de "sólo" 2¹⁶=65536, con lo cual no tardaríamos 25.000 millones de años sino sólo 381.000 años. Hombre, sería un progreso, pero no va a ser suficiente para resolver el problema en un tiempo razonable. Hay que podar ramas gruesas, y para ello el acotador tiene que ser capaz de calcular cotas grandes, y para ello no puede desbocarse cuando añada un número pequeño de puntos. Este es precisamente el fallo del primer acotador.)

¿Cuánto cuesta el acotador?

Usaré para comparar el récord de 110 rayas. Sin usar acotador, en 180.247 segundos se llegó a este récord, explorando 15.900.563.680 vértices, luego explorar un vértice cuesta 11,34 millonésimas de segundo. Usando el acotador, en 180.195 segundos se exploraron 10.201.449.392 vértices y se hicieron 1.886.323.606 acotaciones, luego una acotación cuesta en promedio 34,20 millonésimas de segundo. Así pues, una acotación cuesta tanto como explorar tres vértices.

La noticia buena es que el uso del acotador redujo el número de vértices explorados en un 36%. La noticia mala es que el 36% del tiempo se invirtió en calcular acotaciones.

Cada acotación eliminó un promedio de 3,02 vértices. Si nos pudiésemos olvidar de las acotaciones que produjeron cotas de 0 o 1 raya, que siempre son exactas pero representan una pérdida de tiempo, y también de las acotaciones que no consiguieron producir ninguna cota y que por tanto no eliminaron ningún vértice, nos encontraríamos con que las 355.763.761 cotas útiles eliminaron 5.699.114.288 vértices. No es mucho; esto quiere decir que por el coste de 3 vértices nos ahorraríamos 16. Esto podría parecer bueno, pero de nuevo no nos sirve; en el mejor de los casos esto nos permitiría acelerar el programa en un factor 16/3, con lo cual bajaríamos de 25.000 millones de años a 4.700 millones.

¿Qué precisión tiene el acotador?

Cuando el acotador nos dice que a una figura se le pueden añadir como mucho n rayas, ¿hasta qué punto está lejos del máximo real? Bueno, pues mucho. La siguiente tabla, generada tras unas 24 horas de CPU, viene a confirmar que este acotador no es muy preciso. Las columnas profundidad y vértices indican el tamaño de la rama podada. Los datos se refieren únicamente a las ramas podadas, de aquí que parezcan un poco raros.

cota	máximo real	profundidad	vértices
0	0	0	0
1	1	1.14249	2.2850
2	1.95974	2.30487	5.4617
3	2.50155	3.04756	9.4554
4	3.11749	3.93441	15.5819
5	3.52629	4.48573	22.7194
6	3.70997	4.77245	29.2670
7	4.02461	5.31142	39.1521
8	4.25367	5.80146	54.8526
9	4.43245	6.09479	69.5210
10	4.80206	6.83219	97.9958
11	4.07557	6.80793	93.4930
12	3.92569	7.14832	124.9150
13	3.66041	7.48019	102.2030
14	3.17198	5.63476	49.2213

Los datos para cotas mayores son completamente ridículos, en parte porque hay pocas ramas y al hacer la media puede salir cualquier cosa. Es un poco triste ver que el máximo real no llega a 5; y eso de que cuando la cota sea de 14 rayas en promedio sólo se puedan añadir 3 es para deprimirse. Pero al menos el número de vértices en las ramas podadas crece de forma parecida a 2^profundidad.

El lado bueno es que un acotador que acotase relativamente bien hasta el nivel de 10 rayas aceleraría el programa en un factor de al menos 100.

Conclusiones

1. El primer acotador es caro en términos de tiempo, pero no demasiado; falla por el lado de la precisión en vez de por el tiempo.
2. El problema no es exactamente que sea pesimista, sino más bien que con demasiada frecuencia no llega a producir una cota útil.
3. El segundo acotador debe evitar la posibilidad de pasarse poniendo puntos, y puede ser bastante más caro.

Solitario de rayas VIII: Record con 110 rayas

Usando el primer acotador, tras 2,1 días de CPU, y buceando hasta el nivel 134 del árbol binario, se ha encontrado este bicho con 110 rayas:

Se exploraron 10.201.449.392 vértices, se llamó al acotador 1.886.323.606 veces, y se podaron 1.459.117.650 ramas. La posición de esta figura en el árbol es 1111111111 1111111111 1111111111 0111111011 1110110111...; es decir, apenas se ha avanzado, tras dos días de CPU sigue en el bit 44 (42 efectivos), luego a este ritmo puede tardar unos 25.300 millones de años en acabar. Antes parecía que iba a bastar con la edad del universo, pero esto está empeorando.

Solitario de rayas VII: El primer acotador

Tengo que empezar admitiendo que medio he hecho trampas al poner este título; en realidad, ya he probado el primer acotador, así que ahora ya sé que habrá (al menos) un segundo acotador.

La idea es simple; este acotador funcionará en dos etapas:

1. añadir todos los puntos que se pueda.
2. averiguar el número máximo de rectas que pueden cubrir los puntos.

Ese "todos los puntos que se pueda" se complica un poquito. En realidad, el criterio que usa este acotador no es para añadir puntos, sino para añadir rayas; lo que pasa es que en cuanto decida añadir una raya, se va a olvidar de ella y va a añadir sus puntos. Éste es el criterio exacto:

1. Las rayas añadidas no pueden "pisar" las rayas que había puestas antes de llamar al acotador (sí pueden pisar las rayas puestas por el acotador)
2. Si la raya que se va a añadir tenía exactamente cuatro puntos marcados anteriormente, ninguno de estos puntos puede satisfacer:
   1. haber sido añadido por el acotador;
   2. tener todos sus enlaces usados en la dirección de la raya (en cualquiera de los dos sentidos);
   3. y tener al menos uno de esos enlaces pisado por la raya.

Como siempre, un ejemplo dejará claro qué quiere decir esto. Imaginemos que tenemos que acotar el número de rayas que se pueden añadir a esta figura:

Podríamos añadir una raya que cogiese el punto de la derecha, o otra que cogiese el de la izquierda, pero no ambas rayas. Bueno, pues este acotador en realidad no recuerda si ha añadido una raya o no, lo que ve es que podría añadir cualquiera de ellas, y va a añadir los dos puntos.

Hay que aclarar una cosa; si vemos sólo los puntos, ahora parecería que podríamos añadir dos rayas más, y luego otras dos, y luego otras dos... pero claro, esto haría que añadiésemos infinitos puntos, y no sería muy útil que nuestro acotador dijera siempre "como mucho puedes añadir infinitas rayas". Así que el acotador tiene que recordar cuándo no debe continuar añadiendo puntos. El criterio retorcido de arriba impide esto (si fuésemos a añadir una nueva raya, nos encontraríamos con que tendría 4 puntos marcados previamente y los puntos ahora en los extremos habrían sido añadidos por el acotador, tendrían su único enlace usado en la misma dirección de la nueva raya, y este enlace sería pisado por la nueva raya).

Entonces viene la segunda etapa del acotador. Tenemos seis puntos en fila; ¿cuántas rayas puede haber ahí? Obviamente, sólo una. Para poder poner dos rayas tendría que haber 9 puntos en fila.

Y ya hemos acabado; la cota es uno.

Lo bonito de este algoritmo es que hemos acotado el número de rayas que podemos añadir sin haber decidido qué rayas añadir. Lo malo es que a veces esta estimación va a ser muy mala. Veamos un ejemplo en que el acotador nos cuela una raya de propina; empezamos con esta figura:

El primer punto que añadiremos será S; de hecho, podemos hacerlo de dos formas, uniendo P-R o Y-N. Supongamos que unimos los puntos P-R, y por tanto el acotador recuerda (por el criterio) que no puede continuar añadiendo puntos en esa dirección, así que, de momento, U no se puede añadir.

Una vez hemos añadido S, resulta que podemos añadir T, uniendo Z-S.

Y sorpresa, ahora el criterio nos deja añadir U, porque resulta que ahora no todos los enlaces usados de S están en la misma dirección. Es decir; mientras conocíamos una única forma de llegar a S, el criterio nos impedía continuar en esa dirección; pero una vez hemos llegado a S en dos direcciones (desde N y R), como no se puede saber cual es "la primera", tenemos que dejar continuar en las dos direcciones.

Total, estamos en que el acotador ha descubierto que puede llegar a los puntos S, T y U. Esto es correcto, salvo por el detalle de que por las incompatibilidades entre rayas, se puede añadir o bien T o bien U, pero no ambos. Da igual, este acotador no recuerda incompatibilidades entre rayas. Así que a continuación decide que también puede añadir X; lo único que hay que hacer es añadir la raya T-X. Lo cual es falso...

Y entonces el acotador llega a su segunda etapa; estos son los puntos alcanzables:

que pueden albergar como mucho tres rayas; una horizontal (que se podría escoger de dos formas), una vertical, y una diagonal (que se podría escoger de dos formas). De forma que el acotador dirá que se pueden añadir como mucho 3 rayas cuando, en realidad, el máximo son dos rayas.

¿Es esto muy malo? Bueno, ya sabemos que un acotador rápido no puede ser muy preciso, así que si este acotado nos clavase sólo una raya de más estaríamos muy contentos. El problema es que una vez que empieza a añadir rayas incorrectamente se desboca y acaba añadiendo infinitas rayas incorrectas. Veamos un ejemplo "real"; empezamos con esta figura:

         *        *         
         |\      /|         
         | \    / |         
      *--#--#--#--#         
         |   \/   |         
         |   /\   |         
         #  *  *  #         
         | /    \ |         
         |/      \|         
         #        #         
        /|        |\        
       / |        | \       
#  #  #  #        #  #  #  #
                            
                            
#                          #
                            
                            
#                          #
                            
                            
#  #  #  #        #  #  #  #
                            
                            
         #        #         
                            
                            
         #        #         
                            
                            
         #  #  #  #         

(Perdón por volver a los gráficos en ASCII, pero es que la salida del acotador no la preparado para matlab...)

Vale, el acotador hace una primera pasada y encuentra que podría añadir 37 puntos:

            B        B            
            |\      /|            
            | \    / |            
         B--#--#--#--#            
            | / \/ \ |            
            |/  /\  \|            
         @--#--B--B--#--@         
           /| /    \ |\           
          / |/      \| \          
   @     B  #        #  B     @   
   |    /  /|        |\  \    |   
   |   /  / |        | \  \   |   
@--#--#--#--#--B--B--#--#--#--#--B
   | /                      \ | / 
   |/                        \|/  
   #                          #   
  /|                         /|\  
 / |                        / | \ 
@  #        @        B--B--B--#--B
   |\       |        |    /  /|   
   | \      |        |   /  / |   
@--#--#--#--#--B--B--#--#--#--#--@
   |   \    |     |  | /  /   |   
   |    \   |     |  |/  /    |   
   @     B--#--B--B--#--B--B--B--@
          \ |     | /| /          
           \|     |/ |/           
            #     B  #            
            |\   /| /|            
            | \ / |/ |            
         @--#--#--#--#--@         
            | / \/|  |            
            |/  /\|  |            
         @--B--B--B--B--@         

Pero claro, una vez ha añadido estos puntos, podría usarlos para añadir nuevas rectas; en la segunda pasada, el acotador cree que puede añadir estos 132 puntos:

            B  B  @  B  B               
            |\/|\  \/|\/|               
            |/\| \ /\|/\|               
            B--#--#--#--#  @            
           /|  |\/ \/|\/|\ |            
          / |  |/\ /\|/\| \|            
   B--B--B--B--#--B--B--#--B--B  B  B  @
    \ | /   |\/|\/ \/|\/|\/|\/| /| /| / 
     \|/    |/\|/\ /\|/\|/\|/\|/ |/ |/  
@     B--B--B--#--B--B--#--B--B--B--B--B
 \   /|\ |\/|\/|\/|\/|\/|\/|\/|\/| /| / 
  \ / | \|/\|/\|/\|/\|/\|/\|/\|/\|/ |/  
@--B--#--#--#--#--B--B--#--#--#--#--B--B
  / \ |\/|\/|\/|\/|\/|\/|\/|\/|\/|\/| / 
 /   \|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/  
B--B--#--B--B--B--B--B--B--B--B--#--B--B
 \ |\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/| /|
  \|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/ |
B--B--#--B--B--B--B--B--B--B--B--#--B--B
 \ |\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|
  \|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|
B--B--#--#--#--#--B--B--#--#--#--#--B--B
 \/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|
 /\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|
B--B--B--B--B--#--B--B--#--B--B--B--B--B
|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|
|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|
B--B--B--B--B--#--B--B--#--B--B--B--B--B
| /|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\/|\ |
|/ |/\|/\|/\|/\|/\|/\|/\|/\|/\|/\|/\| \|
B--B--B--B--B--#--#--#--#--B--B--B--B--B
| /| /|\/|\/|\/|\/|\/|\/|\/|\/|\/|\ |\ |
|/ |/ |/\|/\|/\|/\|/\|/\|/\|/\|/\| \| \|
B--B--B--B--B--B--B--B--B--B--B--B--B--B
| /| /| /|\/|\/|\/|\/|\/|\/|\/|\ |\ |\ |
|/ |/ |/ |/\|/\|/\|/\|/\|/\|/\| \| \| \|
B--B--B--B--B--B--B--B--B--B--B--B--B--B

La razón por la que esto tiene forma cuadrada es que el acotador busca nuevas rectas dentro de un cuadrado, que va ampliando según sea necesario. Como hace la búsqueda de arriba abajo y de izquierda a derecha, las nuevas rayas aparecen "barridas" hacia abajo a la izquierda. En las siguientes pasadas el cuadrado se va ampliando y las rayas acaban invadiendo todo el plano, así que cuando el acotador cree que puede añadir más de 200 rayas nuevas abandona y en vez de devolver una cota sobre el número de rayas devuelve un -1, que viene a decir "NPI".

Bueno, el que el acotador no acote ocasionalmente no es un problema demasiado grave; simplemente exploraremos ramas del árbol que quizás nos podríamos haber ahorrado. El problema sería que no consiguiese acotar con mucha frecuencia.

¿Pero cómo funciona en la práctica? Continuará...