----- Original Message -----
Sent: Friday, October 25, 2002 8: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.