RES: problema

["M. A. A. Cohen" <mcohen@xxxxxxxxxx>]

Para que ver que eh invariante, considere os casos possiveis:
Se de um estado generico (a,b,c) voce retirar um da cor de a, e um da cor de
c, voce vai ficar com o estado (a-1, b+2, c-1). Se vc olhar para a diferenca
de dois deles, vai ver que essa diferenca eh sempre congruente a diferenca
original modulo 3. (de fato, a-1-(b+2) = (a-b)-3 = a-b mod 3, e
(a-1)-(c-1)=a-c ).
Qualquer outro caso eh analogo (basta renomear as cores retiradas q vc cai
no anterior). Portanto, a diferenca entre dois termos quaisquer tomada mod 3
eh um invariante do problema.

Para que na situacao final voce tenha (0,0,k) (i.e, sobraram k chips da cor
3 apenas) entao eh necessario que a tripla inicial (a,b,c) satisfaça b=a
mod3 e c-b=k mod3 (pq nesse caso voce tem 0-0=0 mod 3 e k-0 = k mod3). Como
k eh qualquer, uma condicao necessaria para que ao final soh haja chips da
cor 3 eh que a=b mod 3.

Por outro lado, comecando com uma configuracao satisfazendo a=b mod 3, eh
sempre possivel terminar com tudo da mesma cor. Basta sempre retirar 1 de a
e 1 de b.

Agora, tem uma coisa meia estranha no modo como vc deu o enunciado. A unica
maneira de o processo chegar ao "final" eh se tiver 2 cores zeradas. Se nao
houverem 2 cores zeradas, vc sempre pode continuar... o enunciado poderia
ser: 'de uma condicao para que se consiga chegar ao estado em que apenas uma
cor existe.' O unico caso em que isso nao ocorre eh quando as qtds de cores
sao as 3 possiveis classes mod 3: 0,1,2. Nesse caso, vc nunca consegue
"terminar".

Marcio

-----Mensagem original-----
De: owner-obm-l@mat.puc-rio.br [mailto:owner-obm-l@mat.puc-rio.br]Em
nome de Marcelo Souza
Enviada em: domingo, 29 de julho de 2001 00:05
Para: obm-l@mat.puc-rio.br
Assunto: problema


Esse problema aki tem uma solução que eu naum entendi, se alguém pudesse me
explicar eu seria grato
"Dados a chips brancos, b chips pretos, c chips vermelhos em cima de uma
mesa. Escolhemos dois De cores diferentes e substituimos cada um pelo de
terceira cor. O processo se repete. Diga a condição que deve haver entre os
numeros a,b e c para que ao final todos os chips sejam da mesma cor."
A solução começa no caso inicia, (a,b,c) que após o primeiro passo pode
passar a ser (a+2, b-1, c-1); ou (a-1,b+2,c-1); ou (a-1,b-1,c+2). A solução
diz que em qquer caso I = a-b mod 3. E diz que b-c=0 mod 3 e
a-c=0 mod 3 são invariantes, naum entendi essa parte, pq eles são congruos a
zero mod 3???
abraços
M.

_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp