2013/2/23 Mauricio de Araujo <[email protected]>
> Os números 1, 2, ..., 20 são escritos em um quadro negro. Podemos apagar
> dois deles a e b e escrever no lugar o numero a+b+ab. Após muitas
> operações ficamos apenas com um numero.
> Qual deve ser esse numero?
>
>
O invariante vai ser a soma dos termos a_i1 * a_i2 * ... * a_ir, para cada
combinação {i1, i2, ..., ir} do conjunto {1, 2, 3, ..., n}.
Na sequência sem o 'a' e 'b' mas com a+b+ab (a sequência transformada), o
termo (a + b + ab) * x na forma acima está associado a 3 termos distintos
da sequência original: a*x, b*x e ab*x.
A volta também é verdadeira: dá pra agruparmos 3 termos da sequência
original para formarmos este termo na sequência transformada. Ou seja, a
invariante existe.
Então precisamos obter justamente esta soma.
Basta então lançarmos mão sobre a recorrência S_n = a_n*S_{n-1} + S_{n-1} =
n*S_{n-1} + S_{n-1}. Ela soma os termos com o "n" e sem o "n".
Assim S_n = (n+1) S_{n-1}
Como S_1 = 1, S_n = (n+1)!/2.
--
[]'s
Lucas
