O Problema do Final Feliz

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Este artigo não cita fontes fiáveis e independentes. (desde setembro de 2013). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)
Wikitext.svg
Este artigo ou seção precisa ser wikificado (desde setembro de 2013).
Por favor ajude a formatar este artigo de acordo com as diretrizes estabelecidas no livro de estilo.

O Problema do Final Feliz, nomeado por Paul Erdős porque isso levou ao casamento de George Szekeres e Esther Klein é afirmado a seguir:

Qualquer conjunto de cinco pontos em um plano em uma posição qualquer tem um subconjunto de quatro pontos que formam os vertices de um quadrilátero convexo.

Isso foi um dos resultados originais que levaram ao desenvolvimento da Teoria de Ramsey.

O Teorema do Final Feliz pode ser provada através de uma analise de casos: Se quatro ou mais pontos são vértices de involucro convexo, qualquer um dos quatro pode ser escolhido. Se por um lado o conjunto de pontos tiver a forma de um triangulo com dois pontos dentro dele, os dois pontos internos e um dos outros três pode ser escolhido.

A conjectura de Erdos-Szekeres enuncia precisamente uma relação mais geral entre números de pontos e um conjunto de pontos em uma posição geral e o maior polígono convexo.

Polígonos maiores[editar | editar código-fonte]

Erdõs e Szekeres provaram a seguinte generalização:

Teorema. Para qualquer inteiro positivo N, qualquer conjunto finito suficientemente grande em um plano em uma posição geral tem um subconjunto de N pontos que formam os vértices de um polígono convexo.

Faça f(N) denotar um minimo M para o qual qualquer conjunto de M pontos em posição geral contem um N-ágono.

  • f(3) = 3, trivial.
  • f(4) = 5.
  • f(5) = 9.
  • f(6) = 17
  • O valor de f(N) é desconhecido para qualquer N > 6; pelo resultado de Erdõs & Szekeres (1935) é tido como finito.

Na base dos valores conhecidos de f(N) para N = 3,4 e 5, Erdõs e Szekeres conjecturaram em seu artigo original que

f(N) = 1 + 2^{N-2} \quad \mbox{para todo } N \geq 3.

Eles provaram posteriormente, por construção de exemplos explícitos, que

f(N) \geq 1 + 2^{N-2},

mas o melhor limite superior quando N ≥ 7 é

f(N) \leq {2N-5 \choose N-2} + 1 = O\left(\frac{4^N}{\sqrt N}\right).

Polígonos vazios[editar | editar código-fonte]

Alguém também pode considerar o questão de se qualquer conjunto de pontos suficientemente grande tem um quadrilátero vazio, pentágono, etc., isso é, um que não contem nenhum outro ponto interior. A solução original para o problema do Final Feliz pode ser adaptado para mostrar que quaisquer cinco pontos em posição geral contem um quadrilátero convexo vazio, e quaisquer dez pontos em posição geral contem um pentágono convexo vazio. No entanto, existem arbitrariamente um conjunto de pontos grande que contem um heptágono não vazio.

Por um bom tempo esse questionamento da existência de hexágonos continua aberta, mas Nicolás (2007) e Gerken (2008) provaram que todo conjunto de pontos suficientemente grande em posição geral contem um hexágono convexo vazio. Mais especificamente, Gerken mostrou que o numero de pontos necessários não é mais que f(9) para a mesma função f definido acima, enquanto Nicolás mostrou que o numero de pontos necessários é mais que f(25). Valtr (2006) supriu a simplificação da prova de Gerken que apesar de requerer mais pontos, f(15) ao invés de f(9). Pelo menos 30 pontos são necessários: existe um conjunto de 29 pontos em posição geral com nenhum hexágono convexo vazio.

Problemas relacionados[editar | editar código-fonte]

O problema de encontrar conjuntos de n pontos minimizando o número de quadriláteros convexos é equivalente à minimização do Crossing Number em um desenho de uma linha reta de um grafo completo. O número de quadriláteros deve ser proporcional ao quarto da potência de n, mas a constante de previsão não é conhecida.

A demonstração é direta, em espaços Euclidianos dimensionais maiores, conjuntos de pontos suficientemente grandes terão um subconjunto de k pontos que formam os vértices de um politopo convexo, para qualquer k maior que a dimensão: isso segue imediatamente a existência de um k-ágono convexo em conjuntos de pontos planares de tamanho suficiente, por projetar um conjunto de pontos maior em um sub-espaço arbitrário 2-dimensional. Entretanto, o números de pontos necessários para achar k pontos in posição convexa pode ser menor em maiores dimensões do que a do plano, e é possível de achar subconjuntos que são altamente reprimidos. Em particular, em d dimensões, todo d + 3 pontos em posição geral contem um subconjunto de d + 2 pontos que formam os vértices de um politopo cíclico. Mais geralmente, para todo d e k > d existe um numero m(d,k) tal que todo conjunto de m(d,k) pontos em posição geral contem um subconjunto de k pontos que formam os vértices de um politopo.

Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.