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