|
|
||||
Na RPM 10, p.52, propusemos o seguinte problema: Um professor sobrevive lecionando em três colégios. Qual é o melhor lugar para ele morar? Procura-se assim um ponto P que minimize a soma das distâncias a três pontos dados A1,A2, A3. Este problema é conhecido como problema de Fermat ou de Steiner e pode ser estendido para n pontos A1,... ,An. (O pobre professor leciona em n colégios!) Soluções exatas ou aproximadas para este problema são de enorme interesse quando se procura minimizar, por exemplo, o custo de redes telefônicas, rodovias ou redes de distribuição de água e esgoto. Apresentamos aqui uma resolução do problema para três pontos, A, B e C não colineares, subdividindo a análise em dois casos:
Fig.0l: O triângulo ABC tem todos os ângulos menores do que 120°: Neste caso o ponto P que minimiza a soma das distâncias aos vértices é o ponto interior ao triângulo que "olha" os três lados sob ângulos iguais. Fig.02: O triângulo ABC possui um ângulo CAB maior ou igual a 120°: Neste caso, o ponto que minimiza a soma das distâncias aos vértices é o vértice A. A primeira observação a ser feita é que podemos neste problema nos restringir a procurar a solução em pontos da região triangular (formada pelo triângulo e seus pontos interiores). Isto é conseqüência do fato que, dado um ponto Q exterior ao triângulo é sempre possível encontrar um ponto Q' no triângulo ABC tal que QA + QB + QC > Q'A + Q'B + Q'C. A prova deste fato está esquematizada no desenho acima. Temos que considerar, separadamente, os pontos das duas regiões do plano (Q = Q1, Q = Q2) I) Vamos considerar primeiramente o caso em que os ângulos do triângulo ABC não excedem 120° (Fig.4). Queremos encontrar o valor mínimo para d = AP + BP + CP, onde P é um ponto de região triangular fechada. Girando o triângulo APB de 60° com centro em B, obtemos C'P'B. ABC e BPP' são triângulos equiláteros. Observamos que AP + BP + CP = CP' + P'P + PC, ou seja d é o comprimento da poligonal CP'PC. Concluímos então que d será mínima se os pontos C, F',P e C estiverem alinhados . Neste caso, teremos e .
Então o ponto, P, para o qual d é mínima é o que "olha" os lados AB,BC e AC de 120°. Nos triângulos com ângulos menores que 120°, é sempre possível determinar este ponto P, conhecido como ponto de Fermat. As construções serão dadas a seguir. Observamos que, se o ângulo BAC é de 120°, obtemos CAC alinhados e portanto a solução para o nosso problema é P = A. II) Suponhamos agora que o triângulo ABC tenha um ângulo, A, maior que 120°. Vamos mostrar que o ponto-solução para o problema de Steiner é o vértice A. Isto é: AP + BP + CP> AB + AC.
Girando o triângulo APB em A de tal maneira que o triângulo obtido B'P'A tenha B',A e C alinhados, temos PÂP' < 60°. Isto implica que P'P < AP. Então d = AP + BP + CP > P'P + B'P + PC, ou seja, d é maior que o comprimento da poligonal B'P'PC, que por sua vez é maior que o segmento B'C. Temos então: AP + BP + CP > B'C = B'A + AC = AB + AC. Concluímos portanto as provas das afirmações feitas em i) e ii). O Ponto de Fermat Uma determinação do ponto de Fermat (para triângulos com ângulos menores que 120°) é feita a partir da construção feita em (I). Repetimos o processso para os demais vértices, a partir de triângulos equiláteros ABC, ACB' e BC A'. Observamos que o valor mínimo para a soma das distâncias aos vértices é o comprimento de qualquer um dos segmentos AA', BB' ou CC. Outra forma de se determinar o ponto de Fermat P ê baseada na constatação feita em (I) de que este "olha" todos os lados do triângulo sob um ângulo de 120° : P é determinado pela intersecção dos arcos-capazes correspondentes (Fig. 7).
A figura 8 ilustra a construção de Steiner utilizada nos algoritmos computacionais. Esta é uma combinação das duas anteriores. Observações - Usando propriedades da elipse, obtemos uma outra forma de concluir que, quando a solução P do problema de Steiner está na região interior do triângulo, este ponto tem que olhar os lados sob um ângulo de 120°. Consideramos a elipse de focos B e C passando pela solução P. Entre os pontos da elipse, P tem que ser o mais próximo de A. Para que isso aconteça e tem que ser iguais (propriedade reflexiva da elipse). Fazendo o mesmo raciocínio para a elipse de focos A e B passando por P, concluímos que os ângulos , e são iguais. (Esta é a idéia de nossa primeira resolução para o problema e também da solução enviada por Eduardo Wagner.) - A procura de um ponto que minimize a soma das distâncias a n pontos dados já aparece nos trabalhos de Jacob Steiner (1786-1863), professor de Matemática na Universidade de Berlin. A generalização mais significativa para o problema aqui apresentado (também conhecida como problema de Steiner generalizado) é a procura da rede mínima de comunicação entre n pontos dados. Ou seja: Dados n pontos, determinar um sistema conexo de segmentos retilínios que os una e que tenha comprimento mínimo (Fig. 10). A solução nem sempre é univocamente determinada. Atualmente existem programas computacionais capazes de resolver este problema para quinze pontos em apenas uma hora, utilizando-se um computador de grande porte. Entretanto, ao se aumentar o número de pontos para, por exemplo, 100, verifica-se que, com os algoritmos atuais, mesmo o mais rápido computador levaria milhares de anos para encontrar soluções. Este fato tem levado à procura de processos que dão soluções aproximadas para o problema, em geral um tanto mais longas que a ótima, mas factíveis de serem obtidas computacionalmente. Um artigo recente que discute este assunto é The Shortest-Network Problem, Scientific American, janeiro de 1989, p. 66 a 71. - Vários leitores chamaram nossa atenção para o fato de que o problema aqui apresentado foi proposto por Pierre de Fermat (1601-1665) a Evangelista Torricelli (1608-1647) e não o contrário, como consta em Onde Morar? , RPM 10. "De fato, na maior parte da bibliografia que consultamos posteriormente é esta a versão que aparece. (A afirmação que fizemos no artigo foi retirada do livro: C. De Comberouse, Cours dAlgèbre Supérieure, Gauthier-Villars, 1904.) O primeiro registro conhecido de solução para este problema no caso de três pontos é de cerca de 1640, com resoluções independentes de Evangelista Torricelli e Francesco Cavalieri. Foi o leitor João Linneu de Almeida Prado, Jaú, SP, quem primeiro nos alertou para a grande contribuição de J. Steiner para o caso geral do problema que hoje leva seu nome. - Outras duas bonitas resoluções do problema de Steiner para três pontos são as que se utilizam do teorema de Viviani (discípulo de Galileu e Torricelli) e do teorema de Ptolomeu (Alexandria, séc. II). Referências: Dõrrie, H., 100 great problems of elementary Mathematics, New York Dover, 1965, p. 361-365; Padoc, D. A course oí Geometry for colleges and universities, Cambridge Univ. Press, 1970 (Sugestões de Sérgio Rodrigues, São Carlos, SP). A simplicidade da resolução que apresentamos neste trabalho envolveu um trabalho de síntese de muitas consultas. Principais referências: Courant, C. e Robbins, H., Qué es Ja Matemática.?; H. S. Coxeter, Introduction to Geometry, Wiley, New York, 1969; D. Sokplowsky, A note on the Fermat Ptoblem, The American Mathematical Monthly, vol. 83, 1976, p. 276. - Também enviaram sugestões para a solução do problema Onde Morar. Francisco Mauro, Fortaleza, CE; Pedro Paulo Martins, Três Corações, MG; Marcelo Lower, SP. - Os dois artigos a seguir complementam este trabalho. O primeiro traz uma interessantíssima resolução mecânica para o problema, enviada por Eduardo Wagner. O segundo, enviado por Sérgio Rodrigues, utiliza cálculo diferencial para fazer um rastreamento das soluções possíveis para o problema de Steiner no caso de n pontos. Não percam! - Registramos aqui a participação de Sérgio Rodrigues, Sávio Rodrigues, Marcelo Firer e do grupo editorial da RPM que discutiram o problema conosco e deram importantes sugestões.
|