 |
|
|
|||
 |
|||||
|
|
|
|
|||
|
|
|||||
|
Maurício Fabbri INTRODUÇÃO Recentemente, fui encarregado de ministrar um curso de matemática discreta, para uma turma de Engenharia. Essa disciplina é tida como uma das mais difíceis, e um dos motivos é que os alunos não estão habituados a raciocinar com aritmética, formas, enumeração... Claro, é mesmo uma disciplina desafiadora até para especialistas. Mas parece senso comum o fato de que uma das origens das enormes dificuldades dos alunos é que esse tema raramente é abordado logo cedo no ensino fundamental e médio. Ou então, é tratado de modo acadêmico e formal demais. A excelente coleção de matemática para o ensino médio da SBM (Lages Lima et. al, 2006) trata adequadamente desses assuntos, mas parece um tanto esquecida pela maioria das escolas, infelizmente. Os professores, que já se encontram sobrecarregados, encontram muita dificuldade em introduzir esses problemas nas aulas, ainda mais seguindo a abordagem tradicional. Talvez um motivo é o de que os jovens exigem hoje uma introdução mais visual, prática e sensorial ao assunto. Uma maneira de iniciar o tratamento de enumeração, já envolvendo recorrência e combinatória, é brincar com ladrilhos. Os probleminhas de preenchimento do plano com ladrilhos são atraentes, e mesmo crianças pequenas se envolvem facilmente com as atividades. Do ponto de vista matemático, é um dos mais fecundos, porque lida com geometria, álgebra, aritmética e... bem, até hoje se procura novas técnicas que permitam responder muitas questões importantes e complicadas. De quebra, pode-se introduzir conceitos importantes como notação posicional, listas, árvores, matrizes, entre outros. A intenção aqui é tentar uma exposição que possa ser acompanhada facilmente por qualquer professor ou aluno, mesmo que não tenha experiência alguma com o assunto. Por isso, inicio de maneira bem simples, fatalmente com algumas repetições do tratamento dos livros tradicionais. Espero que os pontos onde são introduzidas as ideias importantes estejam claros o suficiente. Não me dirijo apenas aos alunos ou professores mais preparados, mas mesmo esses, espero, devem encontrar algo de interessante nesta maneira de introduzir o assunto. Os problemas de ladrilhamento há muito tempo atraem a atenção dos matemáticos. Mesmo as questões mais simples levantam problemas que rapidamente se tornam complicados, exigindo técnicas avançadas de análise. Assim, iniciamos com atividades e perguntas simples, e evoluímos para situações que exigem a aplicação de conceitos matemáticos mais elaborados. Há assunto para todos os níveis, desde o início do ensino fundamental até desafios aos alunos mais avançados. ATIVIDADE INICIAL Um pedreiro deve fazer uma decoração em uma parede. Para isso, ele dispõe de ladrilhos vermelhos e azuis, como na figura. O ladrilho azul tem a mesma largura do vermelho, mas exatamente o dobro do comprimento (podemos chamar os vermelhos de ladrilhos 1 × 1 e os azuis de 1 × 2).
Uma escolha simples seria fazer uma faixa, de uma só linha, colando os ladrilhos um ao lado do outro. Por exemplo, abaixo temos uma faixa com 16 posições (casas), que o pedreiro pode preencher usando ladrilhos vermelhos ou azuis.
Se ele for preguiçoso, pode ser que preencha a faixa do modo mais simples. Ou todos vermelhos:
ou todos azuis:
Obviamente, se houvesse um número ímpar de posições, não daria para preencher a faixa toda apenas com ladrilhos azuis. Tentando ser um pouquinho mais artístico, ele poderia escolher
Ou talvez ele faça o serviço de qualquer jeito, por exemplo,
Seria interessante que o professor envolvesse a sala toda nesta atividade, porque muitos alunos tem dificuldade em entender o que se passa. Uma ideia é pedir a cada aluno que desenhe na lousa uma faixa diferente. Veremos logo adiante que, com essas 16 posições, podemos fazer 1597 faixas diferentes, de modo que há opções de sobra. Em uma sala com 20 ou mais alunos, logo vai aparecer o problema de verificar se uma nova faixa é realmente diferente das outras - isto é, essa atividade pode provocar a necessidade de uma sistematização na produção de faixas, e este é um passo importante para se resolver o problema matematicamente. CONTANDO AS FAIXAS DIFERENTES A pergunta que queremos responder é: quantas faixas diferentes podemos produzir com esses dois tipos de ladrilhos? Alguns alunos, com tendência mais artística e menos matemática, podem interpretar essa pergunta de modo inesperado. Ora, dizem eles, as faixas podem depender do gosto e da criatividade do pedreiro. Outros alunos ficam pensando sobre a quantidade de ladrilhos vermelhos e azuis - preocupam-se em gastar mais ou menos ladrilhos do que o permitido. O professor deve ficar atento a esse tipo de interpretação, que pode deixar o aluno fora do problema matemático. Uma maneira de evitar isso é pedir aos alunos que encontrem a resposta para faixas pequenas, simplesmente construindo cada faixa à mão. Mesmo isto não é tão simples como parece - o professor pode, se achar conveniente, ensinar aos alunos como sistematizar a produção de faixas. Sistematizar significa produzir as faixas, uma após a outra, de modo que nenhuma fique esquecida. Há várias maneiras de sistematizar a produção de faixas. Na verdade, isso é análogo a uma contagem com números no sistema posicional. Na figura ao lado, mostramos um modo de contar as faixas diferentes com cinco posições. O ladrilho vermelho é associado ao número 1, o azul ao 2, e uma posição não disponível ao número zero. É claro que, fazendo as coisas desse modo, o número 2 deve ser sempre seguido de zero.
Uma outra maneira de sistematizar, que é mais próxima do método que vamos utilizar no modelo matemático, é construir uma árvore de possibilidades. Ao lado, listamos o que pode acontecer iniciando do nada (nenhum ladrilho), e considerando que o próximo ladrilho pode ser vermelho ou azul. A árvore final tem oito folhas (folhas são os últimos vértices), que é a quantidade possível de faixas diferentes com cinco posições. MODELANDO MATEMATICAMENTE O PROBLEMA Vamos agora tentar prever o número total de faixas diferentes, sem contar uma a uma.
Consideremos antes alguns casos mais simples. Esses casos podem parecer óbvios, mas o professor deve estar certo de que nenhum aluno tenha dúvidas quanto a essas situações. Para início de conversa, se houver apenas um tipo de ladrilho, há uma única possibilidade - ou nenhuma, se os ladrilhos não puderem preencher a faixa. Assim, há um único modo de preencher uma faixa só com ladrilhos vermelhos. Se usarmos apenas ladrilhos azuis, ou há um único modo ou nenhum, dependendo da faixa ter um número par ou ímpar de posições. O professor deve deixar claro que não estamos distinguindo os ladrilhos do mesmo tipo entre si, uma vez que o resultado final é o mesmo independente de qual ladrilho individual foi usado. Ou seja, não nos interessa qual dos ladrilhos vermelhos foi usado, apenas o fato de que ele é vermelho. Se fosse para distinguir os ladrilhos todos uns dos outros, seria melhor iniciarmos já com todos os ladrilhos de cores diferentes, certo? Este é um dos pontos que mais causa confusão entre os alunos. Minha experiência mostra que, dependendo da turma de alunos e da insistência das perguntas, é melhor resolver de vez o caso em que os ladrilhos são todos distintos, para comparar com o caso em que estamos interessados. Não vamos entrar em muitos detalhes aqui, mas o professor pode mostrar de maneira simples que N ladrilhos distintos uns dos outros podem ser enfileirados de modos diferentes. Outro caso que tem uma solução simples é quando todos os ladrilhos tem a mesma forma, como os vermelhos e verdes abaixo:
Nesse caso, temos sempre duas possibilidades para cada uma das N posições da faixa, e então podemos produzir 2N faixas diferentes. Uma delas está abaixo:
Com essas 16 posições, o pedreiro poderia fazer 65 536 faixas diferentes. Quantas faixas diferentes poderiam ser feitas com os três ladrilhos?
O nosso problema com os ladrilhos 1 × 1 e 1 × 2
é um pouco mais complicado, porque um ladrilho azul bloqueia a casa seguinte. O raciocínio simples acima não funciona nesse caso. Então vamos mudar um pouco a pergunta. Quando a faixa é pequena (tem um número pequeno de casas), é fácil saber o número de faixas diferentes. O que acontece quando o número de casas aumenta? Ao invés de ficar escrevendo a mesma coisa toda hora, vamos introduzir uma notação.
Verifica-se que T1 = 1, T2 = 2 e T3 = 3. Pode até parecer meio maluco, mas T0 = 1. Porque há uma única maneira de preencher uma faixa que não tem casa nenhuma: é só não escolher nenhum ladrilho - portanto, um único modo. Agora, qualquer que seja a faixa, só há duas possibilidades: A figura abaixo mostra as duas possibilidades para uma faixa qualquer com n casas.
Mas, no primeiro caso, em que já colocamos um ladrilho vermelho na primeira posição, podemos preencher as n – 1 casas restantes de Tn- 1 modos diferentes. Analogamente, o segundo caso dá origem a Tn- 2 faixas diferentes. Logo, o número de faixas diferentes com n casas é: Tn = Tn-1 + Tn-2. (1) Acabamos de descobrir como saber o número de faixas diferentes à medida que aumenta o número de casas. Basta somar as duas últimas quantidades para obter a próxima. A fórmula (1) é uma relação de recorrência. Com calculadoras e computadores, é muito fácil encontrar o valor de Tn para valores bastante grandes de n.
A sequência Tn é a famosa sequência de Fibonacci É possível resolver essa relação de recorrência, isto é, obter uma fórmula direta para Tn em função de n. Não vamos fazer isso aqui – o leitor interessado pode consultar as referências ao final deste artigo, em particular a coleção de Lages Lima et. al. A fórmula fechada é muito interessante e importante, mas contém números irracionais, e seu uso para n grande introduz erros de arredondamento. Nos tempos atuais é fácil (e divertido) programar a fórmula (1) em uma calculadora ou computador. Por favor, confira o que dissemos na primeira atividade: com 16 casas, podemos fazer 1 597 faixas diferentes. FAIXAS DUPLAS Vamos considerar uma decoração mais elaborada, envolvendo duas faixa idênticas de ladrilhos, lado a lado. Temos agora um domínio 2 × n (duas linhas com n colunas).
Usando apenas ladrilhos vermelhos 1 × 1, podemos produzir um único padrão, como antes.
Mas, usando apenas os ladrilhos azuis 1 × 2 aparecem outras possibilidades, porque podemos agora colocar os ladrilhos deitados ou em pé.
Neste caso, o número de faixas diferentes pode ser encontrado usando a técnica de recorrência, como fizemos acima. A solução é exatamente a mesma que já encontramos antes (fica como exercício):
E se usarmos dois tipos de ladrilhos 1 × 2? Digamos, azuis e verdes?
Neste caso, cada ladrilho pode ser de duas cores. Então, a partir de cada configuração que geramos no parágrafo anterior, podemos gerar 2L faixas diferentes, sendo L o número de ladrilhos usados. Mas L = n, porque cada ladrilho ocupa exatamente duas casas. Portanto, teremos 2n.Tn faixas diferentes, sendo os Tn dados pela fórmula anterior.
Vejamos agora o caso mais interessante, com ladrilhos 1 × 1 e 1 × 2.
Vamos ainda usar a técnica de recorrência. Mas surge aqui uma nova dificuldade, porque se examinarmos as possibilidades de se colocar os primeiros ladrilhos, surgem novas formas de preenchimento. Os primeiros ladrilhos podem ser colocados das seguintes maneiras:
Os dois primeiros modos geram Tn - 1 possibilidades, e o terceiro, Tn - 2 possibilidades. Mas os dois últimos modos geram uma nova forma a ser preenchida. Vamos chamar de Rn o número de possibilidades de se preencher essa nova forma, quando se tem n colunas (sendo que a primeira coluna só tem uma casa). Desse modo, cada uma das duas últimas possibilidades da nossa lista geram Rn-1 faixas diferentes (note que as duas últimas formas se equivalem). Vamos obter uma relação de recorrência para Rn, procedendo como antes: verifiquemos as possibilidades para os primeiros ladrilhos nessa nova forma. Só há duas:
A primeira gera Tn - 1 possibilidades, e a segunda Rn - 1 . A partir das duas últimas figuras, obtemos duas relações de recorrência acopladas para Tn e Rn: Tn = 2Tn-1 + Tn-2 + 2Rn-1 → Rn = Tn-1 + Rn-1
T0 = 1, T 1 = 2, R0 = 1 e R1 = 1 (é melhor verificar que R1 = 1 fornece mesmo o resultado correto: R2 = T1 + R1 = 2 + 1 = 3). Mas ainda podemos obter facilmente uma fórmula envolvendo apenas os Tn. Basta escrever Tn + 1 = 2Tn + Tn-1 + 2Rn , subtrair a primeira das fórmulas acima e usar a segunda. Obtemos, finalmente, Tn = 3Tn - 1 + Tn - 2 - Tn-3 Essa relação é usada a par tir dos valores conhecidos (valores iniciais):
T0 = 1, T1 = 2 e T2 = 2T1 + T0 + 2R1 = Depois desse trabalho, é irresistível calcular alguns valores:
Apenas para conferência: se a nossa faixa da atividade 1 fosse dupla (2 x 16), poderíamos gerar 86.293.865 faixas diferentes usando os ladrilhos vermelhos e azuis. COMENTÁRIOS FINAIS Disponibilizei na web (em http://goo.gl/cFEbrs) um programinha para Windows que preenche murais m x n com ladrilhos 1 × 1 e 1 × 2. É útil para quem quiser brincar ou checar fórmulas. A matemática envolvida no preenchimento do plano com ladrilhos é muito rica, e a bibliografia sobre o assunto é extensa. Há desde livros recreativos elementares até tratados avançados, envolvendo pesquisa de ponta. Ladrilhos de formato mais geral são conhecidos por “polyominoes” (poliminós), e deram origem ao jogo tetris. Há muito material interessante nos livros de Martin Gardner e páginas ilustrativas na Internet (referências [2], [3] e [4]). A referência mais famosa no assunto é um livro de Golomb (referência [5]), infelizmente um tanto difícil de achar, a não ser por alguns exemplares nas bibliotecas das grandes Universidades. Um tratamento muito interessante e útil das relações de recorrência, talvez um tanto pesado, mas ainda ao alcance do ensino médio, é a Matemática Concreta de Graham, Knuth e Patashnik (referência [6]). Finalmente, fica aqui um aviso: essa é uma atividade extremamente viciante!
REFERÊNCIAS [1] LAGES LIMA, E.; CARVALHO, P.C.P.; WAGNER, E.; MORGADO, A.C. A Matemática do Ensino Médio, Vol. 2. 6a ed. Rio de Janeiro, SBM, 2006. [2] WEISSTEIN, E.W. Polyomino. MathWorld – A Wolfram Web Resource. (Disponível em http://mathworld.wolfram.com/Polyomino.html) [3] KODAMA, H.M.Y. e SILVA, Aparecida F. da. Poliminós. Em: Garcia, W.G. e Guedes, A.M. (Org.). Nucleos de Ensino – 2003.1a ed. São Paulo: UNESP Publicações, 2004, V.1, p. 268-289. [4] WIKIPÉDIA, 2014. (Disponível em http://en.wikipedia.org/wiki/Polyomino) [5] GOLOMB, S.W. Polyominoes: Puzzles, Patterns, Problems, and Packings. Princeton University Press, 2nd. ed., 1996. [6] GRAHAM, R.L.; KNUTH, D.E. e PATASHNIK, O. Matemática Concreta. Rio de Janeiro, LTC, 1995. |
