---------- Forwarded message ----------
From: Ralph Teixeira <ra...@mat.uff.br>
Date: 2013/6/13
Subject: Re: [obm-l] questão bacana(quase me tira o sono)
To: obm-l@mat.puc-rio.br
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.
Abraco,
Ralph
2013/6/11 marcone augusto araújo borges <marconeborge...@hotmail.com>
> São dados uma balança de 2 pratos e os pesos 2^0,2^1,2^2,...2^100 gramas
> os pesos são colocados um a um de modo que o prato esquerdo nunca seja
> mais pesado que o prato direito.De quantos modos isso pode ser feito
>
> não consegui e agradeço a quem ajudar
>
> --
> 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.
