Olá,LucasNão entendi bem a passagem ´´...a colocação das i-1 bolinhas menores não afetariam em nada o cálculo...´´ O que significa ´´escaladas de 2n´´?Vc poderia detalhar um pouco mais essa parte: F(n+1) = F(n) + 2nF(n)?Uma coisa que eu não pensaria foi considerar a somente a posição relativa dasbolinhas maiores: F(n-i)Obrigado.
From: [email protected] Date: Tue, 11 Jun 2013 16:06:16 -0300 Subject: [obm-l] Re: [obm-l] Re: [obm-l] questão bacana(quase me tira o sono) To: [email protected] 2013/6/11 Henrique Rennó <[email protected]> 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. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo.
