Sea [math]n un entero positivo. Se tiene un tablero cuadriculado de [math]4 \times 4n dividido en casillas de [math]1\times 1, y [math]4n piezas como la que se muestra en la figura. Determinar de cuántas maneras se puede cubrir totalmente el tablero con estas piezas.
Ttetra - Copy.png
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
Tenemos el tablero vacío:
0000000...
0000000...
0000000...
0000000...
Llamo [math]T(n) a la cantidad de formas de llenar un tablero de ancho [math]4*n. Voy a hacer una recursión.
Sea la casilla [math](i,j) la casilla de la columna [math]i empezando desde la izquierda, y la fila [math]j empezando desde abajo. Veamos que hay dos maneras de ubicar una ficha de modo que cubra la casilla [math](1,1).
La primera:
0000000
0000000
0100000
1110000
Luego, la casilla [math](1,2) podemos llenarla de una sola manera:
2000000
2200000
2100000
1110000
Lo mismo pasa ahora con la [math](2, 4), estamos obligados a llenarla así:
2333000
2230000
2100000
1110000
Ahora, la casilla [math](3, 2) se puede cubrir en principio de tres formas:
2333000
2234000
2144000 ====> Si tenemos calculada T(n-1), sumamos a T(n) ese valor ya que acá cubrimos el cuadrado de 4x4.
1114000
2333000
2234000
2144400
1110000 ==> Acá no podemos cubrir la casilla [math](4,1), entonces no es una configuración válida.
2333000 ----------------------------------------------------------------------------------------------> 23335777
2230000 -------------------------------------------------------------------------------------------- -> 22355570
2144400 ====> Sólo podemos cubrir la casilla [math](4, 3) y la casilla [math](5, 1) así: 21444600
1114000 ----------------------------------------------------------------------------------------------> 11146660
Y ahora nuevamente, podemos o "cerrar" el rectángulo de [math]4x8, donde a [math]T(n) se le suma [math]T(n-2), o no. Si no lo cerramos, tendremos una situación como cuando podíamos cerrar o no el cuadrado de [math]4x4, ya que se ve que una de las opciones no es válida para seguir, y la otra nos deja una "L" invertida arriba, y una casilla suelta abajo (como luego de agregar la ficha número [math]4 en este caso.
Luego tenemos que cubriendo la casilla [math](1,1) como mencionamos en este caso, a [math]T(n) se le suma [math]T(n-1) + T(n-2) + ... + T(0),
donde [math]T(0)=1 ya que al completar el tablero, esa forma en la que lo completamos suma [math]1 a [math]T(n).
La otra manera de completar la casilla [math](1,1) es así:
0000000
1000000
1100000
1000000
Si hacemos el procedimiento como antes, viendo al principio que las casillas [math](1,4) y [math](2,1) tiene una sola forma de completarse, llegaremos a la misma fórmula que antes (1). Por lo que se obtiene que:
Vemos por ejemplo que [math]T(1) = 2, ya que son las dos formas que concuerdan con "cerrar" los cuadrados de [math]4x4 según los dos casos de cómo cubrir a la casilla [math](1,1). Esto coincide con la fórmula.
A partir de ahí, vemos que [math]T(2)=2*(2+1)=6, [math]T(3)=2*(6+2+1)=18, [math]T(4)=2*(18+6+2+1)=54, y podemos ver que hasta ahora, agrandar en [math]1 a [math]n nos da el triple de soluciones.
Entonces intentemos demostrar que [math]T(n)=3*T(n-1) para [math]n>1. Esto podemos verlo rápidamente viendo que: