RE: [obm-l] Outro Problema Legal

["Paulo Santa Rita" <p_ssr@xxxxxxxxxxx>]

Ola Pessoal,

O tabuleiro pode ser IMAGINADO como uma matriz quadrada de ordem 10. 
Adotemos esta imagem
com a seguinte modificacao : as linhas e colunas estarao numeradas de 0 a 9. 
Fixado isso e notando
que um movimento nao interfere no outro, e facil perceber que :

1) Se Ci e a Coluna Inicial do objeto ( Ci = 0,1,...,9 ) entao apos N 
movimentos a Coluna Final Cf
sera tal que : Ci + 7*N = 10*q + Cf, para algum inteiro " q ".
2) Se Li e a Linha Inicial do objeto ( Li = 0,1,...,9 ) entao apos N 
movimentos a Linha Final Lf
sera tal que : Li + 3*N = 10*q' + Lf, para algum inteiro " q' ".

O enunciado informa que N=2004 e que a "casa" final deve ser um verfice, 
isto e :

Ci + 7*2004 = 10*q + Cf => Ci + 14028 = 10*q + Cf  onde Cf=0 ou Cf=9. 
Claramente que
se Ci=2 entao Cf=0  ou se Ci=1 entao Cf = 9. Assim, o objeto devera estar 
nas colunas 1 ou 2.

Mas, em qual linha ?

Li + 3*2004=10*q' + Lf  =>  Li + 6012 = 10*q' + Lf onde Lf=0 ou Lf=9. 
Claramente que
se Li=7 entao Lf=9 ou se Li=8 entao Lf=0.  Assim, o objeto devera estar nas 
linhas 7 ou 8.

Portanto, as valores validos para (Li,Ci) sao (7,1), (7,2), (8,1) e (8,2). 
Exemplificando, se ele partir
de (7,1) terminara em (9,9).

Observe que as equacoes Ci + 7*N=10*q + Cf  e Li + 3*N = 10*q' + Lf sao 
equivalentes a
7*N - 10*q = Cf - Ci  e  3*N - 10*q' = Lf - Li. Como MDC(7,10)=MDC(3,10)=1 
entao qualquer
posicao final e "ATINGIVEL" seja qual for a posicao inicial de onde 
partirmos, bastando tomarmos
um N ( numero de movimentos ) conveniente, pois, conforme nos sabemos, uma 
equacao
diofantina da forma a*x +  b*y = c tem solucao (x,y) no anel dos inteiros 
se, e somente se,
MDC(a,b) divide c.

PROBLEMA : Se, no problema do Benedito, os movimentos fossem 5 para a 
direita e 2 para baixo,
partindo de uma posicao inicial (Li,Ci) seriam ATINGIVEIS, apos um numero 
conveniente de
movimentos, qualquer posicao final ?

Um Abraco a Todos
Paulo Santa Rita
4,0955,250204

>From: "benedito" <benedito@digizap.com.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: <obm-l@mat.puc-rio.br>
>Subject: [obm-l] Outro Problema Legal
>Date: Tue, 24 Feb 2004 19:38:32 -0300
>
>PROBLEMA  24
>
>Considere um tabuleiro  10 × 10. Um "movimento" no tabuleiro se faz
>avançando 7 quadros para a direita e 3 quadros para baixo. No caso de se
>sair por uma linha se continua pelo começo (à esquerda) da mesma linha e no
>caso de acabar uma coluna se continua pelo começo da mesma coluna  (acima).
>
>Onde se deve começar para que depois de 2004 movimentos terminemos num
>vértice?
>
>
>
>Benedito

_________________________________________________________________
MSN Hotmail, o maior webmail do Brasil.  http://www.hotmail.com

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================