2013/6/11 Henrique Rennó <henrique.re...@gmail.com>
> Acho que a solução que coloquei está errada. Pensando nos expoentes de
> forma crescente: se for apenas o peso 2^0 ele tem que estar no prato da
> direita. Acrescentando o peso 2^1, ele deve ir para o prato da direita e o
> peso anterior tem 2^1 possibilidades. Acrescentando o peso 2^2, ele deve ir
> para o prato da direita e os outros pesos tem 2^2 possibilidades.
> Acrescentando o peso 2^3, ele deve ir também para o prato da direita e
> todos os outros 3 poderiam estar em um dos dois pratos, num total de 2^3
> possibilidades. Assim, como o maior pesos é 2^100, existem 2^100
> possibilidades.
>
> Eu consegui um valor bem maior que 2^100 pq eu supus que é possível
colocar os números em qualquer ordem:
201 x 199 x 197 x ... x 5 x 3 x 1
Podemos reinterpretar a questão transformando em bolinhas numeradas de 1 a
n, se uma bolinha for colocada no prato direito, todas as bolinhas menores
podem ser colocadas no prato esquerdo.
Seja F(n) o número de possibilidade para n bolinhas.
Se a i-ésima bolinha for colocada primeiro, a colocação das i-1 bolinhas
menores que ela não afetam em nada o cálculo (podem ser colocadas em
quaisquer lugares) e as n-i bolinhas maiores vão ser posicionadas em F(n-i)
formas possíveis (considerando somente a posição relativa delas).
Assim F(n) = soma_{1 <= i <= n} { 2^(i-1) (n-1)C(i-1) (i-1)! F(n-i) }
Onde nCk é o número de combinações de n, k a k.
A idéia aqui é, das n-1 posições restantes, reservar i-1 para as bolinhas
menores que a i-ésima e aplicar o princípio multiplicativo em duas ocasiões:
1) Permutando as i-1 bolinhas nas i-1 posições reservadas: (i-1)!
2) Decidindo em que prato cada bolinha vai ficar: 2^(i-1)
Daí só falta escolher a posição relativa das n-i bolinhas restantes, o que
é representado pela multiplicação por F(n-i).
A expressão fica difícil assim. É melhor transformar F(n-i) em F(i), assim
substituimos i por n-i:
F(n) = soma_{1 <= n - i <= n} { 2^(n-i-1) (n-1)C(n-i-1) (n-i-1)! F(i) }
= soma_{0 <= i < n } {2^(n-1) (n-1)! F(i) / (2^i i!) }
O que acontece quando passamos de F(n) para F(n+1)?
Surge uma parcela F(n) que não existia antes e as outras parcelas são as
mesmas só que escaladas de 2n.
Assim F(n+1) = F(n) + 2nF(n) = (1+2n)F(n)
Assim F(1) = 1, F(2) = 1 x 3, F(3) = 1 x 3 x 5 ... F(101) = 201 x 199 x 197
x ... x 5 x 3 x 1
--
[]'s
Lucas
--
Esta mensagem foi verificada pelo sistema de antivírus e
acredita-se estar livre de perigo.
