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