Eu resolvi um pouco diferente. Quantos quadrados 1x1 podemos formar? (n+1 escolhe 2)
Quantos quadrados 2x2 podemos formar? (n escolhe 2) ... Então temos Somatorio de i = 2 até n + 1 de (i escolhe 2) = 2^(n+1) Errei em algum canto? On Wed, Jul 9, 2008 at 6:51 PM, Felipe Diniz <[EMAIL PROTECTED]> wrote: > Para uma escada de tamanho n, seja F(n) o numero de quadrados > temos que > F(n)=quadrados que nao englobem a primeira coluna + quadrados que englobem a > primeira coluna. > quadrados que nao englobem a primeira coluna = F(n-1) > > para n par: > quadrados que englobem a primeira coluna: > 1 + 2 + 3 + 4+... + k+k+ (k-1)+(k-2)+...+1 = 2(1+2+3..+k) = k(k+1), onde k > eh o maior inteiro tal que 2k+1<=n, como n e' par n=2m > 2k+1<=2m => k<= m+1/2, logo k = m= n/2 > para n impar: > quadrados que englobem a primeira coluna: > 1 + 2 + 3 + 4+... + k (k-1)+(k-2)+...+1 = 2(1+2+3..+k-1)+k = k^2, onde k eh > o menor inteiro tal que 2k+1>n, como n e' impar n=2m+1 > 2k+1>2m+1 => k> m, logo k = m+1= (n+1)/2 > > Assim F(n)= Somatorio de k=2 ate n de A(k) + F(1) > onde A(n)= n/2 ( n/2 + 1) se n e` par, e [(n+1)/2]^2 se n e` impar. > Assim: > F(2n) = n(n+1)+somatorio de k=1 ate n-1 A(2k)+A(2k+1) + F(1) = 1 + n(n+1)+ > somatorio de k=1 ate n-1 de 2k^2 + 3k+1 = > 1+ n(n+1)+ n-1 + 3(n-1)n/2 + 2 (n-1)n(2n-1)/6 > > F(2n+1)= somatorio de k=1 ate n A(2k)+A(2k+1) + F(1) = 1 + Somatorio de > k=1 ate n de 2k^2 + 3k+1 = > 1 + n + 3n(n+1)/2 + 2n(n+1)(2n+1)/6 > > fiz meio rapido espero estar certo... > > > Felipe Diniz > > On Wed, Jul 9, 2008 at 12:05 PM, Rodrigo Renji <[EMAIL PROTECTED]> > wrote: >> >> Na seguinte figura (link no photobucket) >> >> >> http://s317.photobucket.com/albums/mm387/matcult/?action=view¤t=quadrados2.jpg >> >> >> Queremos saber o número máximo de quadrados de qualquer tamanho >> formados pelos quadrados unitários, numa escada com n degrais >> >> ========================================================================= >> Instruções para entrar na lista, sair da lista e usar a lista em >> http://www.mat.puc-rio.br/~obmlistas/obm-l.html >> ========================================================================= > > -- Wanderley Guimarães ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================
