Florestas Racionais e Círculos Tangenciais

Florestas Racionais e Círculos Tangenciais Marisa da Costa Cardoso Oliveira Mestrado em Matemática para Professores Departamento de Matemática 2014 Orientador Samuel António de Sousa Dias Lopes, Professor Auxiliar, FCUP insira uma figura alusiva ao tema Todas as correções determinadas pelo júri, e só essas, foram efetuadas. O Presidente do Júri, Porto, ______/______/_________ I Agradecimentos Ao meu orientador, professor doutor Samuel Lopes, pela inspiração, disponibilidade, cumplicidade e pelo apoio em todos os momentos. À professora doutora Maria Leonor Moreira por me ter ouvido e apoiado sempre que precisei. Ao professor José Carlos Santos pela disponibilidade imediata em me ajudar a construir algumas imagens no Geogebra. Às minhas amigas, Paula, Ana João, Cláudia e Sandra, pela ajuda e pela força que me deram nos momentos mais difíceis. A todos os outros que não nomeio mas que, de alguma forma, contribuíram para que este objetivo se realizasse. Ao meu amigo Edgar por ter idealizado e construído comigo a capa desta tese. Ao Marco por, juntamente com o Zé, me ter impulsionado a tirar o mestrado. Aos meus pais por me terem ensinado a nunca desistir de um sonho e por me terem ensinado a importância do desenvolvimento constante do conhecimento. Ao Zé e aos meus filhos, José Henrique e Pedro Filipe, por tudo o que representam na minha vida, pelas horas em que estive isolada, pelos maus humores que suportaram e pelas brincadeiras estratégicas que inventaram para a mamã poder trabalhar, sobretudo quando o papá esteve ausente. II Resumo Este trabalho visa explorar conceitos básicos de uma forma rigorosa mas acessível a todos os professores de matemática, tendo como objetivo, não só expor os temas em questão, mas também levar o leitor a levantar outras questões e, assim, desafiá-lo a construir conhecimento matemático. O Capítulo 1 aprofunda conhecimentos ligados às frações, conceito abordado já no 1º ciclo, e introduz uma operação menos conhecida, a mediante de duas frações irredutíveis, que terá um papel ubíquo neste e nos restantes capítulos desta tese. O capítulo dois apresenta uma interpretação geométrica de alguns dos conceitos do primeiro capítulo. O conceito de fração mediante, fortemente referido no primeiro capítulo, volta a ser abordado no Capítulo 2, de uma forma surpreendentemente diferente. No Capítulo 3, como introdução aos dois capítulos seguintes, apresentar-se-á uma breve introdução à teoria dos grafos. Neste capítulo, pretende-se mostrar não só a relação desta teoria com o quotidiano, como introduzir o conceito específico de árvore, conceito a explorar mais alargadamente nos Capítulos 4 e 5, em que são mostradas diferentes formas de enumerar os números racionais, cada uma delas com um conjunto distinto mas interessante de propriedades. Uma dessas formas de enumerar os racionais é recorrendo à árvore de Stern-Brocot, que é estudada no Capítulo 4 e que se baseia nas sequências de Farey, já apresentadas no Capítulo 1. A outra enumeração que apresentaremos dos racionais é baseada noutra árvore designada por árvore de Calkin-Wilf e numa sucessão de contagem relacionada com o sistema de numeração binário. Palavras chave: Enumeração dos Racionais, Fração mediante, Sequência de Farey, Círculo de Ford, Grafos, Árvores, Árvore de Stern-Brocot e Árvore de Calkin-Wilf. III Abstract This thesis aims to explore basic concepts from an underlying rigorous perspective, at the same time employing straightforward terminology comprehensible to teachers. It also sets out not only to explain the topics under study, but also to lead readers into raising their own mathematical questions, thus challenging them into enhancing their mathematical knowledge. The first chapter is concerned with fractions, a topic which is already taught to primary school students. Nonetheless, it introduces a lesser-known operation, the mediant of two irreducible fractions, which will also play an extended role in the chapters that follow. Chapter two presents a geometrical interpretation of some of the concepts focused on in Chapter one. The concept of a mediant fraction, strongly highlighted in Chapter one, is once more approached in the second chapter, however from a surprisingly different perspective. Chapter three, serving as an introduction to the following two chapters, also provides a short introduction to the theory of graphs. The objective of this chapter is not only to the explore the relationship between graph theory and certain concrete real-world applications, but also to introduce the concept of a tree, which will be largely used in Chapters four and five, in which different but interesting ways of enumerating the positive rationals are shown, each bearing its own set of properties. One of these ways of enumerating the positive rationals relies on the the Stern-Brocot tree, studied in Chapter four of this thesis, and which is closely related to the Farey sequences presented in Chapter 1. The other type of enumeration of the positive rationals which is presented here is based on another tree, the so-called Calkin-Wilf tree, as well as on a counting sequence related to the binary system. Keywords: Enumeration of the rationals, Mediant, Farey Series, Ford Circles, Graph, Tree, Stern-Brocot tree, Calkin-Wilf tree. IV Índice Resumo ................................................................................................................................. II! Abstract .............................................................................................................................. III! Lista de tabelas e figuras ..................................................................................................... 5! Introdução ............................................................................................................................ 6! Capítulo 1: Sequências de Farey ........................................................................................ 8! 1.1. Sequências de Farey e Frações Mediantes ............................................................................... 8! 1.2. A função φ de Euler .............................................................................................................. 13! 1.3. Determinação do termo que sucede a dois termos consecutivos ........................................... 19! 1.4. Relação unimodular e irreducibilidade das mediantes .......................................................... 21! Capítulo 2: Círculos de Ford ............................................................................................ 26! Capítulo 3: Teoria de Grafos ............................................................................................ 37! Capítulo 4: Árvore de Stern-Brocot ................................................................................. 46! Capítulo 5: Árvore de Calkin-Wilf ................................................................................... 59! Conclusão ............................................................................................................................ 77! Bibliografia ......................................................................................................................... 78! 5 Lista de tabelas e figuras Tabela 1 ................................................................................................................................ 27! Tabela 2 ................................................................................................................................ 47! ! Figura 1 ................................................................................................................................ 25! Figura 2 ................................................................................................................................ 26! Figura 3 ................................................................................................................................ 28! Figura 4 ................................................................................................................................ 28! Figura 5: Círculos tangentes entre si e ao eixo das abcissas. ............................................... 31! Figura 6 ................................................................................................................................ 31! Figura 7 ................................................................................................................................ 32! Figura 8 ................................................................................................................................ 32! Figura 9 ................................................................................................................................ 34! Figura 10 .............................................................................................................................. 35! Figura 11: Mapa do Metro da cidade do Porto. ................................................................... 37! Figura 12: Exemplo de um grafo. ........................................................................................ 38! Figura 13: Mapa do Parque da Cidade do Porto. ................................................................. 39! Figura 14: Duas árvores com 7 vértices. .............................................................................. 41! Figura 15 .............................................................................................................................. 42! Figura 16: Algumas árvores. ................................................................................................ 42! Figura 17: Planta da cidade de Königsberg. ........................................................................ 45! Figura 18 .............................................................................................................................. 48! Figura 19: Enumeração de INxIN. ....................................................................................... 49! Figura 20 .............................................................................................................................. 52! Figura 21 .............................................................................................................................. 53! Figura 22: Primeiros níveis da árvore de Stern-Brocot. ...................................................... 54! Figura 23 .............................................................................................................................. 57! Figura 24: Primeiros níveis da árvore de Calkin-Wilf. ........................................................ 69 6 Introdução Esta tese, a sua estrutura, bem como a escolha dos temas que a constituem foram alvo de uma intensa reflexão na medida em que, pela minha experiência, um professor de matemática interessado em aprofundar ou alargar conhecimentos nem sempre tem ao seu dispor informação ou estudos rigorosos que sejam suficientemente acessíveis, quando a sua formação se restringe ao nível do 1º ciclo de estudos do ensino superior, ou quando já esqueceu pequenos grandes pormenores em termos de conceitos, linguagem e notação. Assim, ao longo de todo o trabalho, usar-se-á uma linguagem científica que consideramos adequada e acessível a todos os interessados por estes temas. Serão ainda usados os seguintes símbolos que pretendem chamar a atenção do leitor para certos aspetos do texto: v Questões levantadas; " Sugestões de atividades; þ Resolução de atividades; Chamadas de atenção; Questões finais.! Qualquer um dos temas escolhidos permite alargar o leque de atividades a desenvolver em contexto escolar. Deste modo, não só serão explicadas propriedades como apresentadas as respetivas provas. Tanto quanto possível, procurar-se-á ativar conceitos base no início de cada capítulo, revendo pequenas noções matemáticas que terão relação com cada um dos temas a abordar. Além disto, o que no meu entender é mais desafiante, o leitor será incentivado a descobrir propriedades, através de questões propostas, e a tirar conclusões acerca de alguns aspetos relativos aos temas apresentados. No sentido de consolidar e potenciar o entendimento de algumas propriedades, o leitor encontrará, ao longo de cada capítulo, sugestões de atividades. A resolução das referidas atividades encontrar-se-á imediatamente após a proposta de cada uma delas. Para promover novas interpretações dos diferentes temas e tornar o conhecimento matemático mais significativo, serão sugeridas ainda algumas tarefas, que poderão ser encontradas no final de cada capítulo. Este trabalho está estruturado, de acordo com o tema, em cinco capítulos. No primeiro capítulo, designado Sequências de Farey, mostrar-se-á uma forma de escrever todas as frações entre 0 e 1, tendo em atenção o seu denominador. No segundo capítulo, intitulado Círculos de Ford, apresentar-se-á uma interpretação geométrica das sequências apresentadas no capítulo anterior. 7 O capítulo três, denominado Teoria dos Grafos, pretende estabelecer uma ligação entre o conceito de árvore e os capítulos alusivos à enumeração dos números racionais. Nos capítulos quatro e cinco, designados respetivamente por Árvore de Stern-Brocot e Árvore de Calkin-Wilf, serão mostradas diferentes formas de enumerar os racionais. 14 denominadores podem tomar os valores 1, 2, 3, 4, ..., n. Assim, uma forma aparentemente rápida de contar o número de frações próprias de uma sequência de ordem n é determinar, para cada denominador k menor ou igual que n , quantos são os numeradores entre 1 e k que são primos com k . Designando esse número por ϕ k ( ) , temos ϕ k ( ) =1≤i≤k:m.d.c.k,i ( ) =1 { } , onde, para um conjunto A , A representa o seu cardinal. Particularizando este procedimento no exemplo em estudo, onde n=7 , temos que: - ϕ 1 ( ) =1 ; note-se, no entanto, que F 1 tem dois termos porque inclui também a fração 0 1=0 ; - ϕ 2 ( ) representa o número de inteiros positivos entre 1 e 2 que são primos com 2. Neste caso, ϕ 2 ( ) =1 ; - ϕ 3 ( ) representa, do mesmo modo, o número de inteiros positivos entre 1 e 3, que são primos com 3. Neste caso, apenas 1 e 2 são primos com 3, logo ϕ 3 ( ) =2 ; - ϕ 4 ( ) =2 porque apenas 1 e 3 são primos com 4; - ϕ 5 ( ) =4 porque 1, 2, 3 e 4 são primos com 5; - ϕ 6 ( ) =2 porque apenas 1 e 5 são primos com 6; - ϕ 7 ( ) =6 porque todos os números menores que 7 são primos com ele. Assim, N7=1+ ϕ 1 ( ) + ϕ 2 ( ) + ϕ 3 ( ) + ϕ 4 ( ) + ϕ 5 ( ) + ϕ 6 ( ) + ϕ 7 ( ) =1+1+1+2+2+4+2+6 =19. Em geral, para n≥1 , Nn=1+ ϕ k ( ) k=1 n ∑ . 15 Porém, este processo simples pode não ser suficientemente prático para determinar o número de elementos de uma sequência quando esta é de uma ordem substancialmente mais elevada. Observemos algumas situações particulares e muito curiosas, inerentes ao procedimento anterior. Quando calculamos ϕ (2), ϕ (3), ϕ (5) e ϕ (7) estamos a determinar o número de inteiros positivos que não excedem e são primos com 2, 3, 5 e 7, respetivamente. Repare-se que, neste caso, todos estes números são primos e, por isso, todos os números menores que eles serão primos com eles. Isto permite-nos afirmar que se p é um número primo, ϕ (p)=p−1 . Se tomarmos como exemplos casos em que o número n não é primo, tendo em conta a relação anterior, podemos decompor n em fatores primos e tentar formular, a partir daí, algumas conjeturas para o cálculo de ϕ n ( ) . Comecemos por analisar casos simples, como por exemplo ϕ (6) . Por decomposição em fatores primos, 6=2×3 . A função ϕ tem a seguinte propriedade, que permite simplificar o cálculo de ϕ n ( ) a partir da decomposição de n em fatores primos: ϕ (a×b)= ϕ (a)× ϕ (b) , se m.d.c.(a,b)=1 . (2) Esta relação será devidamente provada no final desta secção. Assim, ϕ (6) = ϕ (2×3) = ϕ (2) × ϕ (3) e, pela relação ϕ (p)=p−1 para p primo, obtemos ϕ (6) = ϕ (2) × ϕ (3) =(2 −1) ×(3−1) =2 , como havíamos anteriormente verificado. No entanto, quando a decomposição de n em fatores primos dá origem a fatores com expoentes superiores a 1, este procedimento não é suficiente. Por exemplo, ϕ 48 ( ) = ϕ 42×3 ( ) = ϕ 42 ( ) × ϕ 3 ( ) = ϕ 42 ( ) ×3−1 ( ) =2 ϕ 42 ( ) . Pretende-se, então, encontrar uma expressão para ϕ p α ( ) onde p é um primo e α é um número natural. Pelo procedimento exemplificado anteriormente, isto será suficiente para determinar ϕ (n) para qualquer n . Determinar ϕ p α ( ) consiste em saber quantos números k , 1≤k≤p α , são primos com p α . 16 Se k e p α são primos entre si, então m.d.c.k,p α ( ) =1 , ou seja, p não divide k . Por outro lado, se m.d.c.k,p α ( ) ≠1 , então p divide k , ou seja, k é um múltiplo de p . Neste caso, ϕ p α ( ) =p α − número de inteiros entre 1 e p α que são múltiplos de p . Para calcular ϕ p α ( ) consideremos o seguinte: Os elementos entre 1 e p α que são múltiplos de p são: 1p, 2p, 3p, ..., p α . Assim, como p α =p α −1×p podemos concluir que existem p α −1 elementos de 1 até p α que são múltiplos de p . Desta forma, ϕ p α ( ) =p α −p α −1 = p α −1p−1 ( ) . Podemos agora calcular ϕ 48 ( ) . ϕ 48 ( ) = ϕ 42×3 ( ) = ϕ 42 ( ) × ϕ 3 ( ) =4×3×2=24 . " Usando as relações expostas, determine ϕ 35280 ( ) . þ ϕ 35280 ( ) = ϕ 24×32×5×72 ( ) = ϕ 24 ( ) × ϕ 32 ( ) × ϕ 5 ( ) × ϕ 72 ( ) =24−23 ( ) ×32−3 ( ) ×5−1 ( ) ×72−7 ( ) =8×6×4×42 =8064. No que se segue, apresenta-se uma expressão para ϕ n ( ) e prova-se a igualdade (2) utilizada acima, ou seja, ϕ (a×b)= ϕ (a)× ϕ (b) , se m.d.c.(a,b)=1 . À semelhança do que referimos anteriormente, ϕ n ( ) =número de inteiros entre 1 e n que são primos com n. (3) =n - número de inteiros entre 1 e n que não são primos com n. (4) Considerando n=p1 α 1.p2 α 2.....pt α t ( α i>0 ) a decomposição de n em fatores primos e Mi o conjunto dos múltiplos de pi ( 1≤i≤t ) entre 1 e n , o conjunto dos números entre 1 e n que não são primos com n é a união M1∪M2∪...∪Mt . 17 Tomemos alguns exemplos para melhor compreender o que acabámos de afirmar. Consideremos, num primeiro exemplo, n=45 . Sabemos que 3,5,6,9,10,12,15,18,20,21,24,25,27,30,33,35,36,39,40,42,45 { } é o conjunto dos números que não são primos com 45, num total de 21, concluindo assim que existem 24 números que são primos com 45. Pelas igualdades (3) e (4) podemos verificar que, ϕ 45 ( ) =45−24 =21 . Por outro lado, uma vez que n=45 =32×5 , consideremos os conjuntos dos múltiplos de 3 e 5, tendo em conta que estes são os primos envolvidos na decomposição do número 45. Neste caso, se p1=3 e p2=5 , temos que M1=3,6,9,12,15,18,21,24,27,30,33,36,39,42,45 { } e M2=5,10,15,20,25,30,35,40,45 { } , pelo que # M1∪M2 ( ) =21 . v Como calcular o cardinal da reunião de dois conjuntos? O tema das Probabilidades, ensinado pela primeira vez aos alunos do 9º ano de escolaridade, aborda a questão da probabilidade da reunião de dois conjuntos. A este propósito, os alunos devem compreender que P A∪B ( ) =P A ( ) +P B ( ) −P A∩B ( ) , muitas vezes recorrendo à ajuda de um diagrama de Venn. De forma análoga, o cardinal de reunião de dois conjuntos é dado por A∪B=A+B−A∩B . (5) Aplicando esta igualdade ao exemplo anterior, concluimos que M1∪M2=M1+M2−M1∩M2=15+9−3=21 . Consideremos, como outro exemplo, n=30 . v O que acontecerá de diferente relativamente ao exemplo anterior? Repare que nesta situação 30 =2×3×5 e, por isso, tomaremos para os conjuntos de múltiplos, os números p1=2 , p2=3 e p3=5 , ou seja, M1=2,4,6,8,10,12,14,16,18,20,22,24,26,28,30 { } , M2=3,6,9,12,15,18,21,24,27,30 { } e M3=5,10,15,20,25,30 { } . 18 Como pode observar, este é um exemplo que envolve mais do que dois conjuntos e, por essa razão, impõe-se a seguinte questão: v Como proceder se quisermos calcular o cardinal da reunião de mais do que dois conjuntos? Com a ajuda de um diagrama de Venn concluimos que, A∪B∪C=A+B+C−A∩B−A∩C−B∩C+A∩B∩C . (6) Aplicando esta última relação ao exemplo considerado, observamos que M1∪M2∪M3=M1+M2+M3−M1∩M2−M1∩M3−M2∩M3+M1∩M2∩M3 =15+10 +6−5−3−2+1 =22. Repare que existem sempre números repetidos nos conjuntos Mi , por exemplo, n ocorre em todos estes conjuntos. Como tal, ao calcular o cardinal da reunião de dois ou mais desses conjuntos, devemos ter cuidado para que os números que aparecem repetidos não sejam contabilizados mais do que uma vez. As relações (5) e (6) referidas anteriormente mostram uma forma eficaz de fazer essa contagem, sendo baseadas num processo que se designa por Princípio de Inclusão-Exclusão. Para facilitar a escrita comecemos por definir, dados índices i1<i2<...<ik , Mi1...ik =Mi1 ∩Mi2 ∩...∩Mik , o conjunto dos múltiplos de pi1 ×pi2 ×...×pik entre 1 e n . O princípio de Inclusão-Exclusão diz que: ∪ i=1 t Mi=M1+M2+...+Mn ( ) −M1∩M2+M1∩M3+... ( ) +M1∩M2∩M3+... ( ) −... =−1 ( ) k+1 i1<...<ik ∑ k=1 t ∑Mi1,...,ik . 19 Notemos que Mi=n pi . Analogamente, se i≠j , Mi∩Mj=n pipj e, mais genericamente, Mi1 ∩...∩Mik =n pi1 ×...×pik , já que os primos pi1 ,...,pik são distintos. Assim, ϕ n ( ) =n− i=1 t ∪Mi =n−M1+M2+... ( ) +M1∩M2+... ( ) −M1∩M2∩M3+... ( ) +... =n−n p1 +n p2 +...+n pt ! " # # $ % & &+n p1p2 +n p1p3 +... ! " # # $ % & &−... =n1−1 pi i=1 t ∑+1 pipj −1 pipjpk +... i<j<k ∑ i<j ∑ " # $ $ % & ' ' *=n1−1 p1 ! " # # $ % & &1−1 p2 ! " # # $ % & &... 1−1 pt ! " # # $ % & & =p1 α 1p2 α 2...pt α tp1−1 p1 p2−1 p2 ... pt−1 pt =p1 α 1−1p2 α 2−1...pt α t−1p1−1 ( ) p2−1 ( ) ... pt−1 ( ) , o que permite calcular ϕ n ( ) , conhecida a decomposição de n em fatores primos (cf. [6]). Com vista à prova da relação (2), suponhamos que a e b são inteiros positivos primos entre si. Então, os conjuntos dos divisores primos de a e de b são disjuntos, e segue facilmente desta observação e da fórmula obtida acima a igualdade (2). * Ao expandir 1−1 p1 " # $ $ % & ' '1−1 p2 " # $ $ % & ' '... 1−1 pt " # $ $ % & ' ' usando a distributividade, em cada fator escolhemos 1 ou −1 pi , logo as parcelas serão do tipo −1 ( ) k1 pi1 ...pik , para i1<...<ik e 0≤k≤t . 1.3. Determinação do termo que sucede a dois termos consecutivos Consideremos as frações 7 1 e 6 1 , consecutivas em F7 . Tendo em conta o algoritmo apresentado para a construção dos termos de uma sequência de Farey, sabe-se que a fração que sucede a 1 7 e 1 6 , em F7 , será uma fração x y em que 6 1 7 1= + + y x . Logo, existe 20 uma constante natural z que verifica ⎩ ⎨ ⎧ ×=+ ×=+ zy zx 67 11 ou seja, ⎩ ⎨ ⎧ −= −= 76 1 zy zx . Como em F7 os denominadores não podem exceder 7, facilmente se conclui que, neste caso, z tem de ser 2 e por isso y=6×2−7=12 −7=5 e por conseguinte 112 =−=x . Fica assim determinado que x y=1 5 . v Existirá, em geral, um único possível valor para a constante z ? Vejamos se este procedimento é igualmente simples se escolhermos as frações consecutivas 1 3 e 2 5 em F7 . Do mesmo modo podemos afirmar que sendo x y a fração que lhes sucede em F7 , então 1+x 3+y=2 5 , donde obtemos ⎩ ⎨ ⎧ −= −= 35 12 zy zx para algum inteiro z . Nesta situação deparamo-nos com algo novo relativamente à situação anterior. Para que y não exceda 7, z pode tomar os valores 1 ou 2. Observe-se que tomando 1=z obtemos a fração 2 1 que sucede 3 1 e 5 2 em F 5 e em F6 ; tomando 2=z obtemos a fração 7 3 que sucede 3 1 e 5 2 em F7 como se pretende no exemplo considerado. v Então, como determinar z ? Para entendermos como tratar esta ou outras situações semelhantes, consideremos três termos consecutivos da sequência Fn, digamos a b<a' b'<x y . Significa assim que x y é a fração que menos difere de a' b' de entre todas as frações de Fn maiores que a' b' . Tal como vimos anteriormente, a' b' é a mediante de a b e x y . Assim, a+x b+y=a' b' e por isso existe um z natural tal que ⎩ ⎨ ⎧ −= −= bzby azax ' ' . Como ny ≤ , da segunda equação anterior vem que nbzb ≤−' , logo 'b bn z+ ≤ e assim z≤n+b b' " # "$ % $ já que z é inteiro, onde α ! "# $ designa o maior inteiro que não excede α . 21 Porém, notemos que esta última relação não permite determinar z . Suponhamos que z<n+b b' ! " !# $ # . Então z+1≤n+b b' e, como a'b>ab' , temos que za'−a zb'−b− z+1 ( ) a'−a z+1 ( ) b'−b= za'−a ( ) z+1 ( ) b'−b " #$ %−zb'−b ( ) z+1 ( ) a'−a " #$ % zb'−b ( ) z+1 ( ) b'−b " #$ % = b' za'−a ( ) −a zb'−b ( ) zb'−b ( ) z+1 ( ) b'−b " #$ % =a' b −ab' zb'−b ( ) z+1 ( ) b'−b " #$ % >0. Logo, a b<a' b' < z+1 ( ) a'−a z+1 ( ) b'−b<za'−a zb'−b e z+1 ( ) b'−b≤n , o que mostra que a b,a' b',za '−a zb'−b não são termos consecutivos em Fn . Provámos assim que o valor que se pretende de z é o maior possível. Por isso, na condição anteriormente referida, z≤n+b b' " # "$ % $ , devemos tomar z o maior inteiro que não excede n+b b' isto é z=n+b b' ! " !# $ # . Fica assim determinado o termo que sucede dois termos consecutivos numa sequência de Farey. No caso apresentado, n+b b' =7+3 5=2 e, por isso, o valor que se deve considerar para a constante z é 2, como se pretendia. 1.4. Relação unimodular e irreducibilidade das mediantes Na sequência que temos vindo a analisar, F7 , 3 7,1 2 são termos consecutivos. Repare que 7×1−3×2=1 . v Será que esta relação se verifica para quaisquer termos consecutivos de uma sequência de Farey? 22 " Se experimentar para outras frações consecutivas, deve verificar essa relação. Dizemos que as frações positivas a b<c d satisfazem a relação unimodular se bc −ad =1 . Proposição: Sejam a b , c d∈0,1 " #$ % , com a,b,c,d∈ Ζ0 + e suponhamos que a b<c d e bc −ad =1 . Se existirem h,k∈ Ζ0 + tais que a b<h k<c d e k≤b+d , então k=b+d , h=a+c e os pares de frações a b,h k e h k,c d satisfazem a relação unimodular. Em particular, se max b,d { } ≤n≤b+d−1 então a b e c d são termos consecutivos em Fn . Demonstração: Suponhamos então que a b<h k<c d e k≤b+d . Temos que kc −hd ≥1 porque h k<c d⇔h k−c d<0⇔hd −kc <0⇔kc −hd >0⇔kc −hd ≥1 , uma vez que h,d ,k ,c são inteiros. Analogamente, hb −ak ≥1 porque a b<h k . Logo, k=k⋅1=k bc −ad ( ) =kbc −kad =b kc −hd ( ) +d hb −ak ( ) ≥b+d, de onde resulta que k=b+d porque partimos da hipótese que k≤b+d mas acabámos de concluir que k≥b+d . Além disso, a igualdade k=b+d implica que b kc −hd ( ) +d hb −ak ( ) =b+d , o que, por sua vez, implica que kc −hd =1=hb −ak . Assim, temos também que h=h bc −ad ( ) =a kc −hd ( ) +c hb −ak ( ) =a+c . 23 Se max b,d { } ≤n , então b≤n e d≤n , o que significa que a b e c d são termos de Fn . Notese que estas frações estão na forma irredutível, pela relação unimodular: se l≥1 dividir a e b , então l divide bc −ad , o que implica l=1 . Se a b e c d não forem termos consecutivos em Fn , então existem naturais h e k tais que a b<h k<c d e k≤n . Assim, k≤n≤b+d−1<b+d , o que contradiz o que foi provado acima. Logo, a b e c d são frações consecutivas em Fn . ¨ Podemos agora justificar o algoritmo dado na secção 1.1 para a construção das sequências de Farey. Teorema: Suponhamos que n≥1 . (a) Se a b<c d são termos consecutivos em Fn , então bc −ad =1 . (b) Para n≥2 , a sequência Fn obtém-se de Fn−1 acrescentando as mediantes dos termos consecutivos de Fn−1 , cuja soma dos denominadores não excede n . Prova: A prova será feita por indução sobre n≥1 . Considerando as sequências Fn quando n=1 e n=2 temos F 1=0 1,1 1 ! " # $ % & e F2=0 1,1 2,1 1 ! " # $ % & , o que permite verificar a veracidade das afirmações (a) e (b) para n≤2 . Suponhamos que o Teorema é válido para n−1 com n≥3 e provemos o caso n . Suponhamos também que a b<c d e que estas são frações consecutivas em Fn . Se b,d≤n−1 , então a b e c d são consecutivas em Fn−1 e, por hipótese de indução, satisfazem a relação unimodular. Logo, podemos assumir que b=n ou d=n ; digamos b=n . 30 Consideremos agora o caso r 1≠r 2 . Então, b≠d e fazendo as substituições γ 1=a b , γ 2=c d , r 1=1 2b2 e r 2=1 2d2 na equação (2), obtemos b2−d2 2b2d2 α 2−2ab −cd 2b2d2 α +a2−c2 2b2d2=0 ou, de forma equivalente, α 2−2ab −cd b2−d2 α +a2−c2 b2−d2=0 . Note-se que a2−c2 b2−d2= a−c ( ) a+c ( ) b−d ( ) b+d ( ) =a−c b−d×a+c b+d ; além disso, a−c b−d+a+c b+d= a−c ( ) b+d ( ) +a+c ( ) b−d ( ) b−d ( ) b+d ( ) =2ab −cd b2−d2 . Resulta, portanto, que as soluções de (2) são a+c b+d e a−c b−d e, assim, α =a+c b+d ou α =a−c b−d . Suponhamos, por redução ao absurdo, que α =a−c b−d . Em particular, como 0≤a b< α <c d temos a−c b−d>0 e podemos supor que a−c>0 e b−d>0 (o caso a−c<0 e b−d<0 é análogo). Então, a mediante de a−c b−d e c d está entre estes dois valores, o que é absurdo já que essa mediante é a b< α . Resulta, portanto, que α =a+c b+d e resta determinar r 3 : r 3= α − γ 1 ( ) 2 4r 1 = a+c ( ) b−a b +d ( ) b b +d ( ) ! " # # $ % & & 2 4 2b2 = 2b2bc −ad ( ) 2 4b2b+d ( ) 2=1 2b+d ( ) 2 , pela relação unimodular cb −ad =1 . 31 v Consegue imaginar qual a imagem que obteríamos se construíssemos várias circunferências aplicando o processo descrito neste capítulo? A imagem que se poderia obter depende do número de circunferências que pretenda desenhar. A seguir, apresenta-se um possível exemplo do que se poderia obter (ver também [13]). ! Figura 5: Círculos tangentes entre si e ao eixo das abcissas. " Baseando-se apenas nas duas circunferências que abaixo se apresentam, obtenha uma estimativa para o valor da área da região formada pela reunião de todos os círculos que se poderiam traçar aplicando o procedimento aqui exposto. ! Figura 6 32 þ Uma vez que todos os círculos traçados seão tangentes ao eixo das abcissas nalgum ponto de 0,1 ! "# $ , resulta que a região referida está contida nas regiões planas que se assinalam na figura seguinte por A 1 , A2 e A3 . ! Figura 7 Procurando resolver esta questão de forma bastante simplificada, sugerimos que decomponha a imagem da seguinte forma: ! Figura 8 Começando por determinar a área de cada um dos círculos, devemos recordar que ambos têm raio 0,5 . Logo, tendo em conta que Z1 e Z2 representam 3 4 de cada círculo, a área de Z1 e Z2 é 3 8 π . Uma vez que Z3 representa um retângulo com dimensões 1 e 0,5 , facilmente se determina que a sua área é 0,5 . 33 Assim, a área total de A 1∪A2∪A3 é 3 8 π +1 2=3 π +4 8 , valor este que é um majorante da área da região formada pelo raio de todos os círculos formados pelo processo que descrevemos no início deste capítulo. De facto temos 3 π +4 8≈1,678 . Vamos agora determinar o valor exato da área formada por todas as circunferências obtidas pelo processo descrito. Para cada racional 0≤a b≤1 com a , b inteiros não negativos e primos entre si, o círculo correspondente é Ca b , com raio 1 2b2 e centro a b,1 2b2 ! " #$ % & . Assim, Ca b tem área π 4b4 . Além disso, os círculos Ca b são disjuntos dois-a-dois e para cada b≥1 há ϕ b ( ) círculos com raio 1 2b2 , exceto no caso b=1 em que devemos considerar também o círculo C0 1 de área π 4 . Logo, a área total destes círculos é π 4+ π 4b4× ϕ b ( ) = b≥1 ∑ π 4 ϕ b ( ) 4b4+1 b≥1 ∑ $ % & & ' ( ) ) . Já sabemos que este valor é limitado superiormente por 3 π +4 8 mas para determinar o valor exato desta área é necessário obter o valor de ϕ b ( ) b4 b≥1 ∑ . A determinação deste valor e a sua justificação vai muito além do âmbito desta tese mas, por uma questão de completude e para aliciar a curiosidade do leitor mais ávido, indicamos que ϕ b ( ) b4= b≥1 ∑ ζ 3 ( ) ζ 4 ( ) , onde ζ é a conhecida fração de Riemann, ζ 4 ( ) =1 n4= π 4 90 n≥1 ∑ e ζ 3 ( ) =1 n3≈1,2021 n≥1 ∑ , esta última designada por constante de Apéry (ver [10, Chap. II], [36] e [37]). 34 Logo, a área formada por todos os círculos é π 4 1+ ϕ b ( ) b4 b≥1 ∑ # $ % % & ' ( (= π 4 1+ ζ 3 ( ) ζ 4 ( ) ! " # # $ % & & = π 4 π 4+90 ζ 3 ( ) π 4 = π 4+90 ζ 3 ( ) 4 π 3 ≈1,658. Observa-se que a estimativa que obtivemos inicialmente para o valor desta área difere do valor real por menos de 3 décimas, o que indica que os círculos em A3 são bastante densos. Nas imagens seguintes estão representados alguns círculos, que atendem às características anteriormente expostas, e foram assinalados os seus centros. Imaginando unir sequencialmente esses centros usando segmentos de reta, de forma a obter um gráfico de uma função, consegue tirar algumas conclusões acerca do comportamento das curvas que se obtêm, considerando cada vez mais circunferências? Será que os centros de todas as circunferências obtidas pelo processo descrito são pontos do gráfico de alguma função contínua? ! Figura 9 35 ! Figura 10 A definição formal de continuidade diz-nos que uma função f é contínua em x0 , quando f x0 ( ) =lim x→x0 f x ( ) . Uma definição equivalente, segundo Heine, é que lim n→+∞f xn ( ) =f a ( ) , para toda a sucessão xn ( ) n≥0 de pontos do domínio de f e convergente para a . Seja 0≤a b≤1 , com a,b ≥0 e m.d.c. a,b ( ) =1 . O raio da circunferência correspondente ao ponto de abcissa a b é 1 2b2 . Logo, os centros das circunferências que se obtêm pelo processo descrito forma o conjunto a b,1 2b2 ! " #$ % &:0≤a≤bem.d.c. a,b ( ) =1 ( ) * + * , - * . * . Vamos ver que a função f : 0,1 ! "# $∩Q→Q que tem como gráfico este conjunto não é contínua em nenhum dos pontos do seu domínio. Comecemos por analisar um caso simples. Para tal, vejamos que a função não é contínua para x=1 . Este valor está associado à circunferência que é tangente ao eixo das abcissas no ponto de abcissa 1 e, atendendo ao que foi explanado neste capítulo, podemos afirmar que o raio dessa circunferência é 1 2 . Neste caso, pretendemos mostrar que existe uma sucessão un ( ) n≥1 com valores em 0,1 ! "# $∩Q convergente para 1, mas que f un ( ) não 36 converge para f1 ( ) . Tomemos, para o efeito, un=n−1 n , com n≥1 . Notemos que n−1 e n são primos entre si. Temos então que fn−1 n " # $% & '=1 2n2 e lim n→+∞fn−1 n $ % &' ( )=lim n→+∞ 1 2n2=0 , que é diferente de f1 ( ) =1 2 . Logo, a função f não é contínua em 1. Vamos provar, de seguida, que a função não é contínua em a b , generalizando o exemplo concreto que acabámos de referir, onde a b∈0,1 " #$ %∩Q e a b≠1 . Supomos ainda que os inteiros a e b são primos entre si e 0≤a<b . Seja pn { } n≥1 uma enumeração crescente dos primos maiores que b e consideremos a sucessão a b+1 pn ! " # $ # % & # ' #n≥1 , convergente para a b . • Em primeiro lugar, observemos que a b+1 pn =apn+b bpn , e provemos que apn+b e bpn são primos entre si, ou seja, que a fração apn+b bpn é irredutível. De facto, se existisse um divisor primo, d , de apn+b e bpn , então: o se d divide b , resulta que d≤b e, portanto, d≠pn porque pn>b ; logo d divide a , o que é absurdo; o se d não divide b , então d=pn e pn divide b , o que é absurdo pois pn>b . Nesta situação, verificamos que lim n→+∞fapn+b bpn # $ % % & ' ( (=lim n→+∞ 1 2b2p2 n =0 . No entanto, fa b ! " #$ % &=1 2b2≠0 . Logo, a função f não é contínua em a b . Como também foi visto que a função f não é contínua em 1, podemos concluir que f não é contínua em nenhum ponto do seu domínio. 37 Capítulo 3: Teoria de Grafos A Teoria dos Grafos é atualmente uma das áreas mais importantes da matemática discreta sendo usada no estudo das relações entre os objetos de um determinado conjunto (ver [31]). A sua criação é atribuída a Leonhard Euler, conhecido matemático suíço, por resolver o problema das pontes de Königsberg, em 1736 (ver [34] e [35]). Euler fez várias descobertas na área da matemática, particularmente na área do cálculo e dos grafos. Também fez muitas contribuições para a matemática moderna ao nível da terminologia e notação, em especial na análise matemática, como por exemplo, a noção de função. Tornou-se, ainda, célebre por tudo o que desenvolveu na área da mecânica, ótica e astronomia. Euler é considerado um dos matemáticos mais notáveis do século XVIII (ver [32] e [33]). Ao longo deste capítulo, far-se-á uma exposição global de grafos, dando especial importância às árvores, uma vez que os dois capítulos seguintes têm por base este conceito. Para obter mais informação sobre grafos pode consultar [5] e [35]. A Teoria dos Grafos tem sido aplicada a muitas áreas como informática, economia, sociologia, genética, entre outras, na medida em que um grafo é considerado o modelo matemático ideal para o estudo de determinadas relações entre objetos discretos. v Já tinha ouvido falar em grafos? Acha que poderá já ter encontrado grafos em situações do seu dia-a-dia? Se observar a imagem que em baixo se apresenta, perceberá tratar-se, neste caso, do mapa do metro do Porto, tão vulgarmente conhecido para quem usa este meio de transporte. Fonte: http://lounge.obviousmag.org/risco/2012/08/20/metro/Rede_metro_do_porto.png Figura 11: Mapa do Metro da cidade do Porto. 38 Definição: Um grafo é um par ordenado G=V ,E ( ) , onde: • V é um conjunto finito cujos elementos são denominados por vértices; • E é um conjunto de elementos do tipo x,y { } , chamados arestas, em que x e y são dois vértices diferentes. Considerando a aresta α =x,y { } dizemos que: • x e y são vértices adjacentes e vizinhos; • x e y são as extremidades de α ; • x e α são incidentes, bem como y e α . É usual representar um grafo no plano de forma a que os vértices correspondam a pontos e arestas a curvas entre os respetivos pontos. A figura seguinte é um exemplo de uma representação do grafo G=V ,E ( ) , V=x,y,z,w { } e E=x,y { } , x,w { } , w,z { } , w,y { } , z,y { } { } . Figura 12: Exemplo de um grafo. Entende-se por grau ou valência de um vértice, o número de arestas que são incidentes nesse vértice. Com base na representação anterior, podemos afirmar que x tem grau 2 e y tem grau 3. v Acha que poderá haver alguma relação entre o número de arestas de um grafo e os graus dos seus vértices? 39 " Faça algumas representações de grafos e tente tirar conclusões. þ Em todos os exemplos que considerou deverá ter chegado à conclusão que a soma dos graus dos vértices de um grafo é igual ao dobro do número de arestas. Simbolicamente, grau v ( ) =2E v∈V ∑ . Para que fique verdadeiramente convencido que esta relação se verifica para qualquer grafo G apresentamos, de seguida, a respetiva prova. Considerando um grafo G sabe-se, por um lado, que a soma dos graus dos seus vértices é dada pelo número total de incidências em cada um dos seus vértices; por outro lado, cada aresta contribui com 2 para a soma dos graus dos vértices. Assim se prova que a soma dos graus dos vértices de um determinado grafo é igual ao dobro do número de arestas que constituem esse mesmo grafo, ficando provada a relação anterior. ¨ v Imagine que os professores de Educação Física de uma escola vão organizar uma prova de corta-mato no Parque da Cidade do Porto. Para isso, ao fazerem uma pesquisa na internet para conhecerem o mapa do referido parque, deram conta que havia muitas possibilidades para definirem o trajeto da corrida. Fonte: Google Maps Figura 13: Mapa do Parque da Cidade do Porto. Na reunião de preparação da atividade, os professores do grupo de Educação Física usaram termos como passeio, atalho, caminho, circuito e ciclo para darem ideias acerca do trajeto a definir. Num grafo, estes termos têm significados próprios e distintos. 46 Capítulo 4: Árvore de Stern-Brocot A árvore que vamos descrever neste capítulo remonta a meados do século XIV e foi descoberta por Stern e por Brocot, de forma independente. É uma árvore que permite enumerar todos os números racionais positivos (ver [4], [9], [16] e [17]). Na descrição que a seguir se apresenta, teremos oportunidade de referir mais especificamente quem foram Moritz Stern e Achille Brocot e de mostrar como se deve proceder para conseguir essa enumeração dos racionais positivos. Já terá ouvido e estudado, certamente, algo relacionado com a enumeração dos números racionais, ou seja, algum tipo de algoritmo que permita gerar todos os números racionais. Várias poderão ser as formas de fazer essa enumeração. v Conhece algum processo que faça surgir cada racional positivo uma única vez e na forma de fração irredutível? Quando, na escola, se estudam conjuntos numéricos, a intuição dos alunos fá-los acreditar que não é possível enumerar nenhum dos conjuntos estudados, por serem infinitos. No caso de se considerar um conjunto finito, o aluno procede intuitivamente à contagem dos elementos que o constituem. O problema surge quando o conjunto considerado é infinito. Os conjuntos infinitos podem classificar-se por infinitos numeráveis ou infinitos não numeráveis. v O que é que significa um conjunto ter cinco elementos? Se um conjunto tem cinco elementos significa que é possível enumerar os seus elementos de 1 até 5. De forma mais formal, um conjunto tem cinco elementos se existir uma bijeção entre esse conjunto e o conjunto 1,2,3,4,5 { } dos naturais entre 1 e 5. Recorde-se que uma função f : X →Y é: • injetiva, se a≠b⇒f a ( ) ≠f b ( ) , para quaisquer a,b ∈X ; • sobrejetiva se f X ( ) =Y . Se f é injetiva e sobrejetiva, então f é bijetiva. De um modo geral, diz-se que um conjunto X tem n elementos se existir uma bijeção entre X e o conjunto dos naturais entre 1 e n . 47 Definição: Dizemos que dois conjuntos X e Y têm o mesmo número de elementos se existe uma bijeção entre X e Y . Dizemos também que X e Y são equipotentes ou equicardinais. De seguida, generalizamos esta noção para conjuntos infinitos. Definição: Um conjunto infinito diz-se numerável se existe uma função bijetiva entre o conjunto dos números naturais e esse conjunto. Caso contrário diz-se infinito não numerável. Resulta desta definição que se X for um subconjunto de IN , então ou X é finito ou X é infinito numerável (ver por exemplo [8], proposição 2.5.1]). v Por exemplo, sabia que o conjunto dos números naturais e o conjunto dos números pares positivos têm o mesmo número de elementos? Se refletir um pouco acerca desta questão, entenderá que é possível estabelecer uma bijeção entre o conjunto dos números naturais e o conjuntos dos números pares, como se ilustra na tabela seguinte. n 2n 1 2 2 4 3 6 4 8 5 10 ... ... Tabela 2 Estes dois conjuntos dizem-se, por isso, equipotentes ou com a mesma cardinalidade. v Será que o conjunto dos números racionais também é numerável? É bem conhecido que a resposta a esta questão é afirmativa mas, neste capítulo, iremos abordar uma forma de enumerar os racionais com propriedades particularmente interessantes. 48 Começamos por recordar a prova clássica da que o conjunto dos números racionais é numerável (ver [19]). Para isso, vamos estabelecer uma correspondência entre números naturais e pares de números naturais. Estes últimos serão tidos como pontos no plano com coordenadas naturais, como se representa na figura abaixo. ! Figura 18 Consideremos, para o efeito, que cada coordenada assinalada m,n ( ) representa uma fração m n . v Existirá alguma forma de conseguirmos enumerar todas as frações m n representadas no referencial anterior? Com base nesse referencial, se tentarmos enumerar os racionais por linhas, damos conta que nunca conseguiremos passar para a linha seguinte, uma vez que o número de elementos de cada linha é infinito. De outra forma, se fizermos a contagem seguindo a ordem das setas que ilustram o referencial seguinte, verificamos que existe uma forma de descrevermos todos os racionais apresentados. 49 ! Figura 19: Enumeração de INxIN. Isto permite-nos concluir que existe uma bijeção entre o conjunto dos números naturais e o conjunto dos pares de naturais. Como consequência, podemos ainda afirmar que existe uma bijeção entre o conjunto dos números naturais e o conjunto dos racionais positivos, como vamos ver de seguida. Provámos que existe uma bijeção f : IN →IN ×IN , ou seja, entre o conjunto dos números naturais e o conjunto dos pares de naturais. Podemos identificar o conjunto dos racionais positivos como o subconjunto do conjunto dos pares de naturais que são primos entre si. Esta identificação permite escrever Q+⊆IN ×IN . Seja X=i∈IN : f i ( ) ∈Q+ { } =i∈IN : f i ( ) =a,b ( ) com a,b ∈IN em.d.c. a,b ( ) =1 { } . Temos então uma bijeção fX: X ! →! Q+ . Como X não é finito, porque Q+ também não é, então X é numerável. Logo, existe uma bijeção g : IN →X . A composta h=f!g : IN →Q+ é uma bijeção entre IN e Q+ , o que mostra que Q+ é numerável. Provámos, assim, que existe uma enumeração dos racionais positivos. 50 v Será possível fazer uma enumeração de todos os racionais? Tal como vimos anteriormente, Q+ é numerável porque existe uma bijeção h entre IN e Q+ . Considerando a função H definida por H : IN →Q i! h k ( ) ,i =2k −h k ( ) ,i =2k+1 0,i =1 # $ % % & % % , para k≥1 vemos também que Q é um conjunto numerável, uma vez que H é bijetiva. A árvore de Stern-Brocot, apresentada neste capítulo, revela uma forma diferente de construir uma enumeração dos racionais positivos, estabelecendo uma bijeção explícita entre IN e Q+ , que é obtida de forma construtiva por um algoritmo. Se explorar um pouco acerca da origem da referida árvore encontrará algo curioso. A designação da árvore, Stern-Brocot, é a conjugação dos dois nomes relacionados com a sua descoberta e aplicação. O mais extraordinário é que essa descoberta foi feita de forma independente, ainda que por volta da mesma altura: Moritz Stern em 1858 e Achille Brocot em 1861. Estará a pensar, neste momento, que nos referimos a grandes matemáticos... Moritz Abraham Stern, de origem alemã e oriundo de famílias humildes, foi o primeiro matemático judaico a exercer funções de professor titular na Universidade de Gotinga, na Alemanha. Começou por descrever a árvore e posteriormente explicou a sua relação com outros temas na área da teoria dos números (ver [20], [23] e [24]). Além da árvore que iremos abordar, Stern deu outros contributos na área da matemática. Ele possivelmente terá sido o primeiro a aperceber-se do talento de Bernhard Riemann para a matemática. Stern terá contribuído para a prova do teorema da reciprocidade quadrática, por Ferdinand Eisenstein. Um outro tema que lhe terá suscitado interesse, relaciona-se com os números primos que não podem ser expressos como soma de um primo menor com o dobro de um quadrado perfeito, atualmente designados por Primos de Stern (ver [25]). Achille Brocot, por sua vez, era um famoso relojoeiro francês e simplesmente um matemático amador (ver [21]). 51 v Que relação terá a relojoaria com a matemática? (A propósito de matemática e relojoaria ver por exemplo [7], embora o tema deste artigo não esteja relacionado com esta tese.) Por que razão estará o nome de um relojoeiro associado a uma descoberta matemática? Como tem conhecimento, os relógios mais antigos funcionavam por um processo associado a roldanas. Esse mecanismo era estudado por engenheiros, que calculavam o número de dentes necessários em cada roldana de forma a garantir que o sistema funcionasse de forma eficaz, nomeadamente ao nível da velocidade de movimento das roldanas. É aí que entra a teoria dos números associada à descoberta de Brocot, cuja visão foi meramente prática. Ele dedicou a sua atenção ao mecanismo dos relógios, para calcular a melhor razão entre as roldanas acabando por criar um algoritmo que o fez chegar à referida árvore (ver [18] e [22]). Veremos que esta árvore goza de várias propriedades interessantes. v Está recordado da definição de árvore? Como foi visto no Capítulo 3, uma árvore é um grafo conexo cujas arestas são todas pontes, ou seja, se retirada qualquer aresta do grafo este se torna desconexo. Foi também visto nesse capítulo que também é possível definir uma árvore como sendo um grafo conexo sem ciclos e que uma árvore com n≥2 vértices tem exatamente n−1 arestas e pelo menos dois vértices de grau 1. Estes vértices designam-se por folhas e os restantes designam-se por vértices interiores. Se pretendermos associar a cada número racional positivo um vértice da árvore de SternBrocot seremos forçados a considerar uma árvore como um conjunto numerável de vértices. Nesta situação não é garantida a existência de folhas e veremos que a árvore de Stern-Brocot não terá folhas, o que não contradiz a afirmação que fizemos acima, tendo em conta tratar-se de uma árvore infinita. Para escrevermos os números racionais positivos segundo o processo de Stern-Brocot, devemos começar por considerar os “extremos” de Q+ : 0 e +∞ . Identifiquemos 0 com a fração 0 1 e +∞ com o símbolo 1 0 , visto como uma fração de numerador 1 e denominador 0. 52 De seguida, tendo em conta que a árvore vai ser construída faseadamente, vai-se determinando, em cada passo, a fração mediante de cada par de frações consecutivas obtidas no passo anterior. O que se obtém é algo do género do que a seguir se apresenta. ! Figura 20 v Como construir uma árvore com base nesta tabela? Para uma melhor leitura, designaremos o conjunto de todas as frações obtidas até ao passo n , para n≥ −1 , por SBn . Para o efeito tomaremos: SB−1=0 1,1 0 " # $ % & ', SB0=0 1,1 1,1 0 ! " # $ % &, ... Recursivamente, definimos SBn+1=SBn∪mediantes de cada par de frações consecutivas de SBn { } . Note-se que, SB−1=2 , SB0=3 , 53 SBn+1=SBn+SBn−1=2SBn−1 , uma vez que o número de frações existentes numa determinada ordem corresponde ao número de frações que já existiam na ordem anterior, acrescido do número de mediantes adicionadas. Logo, SBn=2n+1+1 , para todo o n≥ −1 , resultado que se prova do seguinte modo, por indução: - Para n=−1 , temos que: SB−1=0 1,1 0 " # $ % & '=2=2−1+1+1 . - Supondo que a igualdade que queremos provar se verifica para determinado n≥ −1 , provemos que também se verifica para n+1 : SBn+1=2SBn−1=2 2n+1+1 ( ) −1=2n+2+2−1=2n+2+1 . Fica assim estabelecida a igualdade enunciada. Iremos destacar na árvore a fração 1 1 , que será designada por raiz da árvore. Analisando a tabela anterior a partir dessa raiz, comecemos por destacar a primeira vez que cada fração surge. De seguida, cada fração de SBn (exceto 0 1 e 1 0 ), vai ser usada para calcular duas novas mediantes pertencentes a SBn+1 . Isso deverá ser assinalado com uma aresta entre essa fração e as duas frações correspondentes de SBn+1 , como é ilustrado na tabela seguinte. Figura 21 54 Ignorando todas as frações que não estão destacadas e os termos 0 1 e 1 0 , obtemos parte da árvore que designaremos adiante por árvore de Stern-Brocot: Figura 22: Primeiros níveis da árvore de Stern-Brocot. v Reparou que o número de arestas que partem (no sentido descendente) de cada fração é sempre 2? v Qual é a estrutura desta árvore? Esta árvore é um exemplo de uma árvore binária completa, na medida em que tem as seguintes características: • tem um vértice, neste caso 1 1 , designado por raiz, que tem grau 2; • todos os vértices interiores, exceto a raiz, têm grau 3. Para facilitar a definição da árvore de Stern-Brocot vamos definir recursivamente uma família de árvores finitas, Tn ( ) n≥0 , onde Vn designa o conjunto de vértices de Tn , En designa o conjunto de arestas de Tn , Vn⊆Vn+1 e En⊆En+1 . A árvore de Stern-Brocot será o “limite” ou, mais concretamente, a união destas árvores. Temos então, T0=V0,E0 ( ) , onde V0=SB0\ SB−1=1 1 " # $ % & ' e E0=∅ ; T1=V1,E1 ( ) , onde V1=V0∪ • SB1\ SB0 ( ) =SB1\ SB−1=1 2,1 1,2 1 # $ % & ' ( e E1=E0∪ • arestas de α ∈SB0\ SB−1para β ∈SB1\ SB0se β ocorre em SB1\ SB0como mediante de α e de α '∈SB−1 { } . 55 Recursivamente, Tn+1=Vn+1,En+1 ( ) , onde Vn+1=Vn∪ • SBn+1\ SBn ( ) =SBn+1\ SB−1 e En+1=En∪ • arestas de α ∈SBn\ SBn−1para β ∈SBn+1\ SBnse β ocorre em SBn+1\ SBncomo mediante de α e de α '∈SBn−1 { } . A árvore de Stern-Brocot, designada por T=V ,E ( ) , é definida por T=∪ n≥0 Tn , ou seja, V=∪ n≥0 Vn e E=∪ n≥0 En . Definição: Dizemos que a fração a b∈Q+ tem ordem n≥0 se a b∈SBn\ SBn−1 . Vimos anteriormente que cada fração em Tn , de ordem n≥0 , é mediante de duas anteriores (eventualmente 0 1 e/ou 1 0 ). A este propósito, se analisar a figura 21 verifica, por exemplo, que 5 8 é a mediante de 3 5 e 2 3 . Se analisar as mesmas frações na figura 22, entenderá a razão por que passaremos a designar 3 5 por ascendente menor de 5 8 e 2 3 por ascendente maior de 5 8 . A observação do esquema seguinte pretende facilitar a interpretação desta explicação. ! ! 2 3 ! !!!!!!! !!!!!!!!!! 3 5 ! ! ! !!!!!! 5 8 ! 62 Repare que se somar os produtos das entradas de cada coluna, concluirá que 100 000 =1×216 +1×215 +1×211 +1×25+1×23 . Note que as parcelas cujo resultado desse produto é zero são omitidas. Uma outra forma de obtermos a representação binária de um número é a que a seguir se apresenta. Consideremos, para isso, o número 83, bastante inferior a 100 000, para facilitar a apresentação do procedimento utilizado. Se efetuarmos consecutivas divisões por 2, até obter quociente 0, obtemos o seguinte: 83 2 1 41 2 1 20 2 0 10 2 0 5 2 1 2 2 0 1 2 1 0 v Que significado terão os sucessivos restos da divisão, assinalados a negrito, tendo em conta o que se pretende determinar? Aplicando o algoritmo da divisão, ensinado no 1º ciclo do ensino básico, D=d×q+r , com 0≤r<q , onde D representa o dividendo, d o divisor, q o quociente e r o resto, podemos escrever, 83 =2×41+1 =2×2×20 +1 ( ) +1 =22×20 +2×1+1 =22×2×10 +0 ( ) +2×1+1 =23×10 +22×0+2×1+1 =23×2×5+0 ( ) +22×0+2×1+1 =24×5+23×0+22×0+2×1+1 =24×2×2+1 ( ) +23×0+22×0+2×1+1 =25×2+24×1+23×0+22×0+2×1+1 =25×2×1+0 ( ) +24×1+23×0+22×0+2×1+1 =26×1+25×0+24×1+23×0+22×0+2×1+1 =26×1+25×0+24×1+23×0+22×0+21×1+20×1. 63 v Compare os restos da divisão anterior com os fatores associados às potências de base 2 da última expressão encontrada. Encontra alguma relação? Conclui-se, assim, que 1010011 é a representação binária do número 83. Simbolicamente, podemos escrever 83 =1010011 ( ) 2 . " Escreva o número 37 na base 2 utilizando um dos processos apresentados. þ 37 =100011 ( ) 2 porque 37 =2×18 +1 =2×2×9+1 ( ) +1 =22×9+2×1+1 =22×2×4+1 ( ) +2×1+1 =23×4+22×1+2×1+1 =23×2×2+0 ( ) +22×0+2×1+1 =24×2+23×0+22×0+2×1+1 =24×2×1+0 ( ) +23×0+22×0+2×1+1 =25×1+24×0+23×0+22×0+2×1+1 =25×1+24×0+23×0+22×0+21×1+20×1. v Porque razão terá sido abordada a escrita de números em base binária? Acerca da forma de enumerar os números racionais, existe uma outra forma que está relacionada com uma determinada sucessão b n ( ) com n≥0 , em que todos os racionais se podem escrever na forma b n ( ) b n +1 ( ) para um e um só n≥0 . Os primeiros termos desta sucessão são: 1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,1,5,... (1) Fazendo os quocientes de termos consecutivos da sucessão, ou seja, dividindo um termo da sucessão pelo seguinte, obtemos a sucessão de números racionais que a seguir se apresenta: 1 1,1 2,2 1,1 3,3 2,2 3,3 1,1 4,4 3,3 5,5 2,2 5,5 3,3 4,4 1,1 5, ... 64 v O que representará b n ( ) ? Que significado terão os números que constituem esta sucessão? Definição: Dado um número n , b n ( ) designa o número de formas de escrever n como soma de potências de base 2 e expoente inteiro não negativo, onde cada potência pode ser usada zero, uma ou duas vezes. Por convenção, b0 ( ) =1 . Por exemplo, 4=20+20+21 =21+21 =22 e, por isso, uma vez que existem apenas três formas de escrever 4 usando, no máximo, cada potência de 2 duas vezes, b4 ( ) =3 , como consta em (1). Já no seguinte caso, 10 =20+20+21+21+22 =20+20+22+22 =20+20+23 =21+22+22 =21+23, pelo que se conclui que b10 ( ) =5 . v Entende agora o motivo pelo qual abordámos o sistema binário? Este procedimento apenas difere no número de vezes que as potências de 2 podem ser usadas. v Existirá, no entanto, outro processo para determinarmos o número de formas de escrever n como soma de potências de base 2, ou seja, alguma forma de determinarmos os termos da sucessão b n ( ) de forma sistemática, que não seja por métodos exaustivos? Definição: Por uma questão de simplicidade de linguagem, uma decomposição de um natural em potências de base 2 e expoente inteiro não negativo, onde cada potência é usada, no máximo, duas vezes, será designada por decomposição admissível. 65 Note-se que b n ( ) ≥1 para todo o n≥0 , já que a representação binária de n dá origem a uma decomposição admissível de n . Arranjar uma forma de determinar b n ( ) implicará, como veremos, considerar separadamente os casos n par e n ímpar. Começando por analisar a situação para números pares, determinar b2n ( ) é encontrar uma forma de contagem do número de decomposições admissíveis do número par 2n . O método usado será o método recursivo. Suponha-se, para o efeito, que 2n=2k1+2k2+2k3+...+2kl (2) é uma decomposição admissível de 2n . v Poderão algumas das potências representadas acima ter expoente 0? Tendo em conta que 2n representa um número par, as potências com expoente 0 ou não figuram na decomposição ou são usadas duas vezes. Vamos, por isto, considerar as duas situações. Supondo, em primeiro lugar, que no desenvolvimento (2) não figuram potências com expoente 0, temos que 2n=2k1+2k2+2k3+...+2kl⇔ ⇔2n 2=2k1+2k2+2k3+...+2kl 2 ⇔n=2k1−1+2k2−1+2k3−1+...+2kl−1. Uma vez que subtraímos 1 a cada expoente, a propriedade de cada potência aparecer, no máximo, duas vezes é preservada. Além disso, como estamos a supor que ki≥1 , temos que ki−1≥0 , podendo concluir que todos os expoentes são inteiros não negativos. Reciprocamente, dada uma decomposição admissível de n , é possível obter a partir desta uma decomposição admissível de 2n , multiplicando-a por 2. Isso significa somar 1 a cada expoente e por isso a propriedade de cada potência aparecer, no máximo, duas vezes é preservada. Além disso, como estamos também a supor que os expoentes da decomposição de n são inteiros não negativos, na correspondente decomposição de 2n todos os expoentes são maiores ou iguais a 1. Concluimos assim 66 que o número de decomposições admissíveis de n é igual ao número de decomposições admissíveis de 2n , nas quais não figuram potências de expoente 0. Por isso, b2n ( ) =b n ( ) +# decomposições de 2n em que 20é usada { } . Supondo agora que em (2) aparecem potências com expoente 0, tal como referido anteriormente, estas deverão aparecer duas vezes. Assim, assumindo que k1=k2=0 , temos 2n=1+1+2k3+...+2kl⇔ ⇔2n−2=2k3+...+2kl ⇔2n−2 2=2k3+...+2kl 2 ⇔n−1=2k3−1+...+2kl−1. À semelhança do que concluímos anteriormente, a propriedade de cada potência aparecer, no máximo, duas vezes é preservada. Além disso, como ki≥1 para qualquer i≥3 , todos os expoentes são inteiros não negativos. Reciprocamente, dada uma decomposição admissível de n−1 , podemos obter uma de 2n multiplicando a decomposição de n−1 por 2 e somando de seguida 20+20 , garantindo assim que a decomposição de 2n será uma decomposição admissível, em que a potência 20 ocorre duas vezes. Estudadas as duas situações referidas anteriormente, temos que b2n ( ) =b n ( ) +b n −1 ( ) , para todo o natural n . Estudando agora a mesma situação para números ímpares, suponhamos que o desenvolvimento 2n+1=2k1+2k2+...+2kl (3) é uma decomposição admissível de 2n+1 . Como 2n+1 é um número ímpar, o número de potências com expoente 0 terá que ser ímpar. Porém, atendendo a que cada potência de 2 só poderá aparecer até duas vezes em (3), 20 terá, necessariamente, que aparecer uma única vez no desenvolvimento (3). 67 Supondo, assim, que no desenvolvimento anterior k1=0 e que para qualquer i>1 , ki≠0 , temos 2n+1=2k2+...+2k1+20⇔ ⇔2n=2k2+...+2k1 ⇔2n 2=2k2−1+...+2k1−1 ⇔n=2k2−1+...+2k1−1. Uma vez que, também aqui, subtraímos 1 a cada expoente, a propriedade de cada potência aparecer, no máximo, duas vezes é preservada e os expoentes usados são não negativos. Reciprocamente, dada uma decomposição admissível de n , podemos obter uma de 2n+1 multiplicando a primeira por 2 e somando de seguida 20 . O que se obtém continua a ser uma decomposição admissível. Neste caso, o número de decomposições admissíveis de n é igual ao número de decomposições admissíveis de 2n+1 , ou seja, b2n+1 ( ) =b n ( ) , para todo o inteiro maior ou igual a zero. " Determine b n ( ) para diferentes valores, por si escolhidos. þ Os exemplos que usou dificilmente serão os mesmos que abaixo se apresentam! Vejamos, b1 ( ) =1, b2 ( ) =2, b3 ( ) =b2×1+1 ( ) =b1 ( ) =1, b4 ( ) =b2×2 ( ) =b2 ( ) +b1 ( ) =2+1=3, b5 ( ) =b2×2+1 ( ) =b2 ( ) =2, ... b30 ( ) =b2×15 ( ) = =b15 ( ) +b14 ( ) =b2×7+1 ( ) +b2×7 ( ) =b7 ( ) +b7 ( ) +b6 ( ) =2b2×3+1 ( ) +b2×3 ( ) =2b3 ( ) +b3 ( ) +b2 ( ) =3b3 ( ) +b2 ( ) =3×1+2 =5, ... 68 b43 ( ) =b2×21+1 ( ) = =b21 ( ) =b2×10 +1 ( ) =b10 ( ) =b2×5 ( ) =b5 ( ) +b4 ( ) =2+3 =5. A sucessão b n ( ) tem ainda as seguintes propriedades, que serão justificadas adiante: • Quaisquer termos consecutivos de b são primos entre si, logo cada número racional da forma b n ( ) b n +1 ( ) aparece na forma irredutível, para n≥0 . • Todos os racionais positivos aparecem uma e uma só vez na lista b n ( ) b n +1 ( ) ! " # $ # % & # ' #n≥0 . Mais adiante retomaremos a análise da sucessão b n ( ) , uma vez que esta terá uma relação estreita com a árvore que vamos abordar de seguida. O nome da referida árvore, Calkin-Wilf, liga os nomes de Neil Calkin e Herbert Wilf (19312012), dois reconhecidos matemáticos americanos. Wilf era especialista nas áreas da Combinatória e da Teoria dos Grafos e Calkin na área da Combinatória e Métodos Probabilísticos, particularmente no que respeita à Teoria dos Números. Calkin e Wilf fundaram juntos The Electronic Journal of Combinatorics, em 1994 (ver [29]). Esta árvore foi descoberta anteriormente por Jean Berstel e Aldo de Luca com a designação de árvore de Raney, uma vez que desenvolveram algumas ideias presentes num artigo de George Raney (ver [28] e [29]). À semelhança da árvore de Stern-Brocot, a árvore de Calkin-Wilf também mostra uma forma de enumerar os números racionais (ver [2] [9] e [26]). 69 Consideremos que 1 1 é a raiz da árvore e que a formação de filhos direitos e esquerdos segue a seguinte regra: a b (4) a a+b a+b b Aplicando repetidamente esta regra, pode obter-se o seguinte: 1 1 1 2 2 1 1 3 3 2 2 3 3 1 1 4 4 3 3 5 5 2 2 5 5 3 3 4 4 1 Figura 24: Primeiros níveis da árvore de Calkin-Wilf. A árvore que se obtém iterando este processo, apresenta as seguintes propriedades: Propriedade 1 O numerador e o denominador de cada fração da árvore são primos entre si. A prova desta afirmação será feita por redução ao absurdo. Suponhamos, assim, que existe uma fração a b cujos numerador e denominador não são primos entre si. 70 Como a propriedade enunciada é verdadeira para a raiz da árvore, ou seja, para 1 1 , a b não é a raiz, logo é filho direito ou esquerdo de algum outro vértice da árvore. - Se a b é um filho esquerdo, o seu progenitor é a b−a . Considerando que a e b não são primos entre si, então existe um número inteiro maior do que 1 que divide simultaneamente a e b , e, por consequência, também divide b−a . Assim, a b−a não estará na forma irredutível. - Por outro lado, se a b é um filho direito, o seu progenitor é a−b b . Do mesmo modo, se existe um número inteiro maior do que 1 que divide a e b , este também divide a−b e por isso a−b b , também não está na forma irredutível. Acabámos de mostrar que se a b é um vértice interior da árvore que não está na forma irredutível, então qualquer seu antecessor também não está na forma irredutível. A conclusão a que se chega é que a raiz da árvore não está na forma irredutível, o que é um absurdo. Concluimos, desta forma, que qualquer fração presente na árvore tem o numerador e o denominador primos entre si. Propriedade 2 Todos os racionais positivos aparecem nalgum vértice da árvore de Calkin-Wilf. Suponhamos que existe algum racional que não está na árvore. De entre todas as frações positivas e irredutíveis que não ocorrem na árvore, consideremos as de denominador mínimo. De entre estas, seja a b a que tem menor numerador. - Como a b não ocorre na árvore, em particular não é a raiz da árvore, logo a≠b . - Se a>b então a−b b é uma fração positiva e irredutível, porque m.d.c. a,b ( ) =1 , por hipótese. 71 Uma vez que a−b b tem o mesmo denominador que a b e tem numerador inferior, então a−b b ocorre na árvore. Mas então a b também ocorre, já que é filho direito de a−b b . Tal pode ser ilustrado, segundo a regra estabelecida em (4), da seguinte forma: a−b b ... a b - Se a<b então, como a b−a é uma fração positiva e irredutível com menor denominador que a b , esta fração ocorre na árvore. Do mesmo modo se pode ilustrar esta situação, segundo a referida regra (4): a b−a a b ... Assim, como a b−a aparece na árvore, a b também terá que aparecer, porque é filho esquerdo de a b−a . Chegamos assim a um absurdo, já que não pode existir tal fração a b . Conclui-se, desta forma, que todas as frações positivas aparecerão na árvore. 78 Bibliografia [1] Albert H. Beiler, Recreations in the theory of numbers: The queen of mathematics entertains, Dover Publications, 1966, pp. 169-172. [2] Neil Calkin & Herbert S. Wilf, Recounting the rationals, The American Mathematical Monthly, Vol. 107, Nº. 4, abril 2000, pp. 360-363. [3] L. R. Ford, Fractions, The American Mathematical Monthly, Vol. 45, Nº. 9, novembro 1938, pp. 586-601. [4] R. L. Graham, D. E. Knuth & O. Patashnik, Concrete mathematics, 2ª. edição, Addison-Wesley, 1994. [5] Samuel A. Lopes, Métodos Finitos em Matemática: sebenta do Mestrado em Matemática para Professores, FCUP, 2009. [6] António Machiavelo, Aritmética: as subtilezas dos números naturais, Treze viagens pelo mundo da matemática, 1ª edição, U.Porto editorial, 2010. [7] Helena Mena Matos & Teresa Carrapa, A Tautócrona, a Evoluta e o Relógio de Pêndulo de Huygens, Gazeta de matemática, Nº. 173, 2014. [8] José Carlos Santos, Números, 1ª edição, U. Porto editorial, 2014. [9] Katherine E. Stange, An arborist’s guide to the rationals, arXiv: 1403.2928. [10] A. A. Karatsuba & S. M. Voronin, The Riemann Zeta-Function, Berlim: Walter de Gruyter, 1992. [11] http://apprendre-math.info/portugal/historyDetail.htm?id=Farey, consultado em dezembro de 2013. [12] http://wikipedia.qwika.com/en2pt/John_Farey,_Sr., consultado em dezembro de 2013. [13] http://nrich.maths.org/6594, consultado em janeiro de 2014. [14] http://www-history.mcs.st-and.ac.uk/Biographies/Ford.html, consultado em janeiro de 2014. [15] http://en.wikipedia.org/wiki/René_Descartes, consultado em março de 2014. [16] http://www.maths.surrey.ac.uk/hostedsites/R.Knott/Fractions/fareySB.html#sbfulltree, consultado em abril de 2014. [17] http://en.wikipedia.org/wiki/Stern–Brocot_tree, consultado em abril de 2014. [18] http://www.ams.org/samplings/feature-column/fcarc-stern-brocot, consultado em maio de 2014. [19] http://www.homeschoolmath.net/teaching/rational-numbers-countable.php, consultado em maio de 2014. [20] http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Stern.html, consultado em maio de 2014. [21] http://en.wikipedia.org/wiki/Achille_Brocot, consultado em maio de 2014. 79 [22] http://cybergi.wordpress.com/2010/05/05/a-base-matemtica-dosmecanismos-steampunk/, consultado em maio de 2014. [23] http://pt.wikipedia.org/wiki/Moritz_Stern, consultado em maio de 2014. [24] http://en.wikipedia.org/wiki/Moritz_Abraham_Stern, consultado em maio de 2014. [25] http://planetmath.org/moritzstern, consultado em maio de 2014. [26] http://en.wikipedia.org/wiki/Calkin–Wilf_tree, consultado em junho de 2014. [27] http://marco.uminho.pt/~joao/Computacao2/node4.html, consultado em junho de 2014. [28] http://www-history.mcs.st-andrews.ac.uk/~history/Biographies/Wilf.html, consultado em junho de 2014. [29] http://en.wikipedia.org/wiki/Herbert_Wilf, consultado em junho de 2014. [30] http://www.educ.fc.ul.pt/icm/icm99/icm36/numeracao_binaria.htm, consultado em julho de 2014. [31] http://pt.wikipedia.org/wiki/Teoria_dos_grafos#cite_ref-Biggs_1-0, consultado em agosto de 2014. [32] https://pt.wikipedia.org/wiki/Leonhard_Euler, consultado em setembro de 2014. [33] http://www-history.mcs.st-and.ac.uk/Biographies/Euler.html, consultado em setembro de 2014. [34] http://pt.wikipedia.org/wiki/Sete_pontes_de_Königsberg, consultado em setembro de 2014. [35] http://www.mat.uc.pt/~alma/escolas/pontes/, consultado em setembro de 2014. [36] http://en.m.wikipedia.org/wiki/Dirichlet_series, consultado em setembro de 2014. [37] http://en.m.wikipedia.org/wiki/Particular_values_of_Riemann_zeta_function, consultado em setembro de 2014.