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

[Johann Peter Gustav Lejeune Dirichlet]

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 [EMAIL PROTECTED] 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 bordainferior do reticulado:Imagine que nesta borda você tenha a configuração do tipo/ \. Neste caso, podemos inverter a segunda diagonal de forma a termos aconfiguração // sem alterar o número de diagonais do reticulado. O mesmoraciocínio podemos utilizar para configurações do tipo://podemos "descer" a diagonal de cima de forma a mais uma vez termos aconfiguraçã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 umaconfiguração final otimizada no formato/ / / / / / / / / / /Neste caso, podemos "arrancar" estas duas linhas e duas colunas e continuaro
 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) = 1D(n+2) = D(n) + 2n+3Desenvolvendo, temos que d(n) = (n^2+n)/2-Original Message-From: Johann Peter Gustav Lejeune Dirichlet[mailto:[EMAIL PROTECTED]Sent:: Friday, June 06, 2003 4:35 PMTo: [EMAIL PROTECTED]Subject: [obm-l] Problema do torneio das CidadesOla turma!!!Estrou ha dias pensando nesse problema mas nada me ocorreu:Considere um reticulado n*n, n impar.Nele destacamos alguns segmentos decomprimento 2^(0,5) ligando dois pontos quaisquer desse reticulado,de modoque 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 emhttp://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.

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

[João Gilberto Ponciano Pereira]

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:[EMAIL PROTECTED]
Sent: Friday, June 06, 2003 4:35 PM
To: [EMAIL PROTECTED]
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  http://br.mail.yahoo.com/ 
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
=