Re: [obm-l] E o Nivel Tres,ninguem faz nada??????

[Domingos Jr.]

Eu tamb�m tive uma id�ia para o problema 3:   No caso 2x2 � f�cil ver que existe um elemento i vizinho de i+3, supondo (um argumento de indu��o) que isso vale para guaquer tabuleiro de dimens�es at� m x n, pegamos um tabuleiro maior que m x n. Neste tabuleiro podemos visualizar um caminho de casas vizinhas, como voc� prop�s. Dentro deste caminho, de duas uma: i) ou ocorre um (ou v�rios) retorno(s) fechado(s), comprovando a nossa tese ii) em um dado momento h� um trecho desse tabuleiro cercado por um caminho (pois voc� s� est� fazendo retornos abertos, e o caminho deve passar por todas as casas do tabuleiro).   no caso (ii) o trecho do tabuleiro cercado por um caminho pode ser considerado com um sub-tabuleiro menor do que o tabuleiro original e por tanto, pela hip�tese de indu��o ele possui um retorno fechado.   Fica dif�cil atrav�s de uma mensagem eletr�nica justificar o argumento em (ii), mas ele � bem simples se vc simplesmente desenhar o caminho. Fazendo s� retornos abertos, voc� sempre est� deixando um sub-tabuleiro para ser percorrido.   Alguma opini�o a respeito?   [ ]'s ----- Original Message ----- From: Eduardo Casagrande Stabel To: [EMAIL PROTECTED] Sent: Friday, October 25, 2002 7:36 PM Subject: Re: [obm-l] E o Nivel Tres,ninguem faz nada?????? Ol� Pessoal.   Eu encontrei uma solu��o para a quest�o 3 do n�vel 3, e gostaria de saber se est� boa.   Quest�o 3. Numeramos os quadrados de um tabuleiro m x n, onde m, n >=2 com os n�meros 1, 2, 3, ..., mn. Dois n�meros vizinhos est�o em casas vizinhas (=casas com uma aresta em comum). Mostrar que existem um n�mero i tal que i e i+3 est�o em casas vizinhas.   A minha id�ia foi construir um tabuleiro  X,  m-1 x n-1 que liga o centro de duas casas vizinhas. Nesse tabuleiro ligamos o segmento que une o centro de casas vizinhas, se elas possuem n�meros consecutivos. Repare que no tabuleiro X formamos um caminho fechado que passa por todos os v�rtices de seus quadrados. A primeira coisa agora � reparar que n�o pode o tabuleiro X estar circundado por esse caminho, pois haveria nas bordas uma seq��ncia i, i+1, i+2, i+3, ..., i , i+1, ... sempre crescente, uma contradi��o. Portanto existe um buraco na borda de X. O argumento final. Sobre cada ladinho do caminho levante uma parede, voc� vai formar um labirinto. Deixe um rato (que n�o anda para tr�s) entrar por um dos buracos da borda. H� tr�s possibilidades: (1) ele sai por outro buraco na borda, a� o caminho sobre X teria duas partes separadas, o que n�o ocorre; (2) ele encontra um ciclo infinito dentro do labirinto, e nunca sai dele, isso tamb�m n�o pode ocorrer pois a parte de dentro e de fora desse ciclo estaria deconectando o caminho; (3) ele chega num beco sem sa�da. Todo beco sem sa�da � caracterizado por um quadradinho com uma parede faltando e as outras tr�s ocupadas, logo caracteriza o caso i, i+3 vizinhos.   Abra�o, Eduardo.