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