Determine o número de modos de cobrir um tabuleiro
com dominós
iguais.
Passo 1
O enunciado pede para contar de quantas formas podemos cobrir um tabuleiro de
usando apenas dominós de tamanho
. Esse é um problema clássico de contagem de tilings que leva a uma recorrência de Fibonacci.
Passo 2
Definimos
como o número de maneiras de cobrir um tabuleiro de
. Nosso objetivo é achar uma fórmula ou recorrência para
.
Passo 3
Considere as possibilidades de cobertura envolvendo a primeira coluna (mais à esquerda) do tabuleiro de
:
- Podemos colocar um dominó vertical ocupando toda a primeira coluna. Nesse caso, o restante a cobrir é um tabuleiro
, que pode ser feito de formas. - Podemos colocar dois dominós horizontais empilhados, ocupando as duas células da primeira e da segunda coluna. Nesse caso, sobra um tabuleiro
, que pode ser coberto de maneiras.
Passo 4
Somando essas duas possibilidades, obtemos a relação de recorrência
Passo 5
Agora precisamos das condições iniciais. Para
(tabuleiro vazio) há exatamente uma forma de “cobrir” (não colocar nada), ou seja,
Para
(um tabuleiro
) só cabe um dominó vertical, logo
Passo 6
A sequência
satisfaz
Isso é exatamente a definição dos números de Fibonacci deslocados, de modo que
onde
é a sequência de Fibonacci usual com
,
. Em forma fechada temos também
Resposta
O número de modos de cobrir um tabuleiro
com dominós
é
sendo
o
-ésimo número de Fibonacci.