Re: [obm-l] Combinatoria - Sequencias Cheias

[kleinad@xxxxxxxxxx]

Realmente, eu a princípio achava que ter usado o DEPOIS em lugar do ANTES
não faria grande diferença, mas de fato faz... Então eu mudei bastante o seu
enunciado, que é mais difícil que o meu.

Johann Peter Gustav Lejeune Dirichlet (peterdirichlet2003@yahoo.com.br)
escreveu:
>
>Mesmo assim tem um erro no seu raciocinio. 2212 e cheia.
>
>kleinad@webcpd.com wrote:Ops, eu "mudei" um pouquinho o problema... A
segunda condição do enunciado
>diz que "a primeira aparição de k-1 ocorre ANTES da última aparição de k",
>mas eu considerei que ela ocorre DEPOIS. Bem, isso não muda o grosso do
>raciocínio nem muito menos altera o resultado... Foi mal pelo deslize!
>
>[]s,
>Daniel
>
>kleinad@webcpd.com escreveu:
>>
>>>Seja n um natural dado.
>>>
>>>Dizemos que uma sequencia de n naturais (nao necessariamente distintos) e
>>>CHEIA se ela satisfaz essas propriedades:
>>>
>>>para cada k>1, se k aparece entao k-1 tambem aparece;
>>>a primeira apariçao de k-1 ocorre antes da ultima apariçao de k, para k>1.
>>>
>>>Calcule quantas cheias existem, em funçao de n.
>>
>>São 2^(n-1) cheias.
>>
>>De fato, repare que o 1 deverá ser o último elemento de toda seqüência.
>>Ainda, números seguidos na seqüência ou são iguais ou então o primeiro é
>>sucessor do segundo, logo o maior número em cada seqüência só poderá ser
>>mesmo o n. Ilustro o caso n=4:
>>
>>1, 1, 1, 1
>>2, 1, 1, 1
>>2, 2, 1, 1
>>2, 2, 2, 1
>>3, 2, 1, 1
>>3, 2, 2, 1
>>3, 3, 2, 1
>>4, 3, 2, 1
>>
>>São 2^3 cheias, e vale a afirmação. Suponha que valha para n = x --> S_x =
>2^
>>(x-1). Repare que quando n = x+1, as cheias podem ser construídas a partir
>>das cheias anteriores colocando-se à sua frente, como termo inicial, um
>>termo igual ou sucessor do antigo termo. Quero dizer: se 1,1 é uma
seqüência
>>de n=2, então 1, 1, 1 e 2, 1, 1 serão seqüências quando n = 3. Repare que
>>este método esgotará todas as seqüências possíveis sem repetições, e, para
>>cada uma das seqüências de n = x, produziremos duas seqüências em n = x +
1,
>>logo se S_x = 2^(x-1) então S_(x+1) = 2*S_x = 2^x, e acabamos.
>>
>>[]s,
>>Daniel
>>
>
>=========================================================================
>Instruções para entrar na lista, sair da lista e usar a lista em
>http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>=========================================================================
>
>
>
>---------------------------------
>Yahoo! Acesso Grátis - navegue de graça com conexão de qualidade!

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================