Eu pensei também no problema e vou mostrar o que pensei pra que possam me
mostrar o erro, se houver.
Como 2^0+2^1 + . . . + 2^{99} = 2^{100} -1 < 2^{100}, então não importa
a forma que distribuímos os pesos, o prato com 2^{100} gramas sempre será
mais pesado. Então, o peso com 2^{100} gramas deverá ficar no prato
direito. Tendo isto, não importa como distribuímos os outros 100 pesos, o
prato esquerdo nunca será mais pesado que o direito.
Daí pensei de quantas formas podemos distribuir esses 100 pesos.
Interpretei que cada escolha de pesos pro prato direito seria equivalente a
um subconjunto de {2^0, 2^1, . . ., 2^{99}}, onde concluí que teria
2^{100} maneiras de distribuir esses pesos entre os pratos (considerando
que um prato pode ficar vazio).
Foi isso o que pensei.
Em 11 de junho de 2013 16:06, Lucas Prado Melo <[email protected]>escreveu:
> 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.
