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 V: Simetrías

He modificado el programa para que vaya escribiendo en un fichero el vértice del árbol que está explorando cada vez que explore diez millones de vértices (esto es unos dos o tres minutos). Así puedo interrumpir y rearrancar la búsqueda. Uno podría pensar que esto es necesario por si los apagones, pero no, la experiencia demuestra que el factor limitante aquí son las actualizaciones de Windows: cada semana mi ordenador se tiene que bajar una actualización de seguridad crítica doble rojo fosforito, y luego se reinicia.

El poder empezar a calcular a partir de una figura guardada en disco tiene una importante ventaja, y es que seleccionando varias figuras desde las que empezar podemos recorrer sólo las soluciones realmente diferentes del problema, en vez de recorrer todo el árbol ocho veces a causa de las simetrías.

Por "simetrías" me refiero a dos reflexiones (horizontal y vertical) y una la rotación de 90 grados (rotar 180 grados equivale a reflejar primero horizontalmente y luego verticalmente).

Es decir, estas dos figuras no son iguales entre sí porque no se puede convertir la una en la otra aplicando simetrías

pero estas ocho sí:

porque podemos convertir cualquiera de ellas en las otras aplicando simetrías.

(Por cierto, ¿habrá alguna figura no trivial que bajo una traslación vaya a parar a alguna figura simétrica? Es decir, que permanezca esencialmente invariante bajo una traslación. Es una pregunta tan inútilmente retorcida que lo mismo la pensaré; parte del problema será definir qué significa "no trivial", porque hay figuras así con hasta cuatro rayas.)

La mayoría de las figuras aparecerá por octuplicado, pero algunas figuras tienen alguna simetría (es decir, al aplicarles una de las simetrías caen exactamente sobre sí mismas) y aparecerán cuatro, dos, o incluso una única vez; por ejemplo:

Lo que interesa para ahorrar tiempo es no encontrar ocho veces las figuras que no tienen ninguna simetría; parece razonable pensar que las figuras con alguna simetría serán una minoría minúscula, y por tanto no nos preocuparemos de ellas.

¿Qué tiene todo que ver con leer de un fichero en el disco duro la posición desde la que se debe continuar la búsqueda? Bueno, imaginemos que queremos buscar algo en todas las figuras que tienen exactamente una de las ocho rayas de la izquierda (se ven sólo "cuatro rayas largas" porque las ocho se solapan a pares). Entonces arrancaríamos el programa empezando desde la posición de la izquierda, en la que la raya verde estaría incluida y las seis rayas negras estarían excluidas, es decir, en la lista de rayas que no se deben incluir:

Cualquier figura que tenga exactamente una de las ocho rayas podrá ser rotada y reflajada de una única manera para coincidir con estas condiciones. No es necesario indicar que la última raya (arriba a la derecha) no debe ser incluida, porque al tener que incluir la de la izquierda ya lo impedimos.

Esto funciona muy bien para el caso en que haya una única raya de esas ocho, ¿pero qué ocurre si hay dos o más, o ninguna? Me equivoqué al decir que debería ser fácil evitar todas las figuras duplicadas, porque los otros casos han resultado ser complicadillos, y hay que empezar a subdividirlos.

Es decir: el problema general, buscar en todas las figuras, primero lo dividimos en cinco casos, y cada uno de estos casos lo subdividimos en los subcasos que sean necesarios:

1. Las figuras que tienen exactamente una de las ocho rayas. Es el caso bonito, analizado arriba, y sólo requiere un subcaso sin simetrías.
2. Las figuras que no tienen ninguna de las ocho rayas. Tiene un subcaso muy trivial en el que no ganamos nada porque todas sus figuras siguen apareciendo por octuplicado.
3. Las figuras que tienen exactamente dos de las ocho rayas. Tiene cinco subcasos, cuatro de ellos con simetrías, mencionados más abajo.
4. Las figuras que tienen exactamente tres de las ocho rayas. Tiene tres subcasos sin simetrías.
5. Las figuras que tienen exactamente cuatro de las ocho rayas. Tiene cuatro subcasos, uno con una simetría y otro con dos.

(No es posible tener más de cuatro de esas rayas porque cada vez que incluimos una, excluimos otra.)

Por ejemplo, el caso en que haya exactamente dos de esas ocho rayas puede ser subvidivido ineficientemente en estos cinco subcasos, de los que cuatro tienen simetrías (indico en azul el eje de simetría):

Obviamente, es malo que los subcasos que vayamos a usar tengan simetrías, porque permitirán que algunas figuras encajen en ellas de varias maneras.

Una forma de arreglar esto sería dividir estos subcasos con simetrías en más sub-subcasos, pero de todas formas no nos acabamos de librar de las simetrías.

¿Es esto muy malo? He echado unas cuentas suponiendo que la probabilidad de que aparezca una línea en un par de líneas solapadas es 1/3, y la probabilidad de que no aparezca ninguna es 1/3. Esto es muy discutible, pero como he construido los casos usando las primeras líneas, que "normalmente se ponen", no parece del todo equivocado. Me sale esta tabla, donde "m" se refiere al trabajo mínimo, es decir, el número de vértices que se explorarían si se evitasen todas las epeticiones:

número de casos	trabajo total	trabajo repetido
1 caso	m * 8	m * 7
14 casos	m * 1,4321	m * 0,4321
36 casos	m * 1,1728	m * 0,1728
93 casos	m * 1,0795	m * 0,0795
235 casos	m * 1,0387	m * 0,0387
579 casos	m * 1,0192	m * 0,0192

Uf. Bueno, a pesar de sean números aproximados, sugieren que el trabajo duplicado es proporcional al logaritmo del número de casos dividido entre el número de casos.

No me veo arrancando un programa 579 veces para ahorrarme un 2% de trabajo, hay algo contradictorio en esta frase. De repente, la opción de dejar que el ordenador trabaje por octuplicado no parece tan mala. A menos que aparezcan cientos de voluntarios pidiendo ramas para buscar en paralelo, me parece que intentaré dividir el problema en 14 casos, y ya está.

Quizás las cosas no tengan que ser tan complicadas; yo he examinado los casos a partir de esas ocho rayas iniciales, pero ¿sería posible escoger otras rayas que hiciesen más fácil el análisis? Quién sabe; yo las he buscado y no las he encontrado. Por feo que parezca todo esto, me temo que es lo que hay.