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

[João Gilberto Ponciano Pereira <jopereira@xxxxxxxxxxxxx>]

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