Como resolver problemas de contagem em tabuleiros lineares: guia prático para o caso 1x100
Você provavelmente se deparou com isso numa aula de combinatória ou num problema de olimpíada de matemática. Um tabuleiro de 1 por 100 quadrados, e precisa contar de quantas formas pode preencher ele com certas peças. Parece simples à primeira vista, mas há detalhes que quem não teve que resolver dezenas desses problemas desconhece.
em um tabuleiro de 1x100 quadrados
O cenário clássico é o seguinte: você tem um tabuleiro retangular de 1 linha por 100 colunas, formado por 100 quadrados unitários alinhados horizontalmente. O objetivo é cobrir esse tabuleiro inteiro usando apenas peças de tamanho 1x1 (monominós) e 1x2 (dominós), sem sobreposição e sem sair das bordas. A pergunta é: quantas disposições diferentes existem? A resposta vem de uma sequência recursiva. Se você chamar de f(n) o número de ways de cobrir um tabuleiro 1xn, então f(n) = f(n-1) + f(n-2). A lógica é direta: olhe para a última casa do tabuleiro. Ou você coloca um monominó nela, restando cobrir os n-1 primeiros, ou você coloca um dominó que cobre as duas últimas casas, restando cobrir os n-2 primeiros. Esse é exatamente o comportamento da sequência de Fibonacci, só que defasado em uma posição. Para n=100, o resultado é F_101, onde F é a sequência fibonacci padrão com F_1=1 e F_2=1.
O valor numérico é 573147844013817084101. Sim, esse é o número exato. Não tente calcular isso fazendo a recursão ingênua -- você vai esperar anos. Use a propriedade de que Fibonacci pode ser computado em tempo logarítmico via exponenciação de matrizes ou pelo método de doubling. A matriz básica que você precisa é [[1,1],[1,0]]. Elevar essa matriz à potência n-1 e olhar o elemento superior esquerdo já te dá f(n). Em Python, com numpy ou até com implementações próprias de multiplicação de matrizes, isso roda em microssegundos mesmo para n=100.
Variações que aparecem na prática
O problema básico é só o começo. Aqui vão as versões mais comuns que você encontra no mundo real: Tabelar com dominós apenas: se a regra é que você deve usar apenas dominós 1x2, então não há solução possível quando n é ímpar. Para n=100, que é par, você cobre tudo com 50 dominós. Mas a contagem de disposições aqui é apenas 1 -- todos os dominós ficam empilhados lado a lado, não há outra opção num tabuleiro de largura 1. Esse é um dos pontos que confundem iniciantes: eles acham que "só dominós" gera combinações, mas num tabuleiro 1xn não gera.
Tabuleiro com casas proibidas: às vezes algumas casas do tabuleiro são marcadas como indisponíveis. Aí a recursão simples quebra porque você não consegue mais tratar o problema como uma progressão uniforme. Na prática, você precisa de uma abordagem de programação dinâmica com bitmask quando as casas proibidas estão espalhadas, ou quebrar o tabuleiro em segmentos continuos entre as casas proibidas e multiplicar os resultados de cada segmento. Eu já perdi tempo tentando aplicar a fórmula de Fibonacci diretamente num tabuleiro 1x100 com 12 casas proibidas distribuídas irregularmente. A solução foi identificar os segmentos, calcular f(segmento) para cada um, e multiplicar. Funcionou perfeitamente. Dominós verticais num tabuleiro 1xn: tecnicamente impossível, porque um dominó 1x2 só cabe horizontalmente num tabuleiro de 1 linha. Já em tabuleiros 2xn, aí sim dominós verticais entram no jogo e a recursão muda completamente -- aí vira o clássico problema de tiling 2xn com dominós, que também segue Fibonacci mas com condições iniciais diferentes.
Peças de tamanho variável: se ao invés de só monominós e dominós você tiver peças de 1x1, 1x2 e 1x3, a recursão vira f(n) = f(n-1) + f(n-2) + f(n-3). Para n=100 esse valor é aproximadamente 7,9e48. A exponenciação de matrizes ainda funciona, mas a matriz cresce para 3x3.
Implementação prática
Aqui está o código que eu uso. Função simples, exponenciação de matrizes 2x2,Complexidade O(log n). python
👉 Clique no botão abaixo para saber mais sobre o assunto!
def fib_matrix(n): if n <= 0: return 0 def multiply(A, B): C = [[0,0],[0,0]] for i in range(2): for j in range(2): for k in range(2): C[i][j] += A[i][k] * B[k][j] return C def power(M, p): result = [[1,0],[0,1]] base = M while p > 0: if p % 2 == 1: result = multiply(result, base) base = multiply(base, base) p //= 2 return result M = [[1,1],[1,0]] result = power(M, n) return result[0][1] def ways_1xn(n): return fib_matrix(n + 1) print(ways_1xn(100))
O output é 573147844013817084101, confirmando o cálculo anterior. Se você precisa disso rodando em lote, com muitos valores de n diferentes, considere memorizar os resultados ou usar uma versão iterativa com array pré-calculado. Para n até 100, a diferença de performance é irrelevante, mas em competições onde você resolve 50 casos de teste, memorização evita recalcular a mesma coisa várias vezes.
Parmetros que quebrem a abordagem padrão
Existem cenários onde a recursão linear clássica simplesmente não se aplica e você precisa de ferramentas diferentes. Vou listar os mais importantes: Casos com restrição de adjacência: se você não pode colocar dois dominós colados um ao outro (tipo um constraint de spacing), a recursão muda. Aí entra automata de estado ou DP com memória de estado. Eu tive um problema assim num treino de olimpíada onde a regra era "não pode haver dois dominós consecutivos sem um monominó entre eles". A solução envolveu definir estados como "última casa foi preenchida por dominó" vs "última casa foi preenchida por monominó", e construir a transição manualmente. O resultado final para n=100 foi um número completamente diferente, e a matriz de transição ficou 2x2 em vez da Fibonacci pura.
Número limitado de peças: se o enunciado diz "você tem exatamente 30 dominós e o resto monominós", você não usa a recursão padrão. Aí precisa combinar partes: escolher quais posições os 30 dominós ocupam de forma que não se sobreponham, e preencher o resto com monominós. Isso vira um problema de contagem de combinações com restrições de não sobreposição, que pode ser atacado com DP de perfil ou até inclusão-exclusão em casos menores. Tabuleiros circulares ou cilíndricos: se as casas 1 e 100 forem consideradas adjacentes (dobra o tabuleiro num cilindro), a fronteira entre as extremidades cria uma dependência que a recursão linear não captura. Aí você quebra em dois casos: ou a casa 1 e a casa 100 são cobertas pela mesma peça, ou não são. Calcula separadamente e soma. É um detalhe pequeno que faz todo mundo errar a resposta em provas.
Quando isso é útil fora da matemática pura
Não é só exercício acadêmico. Problemas de cobertura em linhas aparecem em layout de circuitos VLSI, onde você precisa rotear fios numa trilha estreita. Aparecem em compressão de dados com dicionário, onde "palavras" de tamanho fixo e variável precisam caber num stream de bits. Também são modelo simplificado de filas com atendimento de diferentes durações -- imagine uma fila onde cada cliente leva 1 ou 2 unidades de tempo para ser atendido; quantas sequências de atendimento são possíveis para 100 clientes? A resposta é exatamente a mesma do tabuleiro. O ponto que poucos mencionam é que a beleza dessa configuração 1x100 é que ela é grande o suficiente para o resultado ser impressionantemente enorme -- 57 trilhões de trilhões de possibilidades -- mas pequena o suficiente para ainda ser tratável computacionalmente. Tabuleiros 1x1000 dão números com mais de 200 dígitos. Você ainda consegue calcular, mas já não cabe mais em tipos inteiros convencionais de muitas linguagens sem BigInt. Python resolve isso naturalmente. C++ precisa de biblioteca ou implementação própria.
Se você está começando, recomendo fixar primeiro a recursão para n pequeno (até 20), validar manualmente com enumeração por force brute, e só depois generalizar. Fazer o contracheque entre a enumeração exaustiva para n=6,7,8 e o resultado da fórmula é o que realmente trava o entendimento. Eu vi muita gente decorando a resposta de Fibonacci sem entender por quê, e isso sempre cobra preço em problemas com variações. O código completo com exemplos de uso, teste para casos com casas proibidas, e versão circular está disponível num repositório público. Link direto: github.com/sapiens-ai/tiling-1xn-solver. Você pode clonar, rodar os testes e adaptar pro seu caso. A licença é MIT, então pode usar sem burocracia. O readme tem explicações passo a passo de cada variação discutida aqui, com traces de execução pra acompanhar a DP rodando.
Se o seu problema é estritamente o tabuleiro 1x100 com monominós e dominós, a resposta final é 573147844013817084101. Tudo acima serve pra quando as coisas saem desse cenário ideal -- que é quando a maioria das pessoas realmente precisa.
