 |
|
|
|||
 |
|||||
|
|
|
|
|||
|
|
|||||
| Cláudia
S.Tavares
Nosso objetivo neste artigo é descrever, de forma breve, o desenvolvimento da Análise Combinatória, do Stomachion aos modernos problemas da Teoria dos Grafos.
Essa história bem que poderia estar num livro de fábulas de La Fontaine. Explicamos: apesar de difundida, ela não corresponde fidedignamente aos fatos ocorridos.
Só para citar algumas, aos quatorze anos escreveu um tratado sobre as seções cônicas, aos dezoito inventou a calculadora, três anos depois formulou um resultado físico, hoje conhecido como Princípio de Pascal, que diz que a pressão aplicada a um fluido dentro de um recipiente fechado é transmitida, sem variação, a todas as partes do fluido, bem como às paredes do recipiente. Mais tarde ajudou a fundar uma nova área da Matemática, a Probabilidade, e foi também o primeiro a pensar em um sistema de ônibus e organizar uma companhia de transporte público. Segundo, o triângulo de Pascal já era conhecido pelo árabe Al-Kajari, no século XI, e pelo chinês Chu Shï-kié, que nos deixou a mais antiga apresentação preservada do triângulo, datada de 1303. Em 1653, Pascal escreveu o seu Traité du Triangle Arithmétique e o publicou dois anos mais tarde. Nele encontramos os triângulos numéricos, construídos de uma forma diferente da que habitualmente usamos hoje: a partir da segunda linha, cada elemento é obtido como soma dos elementos da linha anterior situados à esquerda ou exatamente acima do elemento:
E, terceiro, recentemente descobriu-se que o estudo de combinatória remonta à antiguidade clássica, mais precisamente ao tempo do grande Arquimedes (287 a.C - 212 a.C), um dos que, juntamente com Newton e Gauss, formam a tríade dos maiores matemáticos de todos os tempos. Dentre os trabalhos publicados por ele encontra-se um que sempre aguçou a curiosidade de matemáticos e historiadores. Trata-se do Stomachion, aparentemente um jogo, semelhante ao conhecido Tangran, constituído de quatorze peças que devem ser encaixadas para formar um quadrado:
O motivo de tanta curiosidade acerca de um simples jogo era exatamente esse, como pôde um simples jogo ter despertado a atenção de uma das mais brilhantes mentes da história? Bem, segundo o matemático Leibniz (um dos fundadores do cálculo diferencial), "Não há homens mais inteligentes do que aqueles que são capazes de inventar jogos". E, para surpresa de todos, em dezembro de 2003, o jornal americano The New York Times publicou um artigo intitulado In Archimedes Puzzle, a New Eureka Moment, sobre os resultados da pesquisa do historiador de Matemática Reviel Netz, da Universidade de Stanford, Califórnia, em que ele afirma que o Stomachion não era um mero passatempo, mas um objeto executado por Arquimedes para fins de Análise Combinatória. Mais especificamente, a conclusão de Netz é que Arquimedes desejava determinar de quantas formas distintas poderiam ser encaixadas as 14 peças para formar o quadrado. A resposta recentemente provada dessa questão pode ser 17 152 ou, desprezando-se as soluções simétricas, 268, o que nos parece mais razoável, e não se sabe ao certo se o próprio Arquimedes obteve essa resposta. De qualquer forma, o fato fundamental é que a origem da Análise Combinatória não se encontra no estudo do binômio de Newton, como se acreditava, mas mais uma vez remonta à genialidade de um homem que sempre esteve à frente de seu tempo, Arquimedes. Dando um grande salto no tempo, voltemos ao binômio (a + 1)n. Como sabemos, ele está diretamente relacionado ao triângulo de Pascal. Em um tratado publicado em 1654, Pascal mostrou como utilizá-los para achar os coeficientes do desenvolvimento de (a + b)n. A grande contribuição do inglês Isaac Newton (1646-1727) ao binômio foi ter mostrado, numa carta a Oldenburg, em junho de 1676, como calcular (a + 1)n diretamente, isto é, sem ter que recorrer a (a + 1)n-1, e ter generalizado esse resultado para (a + b)q, em que q = m/n. A fórmula obtida para a sua expansão é usualmente conhecida como Binômio de Newton devido à sua grande contribuição. Um grande desenvolvimento da Análise Combinatória ocorreu devido aos problemas originados com os jogos de azar. Os jogadores queriam achar maneiras seguras de ganhar em jogos de cartas, dados ou moedas. Entre eles, podemos citar o cavalheiro De Meré, um homem que ficou na história como escritor. De Meré discutia com Pascal problemas relativos à probabilidade de ganhar em certos jogos de cartas e dados. Um dos problemas era saber qual o número mínimo de vezes necessário para que se obtenha um "doble seis" (6 e 6) no lançamento de 2 dados um certo número de vezes. Estava nascendo então a teoria das probabilidades, terreno fértil para o desenvolvimento de novas técnicas da Análise Combinatória. Pascal correspondeu-se com Pierre de Fermat (1623-1662) sobre o que hoje chamaríamos de probabilidades finitas. Outros grandes matemáticos, como Galileu (1564-1642), Jaime Bernoulli (1654-1705), Euler (1710 -1761) e Laplace (1749-1827), se interessaram pelo assunto e contribuíram grandemente para seu desenvolvimento. O genial Leonard Euler, já citado, teve um papel
destacado. É responsável pelo símbolo
Consta que o matemático francês Phillipe Naudé enviou uma carta a Euler, em que questionava sobre "de quantas formas é possível escrever um número inteiro como soma de inteiros positivos", ao que Euler teria prontamente respondido com a então batizada pelo próprio Euler "partitio numerorum". O problema de se determinar o número p(n) de partições de um inteiro positivo n foi objeto de estudos durante um longo tempo, e uma fórmula para seu cálculo só apareceu no século XX, fruto do trabalho de G. H. Hardy, S. Ramanujan e H. Rademacher. Por exemplo, p(4) = 5 e p(5) = 7, como o leitor poderá verificar sem dificuldade. Mais tarde, em 1736, Euler resolveu um problema que intrigava os matemáticos de sua época. Na Prússia, região leste da Alemanha, havia uma cidade chamada Königsberg, famosa por suas sete pontes, cinco das quais ligavam o continente a uma ilha. O problema consistia em saber se era possível dar uma volta pela cidade passando uma e somente uma vez por cada ponte, o que Euler provou ter resposta negativa.
Estava dado um dos pontapés iniciais para a Teoria dos Grafos, fundada por Euler, G. Kirchhoff e A. Cayley. No ano de 1834, o alemão Peter Gustav Lejeune
Dirichlet (1805-1859) formulou o princípio das gavetas, apresentado
no Teorema 1, em cujo enunciado a notação
Teorema 1 Se m objetos são colocados em n
gavetas, com m > n, então ao menos uma gaveta
contém Esse princípio aparentemente ingênuo é um dos recursos mais utilizados para resolver problemas de combinatória (e não raro surge em outras áreas da matemática). Citamos aqui um curioso exemplo, que poderia ser chamado de Teorema do Cabeleireiro.
Exemplo 1 Numa cidade com mais de 2 milhões de habitantes existem mais de dez com a mesma quantidade de fios de cabelo. Demonstração Esse fato é verdadeiro levando-se em conta o fato de que nenhum ser humano chega a ter 200 000 fios de cabelo, pois para tanto as dimensões da cabeça do indivíduo teriam que ser descomunais... Assim, se criarmos 200 000 gavetas, numeradas de 0 a 199 999, e colocarmos em cada gaveta os moradores da cidade com tantos fios de cabelo quanto o número indicado na gaveta, então teremos uma gaveta com pelo menos Dirichlet nasceu na cidade de Duren e sua família é oriunda de Richelet, o que explica seu sobrenome. Johann foi aluno de ninguém menos que Gauss, o Príncipe dos Matemáticos. Conta-se que, por ocasião dos cinqüenta anos de doutorado de Gauss, houve uma celebração, e o ponto alto da festa seria quando Gauss acenderia seu cachimbo usando, para tanto, parte dos originais das Disquisitiones Arithimeticae, sua obra-prima. Vendo a cena, Dirichlet não pôde se conter, avançou sobre Gauss, tomou-lhe das mãos os originais e guardou-os para si, justificando que a queima das Disquisitiones seria, no mínimo, um grande sacrilégio. Outro problema interessante na Análise Combinatória que envolve Teoria de Grafos é o Problema das Quatro Cores, cuja interpretação é acessível a qualquer pessoa, mesmo que não tenha conhecimentos matemáticos. Simplesmente consiste em determinar quantas cores serão necessárias para colorir um mapa de maneira que países adjacentes não tenham a mesma cor. Essa questão surgiu em 1852, quando Francis Guthrie tentava colorir um mapa da Inglaterra. Guthrie, que foi advogado, botânico e, sobretudo, matemático, tinha um irmão mais novo, Frederick Guthrie, que era aluno de Augustus De Morgan (o De Morgan das conhecidas leis de De Morgan, na Lógica), para o qual apresentou a conjectura. Mas apenas em 1976, com a ajuda de um computador IBM360, Kenneth Apel e Wolfgang Haken resolveram o problema de forma definitiva e completa. Outros matemáticos, como Birkhoff e Heesch, contribuíram com idéias que ajudaram no sucesso da demonstração, que tem importância histórica porque constituiu a primeira demonstração matemática feita com a ajuda de um computador. A Análise Combinatória atualmente continua a crescer, principalmente na computação. Os pesquisadores dessa área podem tratar problemas que são difíceis de resolver por métodos analíticos, mas que podem ser simulados em computadores potentes que levam a obter elementos que ajudem à sua compreensão e levam à formulação de conjecturas, senão mesmo à sua resolução A seguir estão alguns problemas clássicos que perturbaram mentes importantes e que deixamos como desafio para o leitor. Exercício 1 Mostre que, se nós tomarmos 10 pontos do interior de um triângulo eqüilátero, de lado 3, pelo menos dois pontos ficarão a uma distância menor do que 1, um do outro. Exercício 2 Provar que todo inteiro positivo pode ser expresso de maneira única como soma de potências distintas de 2.
Exercício 3 Com três dados, o número 9 e o número 10 podem ser obtidos de seis maneiras distintas, cada um deles. No entanto, a experiência mostra que 10 é obtido mais freqüentemente que o 9. Explique esse fato.
Exercício 4 Problema do viajante: dados n pontos no plano ou no espaço, como uni-los de modo que o caminho total seja o mais curto possível?
Exercício 5 Em abril de 1975, Martin Gardner (1914- ... ) apresentou um mapa, com 110 regiões, e dizia que, para aquele exemplo, seriam necessárias cinco cores. Seria, assim, um contra-exemplo, colocando em dúvida o Teorema das Quatro Cores. Esse ato não passou de uma brincadeira realizada no "Dia das Mentiras". Tente também colorir esse pretenso contra-exemplo de Martin Gardner.
Referências bibliográficas [1] CAJORI, Florian. A History of Mathematical
Notations. Mineola: Dover, 1993.
|
Primeiro,
Pascal, ou melhor dizendo, o matemático francês Blaise Pascal
(1623-1662) notorizou-se não só pelo triângulo que
leva seu nome, mas por diversas contribuições valiosas à
Matemática e à Ciência, em geral.
Stomachion
, representando o que hoje conhecemos por 
, o coeficiente binomial. Foi ele o fundador da teoria das partições.
Uma partição de um inteiro positivo n é uma
coleção de inteiros positivos cuja soma é n.
Por exemplo, o número n = 3 tem exatamente três partições:
representa a parte inteira de a, isto é, o maior
número inteiro menor ou igual a a (por exemplo,
).
objetos.
pessoas.
