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