[obm-l] Problema da OBM - 2001

Tue, 10 Sep 2002 11:36:09 -0700

Alo colegas de lista
 
Essa mensagem � sobre o 6� problema do n�vel 3 da 3� fase da OBM do ano passado. A resolu��o de Humberto Silva Navaes pode ser vista na Eureka! n�13, 2002.
 
Na solu��o da segunda parte esta escrita abaixo:
 
-Nota��o: S(x) A: Somat�ria dos termos do tipo A para todos os valores de x pertencentes ao evento.
 

Sabemos que dada uma configura��o inicial, independente das escolhas dos movimentos sempre chegamos a uma configura��o onde � imposs�vel mover (configura��o parada). Suponha por absurdo que a partir de uma configura��o inicial se chegue a duas configura��es paradas distintas A e B.

Seja k' a posi��o da pedra mais � direita das configura��es A e B e k = k' + 2.

Considere o seguinte invariante: (n�o varia a cada movimento)

               I= S(x) F (k-pos(x)), onde Fn � o n-�simo n�mero de Fibonacci.

Lembramos que F1 = 1, F2 = 1 e Fn + 2 = Fn + 1 + Fn, para todo n � 1)

Sabemos que Ia=Ib ,pois I � invariante, isto �, permanece o mesmo depois de cada movimento.

De fato, Fk – (p – 1) = Fk – p + 1 = Fk – p + Fk – p – 1 = Fk – p + Fk – (p + 1), donde I n�o muda ap�s um movimento do tipo A, e F (k-(p-1)) + F (k-(p+2)) = F (k-p) + F (k-p-1) + F (k-p-2)= 2 F (k-p), donde I n�o muda ap�s um movimento do tipo B.

Algoritmo:

  1. Seja x a pedra mais � esquerda de A e y a pedra mais � esquerda de B.

    2. Devemos ter pos(x) = pos(y), pois se fosse pos(x) � pos(y) (assumimos sem perda de generalidade que pos(x) > pos(y)), ter�amos:

    Ia=S(t \in A) F (k-pos(t)), menor ou igual � F (k-pos(x)) + F (k-pos(x)-2) + F (k-pos(x)-4) + ... + F (2)

    se k-pos(x) for par e

    Ia= S(t \in A) F (k-pos(x)), menor ou igual � F (k-pos(x)) + F (k-pos(x)-2) + ... + F (3) caso contr�rio:

    Mas F (2) + ... + F (2k)=F(2k+1)-1, menor que F (2k+1) e F(3) + ... + F (2k+1)= F (2k+2)-1, menor que F (2k+2). (como se prova facilmente por indu��o).

    logo Ia � menor ou igual que F (k-pos(x)+1)-1, que � menor que F (k-pos(x)+1), menor ou igual �

    F(k-pos(y),menor ou igual que Ib, um absurdo!

  2. Seja A: = A – {x} e B: = {y}.

  3. V� para o 1.

Pronto! Demonstramos que A e B s�o a mesma configura��o, o que � um absurdo! A configura��o final independe da escolha dos movimentos.

Queria uma explica��o mais detalhada de cada passo e se isso implica que as duas configura��es s�o iguais por qu� se pode deduzir um invariante.

 

Andr� T.

 

 

Responder a