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.