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 + Fkp – 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!

  3. Seja A: = A – {x} e B: = {y}.
  4. 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