2013/6/13 Ralph Teixeira <ralp...@gmail.com> > > Que tal assim -- pense numa maneira de colocar os pesos como uma fila de > pesos (na ordem em que eles serao colocados) E TAMBEM um bando de post-its, > um pregado em cada peso, com as letras D ou E dizendo onde aquele peso vai. > > Entao, seja F(n) o numero de maneiras de montar uma fila com os N pesos > 2^0,...,2^(N-1) satisfazendo as condicoes do enunciado (isto eh, numa ordem > e escolhendo os post-its de forma que, ao colocar os pesos da fila nos > pratos o lado esquerdo nunca pese mais que o direito). Note que o numero de > maneiras de colocar os pesos 2^1,...,2^N na maneira do enunciado tambem eh > F(N) (afinal eu soh multipliquei todos os pesos por 2). > > Para encontrar uma maneira de colocar os pesos 2^0, 2^1,...,2^N, voce vai > ter que fazer o seguinte: > i) Decida a ordem e o lado onde voce vai colocar 2^1, 2^2, ..., 2^N. Ha > F(N) maneiras de fazer isto. > ii) Agora voce vai ter que encaixar o 2^0 em alguma posicao -- sao N+1 > posicoes, a saber "antes do 1o" ou "entre o 1o e o 2o" ou ... "em ultimo". > Mas, se voce colocar ele no inicio da fila, teria que ser com o post-it D > (direito); em qualquer outra das N posicoes, vale D ou E. Entao sao 2N+1 > opcoes para encaixar o peso 2^0 na fila. > > Assim, para cada 1 maneira de botar os N pesos 2^1, 2^2, ..., 2^N, > ha exatemente 2N+1 maneiras (distintas!) de botar os N+1 pesos 2^0, > 2^1,..., 2^N. > > Note que esta correspondencia eh biunivoca no seguinte sentido: se voce me > der uma maneira de botar os N+1 pesos, eu jogo fora o peso 2^0 e sigo a sua > ordem (e post-its) para colocar os N pesos 2^1, 2^2, ..., 2^N dum jeito > valido! > > Entao F(N+1)=(2N+1).F(N). Como F(1)=1, vem F(2)=3, F(3)=3x5, F(4)=3x5x7, > etc.. > > Em suma, F(N)=1x3x5x7x....x(2N-1) e F(101)=1x3x5x7x...x201 como o Lucas > jah tinha dito. > > Fica mais fácil de entender assim. Muito legal. :)
-- []'s Lucas -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo.
