[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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



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