Triângulos em Arranjos de Retas no Plano Euclideano

Abstract: This paper is about the induction exercise 2.17 from the book ``Introduction to Algorithms: A Creative Approach,'' by Udi Manber: {\em Consider $n\geq 3$ straight lines, in general position, on the Euclidean plane. Prove that these lines create, at least, $n-2$ triangles}. The paper includes a bibliographic research that tells a very interesting story about the solution of this exercise. The main contribution of the paper are three counter-examples to the most common approach, that help explain why it is so hard to obtain a simple inductive proof. We also present a simplified version of a recent proof by counting arguments. \par (This article has been submitted to the Brazilian journal {\em Matemática Universitária}.)



Resumo: Este artigo discute o problema de indução 2.17 do livro ``Introduction to Algorithms: A Creative Approach,'' de Udi Manber: {\em Considere $n\geq 3$ retas, em posição geral, no plano Euclideano. Prove que estas retas formam, pelo menos, $n-2$ triângulos}. Ele apresenta uma pesquisa bibliográfica que revela uma história bem interessante sobre a resolução deste problema. A contribuição principal do artigo são três contra-exemplos para a abordagem mais comum, que ajudam a explicar a dificuldade em se obter uma prova indutiva simples. Também é apresentada uma versão simplificada de uma recente demonstração por argumentos de contagem. \par (Este artigo foi submetido para a revista {\em Matemática Universitária}.)

2000