RE: [obm-l] Re: N/A

[João Gilberto Ponciano Pereira <jopereira@xxxxxxxxxxxxx>]

Pessoal

Sem querer ser chato, mas cheguei ao resultado de 55. O processo é um pouco
"feio", mas chega lá.

"De quantas maneiras podemos formar uma sequencia de oito bits(0 ou 1) de
forma que nunca  apareça nesta sequencia zeros adjacentes"

Seja A(n) o número de combinações dentro das regras que terminam com o bit
1, e B(n) os que terminem com o bit 0.

É fácil ver que:
1) A(n+1) = A(n) + B(n)
2) B(n+1) = A(n)

Logo:
A(n+1) + B(n+1) = 2*A(n) + B(n)
e substituindo, temos:
A(n+2) = 2*A(n) + A(n-1)

Sabendo que:
 A(1) = 1 ==> (1)
 A(2) = 2 ==> (01, 11)
 A(3) = 3 ==> (011, 101, 111) obs: "001" não vale!
podemos seguir com a recorrência até A(9) = A(8) + B(8) = 55

Um abraço!
JG

-----Original Message-----
From: Augusto Cesar de Oliveira Morgado [mailto:morgado@centroin.com.br]
Sent: Monday, November 03, 2003 9:29 PM
To: obm-l@mat.puc-rio.br
Subject: Re: [obm-l] Re: N/A


Recebi a mensagem que enviei com um rosto amarelo com cara de idiota
sorrindo 
no lugar em que digitei o numero 8. Desculpas a todos.
Morgado


--
CIP WebMAIL - Nova Geração - v. 2.1
CentroIn Internet Provider        http://www.centroin.com.br
Tel: (21) 2542-4849, (21) 2295-3331      Fax: (21) 2295-2978
Empresa 100% Brasileira - Desde 1992


---------- Original Message -----------
From: "Augusto Cesar de Oliveira Morgado" <morgado@centroin.com.br>
To: obm-l@mat.puc-rio.br
Sent: Mon, 3 Nov 2003 20:59:29 -0200
Subject: [obm-l] Re: N/A

> Seja f(n) a resposta para uma sequencia de n bits. Ou a seq. começa 
> em 1 ou começa em 01. Logo, f(n)=f(n-1)+f(n-2). Como f(1) = 2 e f(2) 
> = 3, f(3) = 2+3=5, f(4) = 5+3 = 8, f(5) = 8+5 = 13, f(6)=13=8 = 21,
>  f(7) = 21+13 = 44 e f(8) = 44+21 = 65.
> 
> --
> CIP WebMAIL - Nova Geração - v. 2.1
> CentroIn Internet Provider        http://www.centroin.com.br
> Tel: (21) 2542-4849, (21) 2295-3331      Fax: (21) 2295-2978
> Empresa 100% Brasileira - Desde 1992
> 
> ---------- Original Message -----------
> From: "Daniel Faria" <faria_mat@hotmail.com>
> To: obm-l@mat.puc-rio.br
> Sent: Mon, 03 Nov 2003 19:16:55 -0200
> Subject: N/A
> 
> > Ainda nao consegui finalizar este exercício:
> > 
> > De quantas maneiras podemos formar uma sequencia de oito bits(0 ou 1)
> >  de forma que nunca  apareça nesta sequencia zeros adjacentes ( _ _ 
> > 0 0 _ _ _ _ ).
> > 
> > Obrigado.
> > 
> > _________________________________________________________________
> > MSN Hotmail, o maior webmail do Brasil.  http://www.hotmail.com
> > 
> >
=========================================================================
> > 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
> >
=========================================================================
> ------- End of Original Message -------
> 
> =========================================================================
> 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
> =========================================================================
------- End of Original Message -------

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