Primalidad

La siguiente fórmula es un testeador de primalidad:

[Update: no había aclarado que los corchetes simbolizan la función "parte entera de"]

Para j > 1, vale 1 si j es primo, y 0 si j es compuesto.

Vi la fórmula en A Passion for Mathematics, de Clifford A. Pickover, que a su vez lo cita de Mathematical Mysteries, de Calvin Clawson.

Clawson dijo sobre ella: «Es verdaderamente asombrosa. ¿Cómo sabe si su argumento es primo o compuesto?»

Y realmente es asombrosa. Lástima que no es fácil de evaluar para valores grandes de j…

Si lo dicen ellos…

Fernando Chorny me comenta de este estupendo chiste paradojal publicado en Página 12.

Pseudo-laberinto: Solución

(Update: pongo aquí una imagen que puede clarificar la solución)

Luego de un tiempo prudencial, publico aquí la solución del acertijo.

La clave es que en cada pseudo-laberinto no traspasable debe haber una cadena continua de paredes que una los bordes izquierdo y derecho, bloqueando el camino. Si a ese pseudo-laberinto lo transformamos adecuadamente, obteniendo su “dual”, obtendremos uno que que es traspasable (siendo uno de los caminos posibles el correspondiente a la cadena de paredes del original).
Y recíprocamente: el dual de cualquier pseudo-laberinto traspasable será no traspasable (tendrá una cadena de paredes correspondiente a alguno de los caminos que hacían al original traspasable).

Por lo tanto, hay igual cantidad de pseudo-laberintos traspasables y no traspasables; por lo tanto la probabilidad de que uno de ellos generado al azar sea traspasable es de .

Carlos y Santiago habían enviado comentarios acertados sobre esta solución; no los publiqué en el momento para no arruinar el placer de los que leyeran antes el acertijo.

Iván delineó hace unos días el siguiente (delicioso) esquema de demostración:

Si lo publicaste en Bucles, debe ser un acertijo bucloso; por lo tanto…

Y acertó: aunque no lo considero estrictamente bucloso, la solución que doy más arriba tiene definitivamente el olorcillo adecuado…

Pseudo-laberinto

Este acertijo (en realidad esta es una pequeña variante) me lo comentó Luis Silvestre, que a su vez lo escuchó de una persona que se dedica a estudiar problemas de percolación.

Tenemos un tablero cuadriculado de N+1 casillas de ancho y N casillas de alto. En cada segmento del tablero (tanto los que separan casillas como los del borde) ponemos, o no, una pared, según el lanzamiento de una moneda (o sea, con probabilidad 1/2). De esta forma, el tablero quedará transformado en una especie de pseudo-laberinto.
¿Qué probabilidad habrá de que se pueda entrar en el laberinto por arriba y salir por debajo?

Hay, seguramente, soluciones analíticas elaboradas, pero también hay una solución “simple y gloriosa”, como dice Luis; encontrarla es muy placentero. En unos días la publicaré.

Cuando sea grande

Cuando sea grande, quiero ser como yo.

(frase de un amigo en su mensajero instantáneo)

Oración

Señor, por favor no permitas que recupere mi fe.

(frase adaptada de un excelente cuento de Greg Egan)

Acertijos buclosos

Pregunta: ¿Qué tienen en común un gorrión, un reloj de pared y un trébol de cuatro hojas?
Respuesta: Que los tres son mencionados en este acertijo.

Este horripilante cazabobos es especialmente tonto; sin embargo, hay otros acertijos buclosos que son más interesantes.

Por ejemplo, aquellos cuya solución puede (o debe) hallarse suponiendo que hay una solución, o que la solución es única. Un buen ejemplo sería el de los apretones de manos, que tiene una solución laboriosa convencional y otra elegante, que podemos encontrar cuando nos damos cuenta de cierta simetría.

Otra posibilidad es que el acertijo no incluya algún dato crucial, y en cambio se nos diga que alguien pudo (o no) resolverlo usando este dato. En este tipo de acertijos, llamados meta-acertijos, el experto indiscutido es Raymond Smullyan (su libro Alice in Puzzle-Land hay algunos realmente buenos).

¿Se les ocurre alguna otra buclosidad aplicable a los acertijos?