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