Um tabuleiro com uma casa faltando

A figura

Um tabuleiro de lado $2^n$ com uma casa arrancada — qualquer uma — é coberto por peças em forma de L, de três casas. A figura mostra a construção: o tabuleiro é cortado em quatro quadrantes, uma peça vai para o centro ocupando uma casa de cada quadrante cheio, e os quatro quadrantes viram o mesmo problema, menor. As cores marcam o nível da recursão.

A conta

O número de casas restantes, $4^n-1$, tem de ser múltiplo de 3 para caberem peças de três casas — e é:

$$4^n-1=(4-1)(4^{n-1}+\cdots +4+1)=3(4^{n-1}+\cdots +1).$$

Mas contar não basta (contar não diz se as peças encaixam). É a indução que garante: o caso 2 × 2 é uma peça só, e cada tabuleiro se resolve com quatro tabuleiros menores mais a peça do centro. O resultado é de Solomon Golomb, de 1954, que também inventou o nome “poliominó”.