RE: [obm-l] Problema do torneio das Cidades

[Johann Peter Gustav Lejeune Dirichlet <peterdirichlet2002@xxxxxxxxxxxx>]

Na verdade eu generalizei um pouco,pois n=5 no original.Mas tenho que ver,pois a soluçao empirica era 15 e era obtida passando as diagonais pulando algumas colunas.

 

/  /  /

/  /  /

/  /  /

/  /  /
/  /  /
 

João_Gilberto_Ponciano_Pereira <jopereira@vesper.com.br> wrote:

Não sei se entendi direito o problema, mas acho que dá para resolver assim:

Suponha que vc conhece a solução otimizada. Vamos dar uma olhada na borda
inferior do reticulado:
Imagine que nesta borda você tenha a configuração do tipo
/ \. Neste caso, podemos inverter a segunda diagonal de forma a termos a
configuração // sem alterar o número de diagonais do reticulado. O mesmo
raciocínio podemos utilizar para configurações do tipo:
/
/
podemos "descer" a diagonal de cima de forma a mais uma vez termos a
configuração //.
Temos também o caso
\
/
que invertendo a diagonal de cima, também ficaria //.

Fazendo o mesmo para a coluna da esquerda, podemos concluir que existe uma
configuração final otimizada no formato
/
/
/
/
/ / / / / / / / / / /

Neste caso, podemos "arrancar" estas duas linhas e duas colunas e continuar
o problema para um nível inferior (n-2) *(n-2).

Logo, seja D(n) o número diagonais para um reticulado de nxn, com n ímpar,
temos que:
D(1) = 1
D(n+2) = D(n) + 2n+3

Desenvolvendo, temos que d(n) = (n^2+n)/2


-----Original Message-----
From: Johann Peter Gustav Lejeune Dirichlet
[mailto:peterdirichlet2002@yahoo.com.br]
Sent: Friday, June 06, 2003 4:35 PM
To: obm-l@mat.puc-rio.br
Subject: [obm-l] Problema do torneio das Cidades


Ola turma!!!Estrou ha dias pensando nesse problema mas nada me ocorreu:
Considere um reticulado n*n, n impar.Nele destacamos alguns segmentos de
comprimento 2^(0,5) ligando dois pontos quaisquer desse reticulado,de modo
que esses segmentinhos nao tenham pontos em comum (nem mesmo extremidades).
Calcule o maximo desses segmentos que podem aparecer.




_____

Yahoo! Mail
Mais espaço, mais segurança e gratuito: caixa postal de 6MB, antivírus,
proteção contra spam.

=========================================================================
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
=========================================================================

---

Yahoo! Mail 
Mais espaço, mais segurança e gratuito: caixa postal de 6MB, antivírus, proteção contra spam.