Re: [obm-l] Combinatoria - Sequencias Cheias

[kleinad@xxxxxxxxxx]

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