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