On Wed, Nov 27, 2002 at 01:37:53PM -0300, Johann Peter Gustav Lejeune Dirichlet wrote: > > Essa questao de Geometria e "so pra macho",segundo o cara que me propos.Eu > consegui achar uma soluçao viajada demais mas valida.Vamos ver como esses > caras se saem: > > Considere um quadrado de diagonal 2^(1/2) decomposto em varios poligonos de > diametro no maximo 30^(-1).Demonstre que existe um poligono com pelo menos > seis vizinhos(poligonos vizinhos=contem pelo menos um ponto em comum)
A questão é bem legal mas se entrasse em uma olimpíada não contaria como geometria... e o diâmetro é muito menor do que o necessário... Vou supor que os polígonos são convexos mas o caso geral não é muito mais difícil. Podemos supor sem perda de generalidade que não existem quatro polígonos com um ponto comum (se existirem perturbe um pouco perto da quadrupla fronteira) e que polígonos vizinhos sempre têm um lado em comum. Pegue o polígono P0 que contem o centro do quadrado. Se ele tem >= 6 vizinhos acabou. Senão ele tem k <= 5 vizinhos P1, ..., Pk em roda. P1 e P2 têm outro vizinho comum além de P0 (do outro lado); chamemos este vizinho de P(k+1). Analogamente P(k+i) é vizinho de Pi e P(i+1) para i < k e P(2k) é vizinho de Pk e P1. A esta altura P1 já tem 5 vizinhos: P0, P2, Pk, P(k+1) e P(2k) (a rigor você deve considerar também o caso de P(k+1) e P(2k) serem *iguais*; este caso fica a cargo do leitor). Se existir outro vizinho acabou, senão P(k+1) e P(2k) devem ser vizinhos. Analogamente, para que P2, ..., Pk tenham <= 5 vizinhos devemos ter P(k+1),...,P(2k) em roda. A esta altura cada um destes k polígonos tem 4 vizinhos assim para que nenhum deles ganhe mais de 1 novo vizinho seria necessário ter um único polígono dando a volta, que não seria convexo. Assim, demonstramos que dado um polígono ou ele, ou um vizinho dele, ou um vizinho de um vizinho dele tem >= 6 vizinhos. Se o diâmetro dos polígonos é d estes polígonos todos estão contidos em uma bola de raio 3d. Assim 1/7 (ao invés de 1/30) já estaria bom. Tenho outra demonstração, talvez depois eu mande. []s, N. ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> =========================================================================