De quantas formas diferentes podemos cobrir um tabuleiro de
com peças de dominós que cobrem exatamente duas casas do tabuleiro?
Passo 1
O problema pede: “De quantas formas diferentes podemos cobrir um tabuleiro de
usando peças de dominó
?”
Conteúdo: isso é um clássico de contagem e recorrência (também envolve a sequência de Fibonacci).
Para resolver, vamos precisar:
Conteúdo: isso é um clássico de contagem e recorrência (também envolve a sequência de Fibonacci).
Para resolver, vamos precisar:
- Definir a quantidade de maneiras como uma função
. - Encontrar os casos base (pequenos
). - Ver por que aparece uma relação de recorrência
. - Identificar essa recorrência como Fibonacci e, se quisermos, dar a fórmula fechada.
Passo 2
Definição e casos base.
Seja = número de maneiras de cobrir o tabuleiro
.
Seja
- Para
(tabuleiro vazio) só há 1 jeito (não colocar nada): - Para
(duas células uma em cima da outra) só cabe um dominó na vertical:
Passo 3
Montando a recorrência.
Olha o que acontece no lado esquerdo do tabuleiro :
Olha o que acontece no lado esquerdo do tabuleiro
- Se a primeira peça for vertical, ela ocupa as duas células da coluna 1, sobrando um tabuleiro
. São jeitos de completar o resto. - Se a primeira peça for um par de dominós horizontais, um na linha de cima e outro embaixo, eles ocupam as colunas 1 e 2. Sobra um tabuleiro
, que pode ser preenchido de maneiras.
Somando as opções:
Passo 4
Reconhecendo a sequência de Fibonacci.
Aquela relação
Aquela relação
é exatamente a definição da sequência de Fibonacci deslocada. Se
é a sequência clássica com
,
, então dá para mostrar que
Por exemplo:
-
e . -
e .
Passo 5
Fórmula fechada (opcional).
A fórmula de Binet para Fibonacci é
A fórmula de Binet para Fibonacci é
Logo
Resposta
O número de maneiras de cobrir um tabuleiro
com dominós
é
onde
é o
-ésimo número de Fibonacci (ou, em forma fechada,
).