2013/2/24 Lucas Prado Melo <luca...@dcc.ufba.br>
> 2013/2/23 Mauricio de Araujo <mauricio.de.ara...@gmail.com>
>
>> 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.
>
Uma correção:
Na verdade a recorrência é S_n = n S_{n-1} + n + S_{n-1},
Isso dá S_n + 1 = (n+1)(S_{n-1} + 1). Que, como Douglas mostrou, dá S_n =
(n+1)! - 1.
--
[]'s
Lucas
