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 <[EMAIL PROTECTED]> wrote:
Claudio Buffara <[EMAIL PROTECTED]> 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)
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!
