Re: [obm-l] Dominos e Fibonacci (e sapinhos na escada!)

[Johann Peter Gustav Lejeune Dirichlet <peterdirichlet2002@xxxxxxxxxxxx>]

Numero de Fibonacci.

Este problema foi discutido na Lista ha algum tempo, e o Shine falou que obteve uma contagem dupla bem interessante...

Seja f(n) o numero de modos pedido no enunciado.

Pegue um tabuleiro 2x(n+2).Imagine-o copmo normalmente voce imaginaria:

|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|

|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|

 

(eu nao presto pra artista ASCII)

 

Vamos provar que f(n+2)=f(n+1)+f(n).

Olhando as duas ultimas colunas, temos os casos a seguir

1)Dois dominos deitados.

Ai o restante e coberto de f(n) modos.

2)Um domino de pe

Ai o resto e coberto de f(n+1) modos.

 

Como estes casos sao todos os que se pode testar, f(n+2)=f(n+1)+f(n). E acabou!

 

Um problema correlato:

"Um sapo está na base de uma escada.Suas pernas permitem que ele pule somente 1 ou 2 andares (imagina so o tamanho do degrau...). Sabendo que ele nao desce nunca a escada, de quantos modos ele chega ate o enesimo degrau?"

Se quiser tente ver uma bijeçao entre esses dois problemas!

 

Te mais!

Ass.:Johann
Claudio Buffara <claudio.buffara@terra.com.br> wrote:

> De quantas maneiras podemos cobrir um tabuleiro 2xn com dominos?
> Suponha que os dominos sao simetricos (ou seja, ambos os quadrados tem o
> mesmo numero de bolinhas).
>
> =========================================================================
> 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
> =========================================================================

TRANSIRE SVVM PECTVS MVNDOQVE POTIRI

CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBVERE

Fields Medal(John Charles Fields)

 

N.F.C. (Ne Fronti Crede)

---

Yahoo! Messenger - Fale com seus amigos online. Instale agora!