[obm-l] Problema da OBM - 2001

["Wagner" <timpa@xxxxxxxxxx>]

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 F_n é o n-ésimo número de Fibonacci.

Lembramos que F₁ = 1, F₂ = 1 e F_n + 2 = F_n + 1 + F_n, para todo n ³ 1)

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

De fato, F_{k – (p – 1)} = F_{k – p} + 1 = F_{k – p} + F_k – p – 1 = F_{k – p} + F_k – (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.

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.