Re: [obm-l] Combinatoria - Sequencias Cheias

[kleinad@xxxxxxxxxx]

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
=========================================================================