Durante a semana, fiquei pensando sobre esse problema e alguns outros, cheguei a algumas conclusões sobre as quais escrevo agora.
Suponhamos um tabuleiro 2x1: _ |_| |_| Há uma única possibilidade de disposição do dominó (suposto simétrico). Agora, um tabuleiro 2x2: _ _ |_|_| |_|_| Temos duas possibilidades: dois dominós na horizontal ou dois dominós na vertical. Seja um tabuleiro 2x3: _ _ _ |_|_|_| |_|_|_| Temos três possibilidades: três dominós na vertical, dois à esquerda na horizontal e um na vertical, dois à direita na horizontal e um na vertical. Para um tabuleiro 2x4: _ _ _ _ |_|_|_|_| |_|_|_|_| Há cinco possibilidades: quatro dominós na vertical, dois à esquerda na horizontal e dois na vertical, dois à direita na horizontal e dois na vertical, dois dominós na horizontal no centro e um dominó na vertical em cada extremo, quatro dominós na horizontal. Curiosamente: 2x1 ---> 1 possibilidade ---> F(2) = 1 2x2 ---> 2 possibilidades ---> F(3) = 2 2x3 ---> 3 possibilidades ---> F(4) = 3 2x4 ---> 5 possibilidades ---> F(5) = 5 .... 2xn ---> F(n+1) possibilidades, em que F(n) é o enésimo número de Fibonacci. Quanto ao problema que eu havia proposto ("probabilidade e quadradinhos"), os tabuleiros são quadrados. Seja um tabuleiro 2x2: _ _ |_|_| |_|_| Temos duas possibilidades na horizontal e outras duas na vertical, i.e., 2*2 = 4 possibilidades. Vamos ao 3x3: _ _ _ |_|_|_| |_|_|_| |_|_|_| Temos 2*3 possibilidades na horizontal (duas possibilidades para cada coluna). Na vertical, por simetria, temos outras 2*3 possibilidades, o que nos dá 2*2*3 = 12 possibilidades. Se tivéssemos um tabuleiro 4x4: _ _ _ _ |_|_|_|_| |_|_|_|_| |_|_|_|_| |_|_|_|_| Teríamos 3*4 possibilidades na horizontal e, por simetria, 3*4 possibilidades na vertical: 2*3*4 = 24 possibilidades. Analogamente, um tabuleiro nxn teria n(n-1) possibilidades na horizontal (para cada coluna, n-1 possibilidades) e, por simetria novamente, n(n-1) na vertical, o que nos traz o resultado que o Cláudio utilizou: 2n(n-1). Na lista também foi proposto um problema sobre "sapos na escada" pelo Anderson (também conhecido por Dirichlet --- agora com a identidade secreta revelada). Reformulando o problema, em vez de uma escada, imaginemos tocas: x |_|_|_|_|_|_|_|_|_|_|_|.... O objetivo do sapo é, sem retroceder, partir de x e chegar novamente ao chão. Supondo que haja apenas duas tocas, teremos: - Do chão, o sapo salta e cai na 1a. toca, salta e cai na 2a., salta e vai para o chão; - Do chão, o sapo salta e cai na 1a. toca, salta e vai para o chão; - Do chão, o sapo salta e cai na 2a. toca, salta e vai para o chão. Para duas tocas, temos 3 possibilidades. E se fossem três tocas? - Do chão, o sapo salta e cai na 1a. toca, salta e cai na 2a., salta e cai na 3a., salta e vai para o chão; - Do chão, o sapo salta e cai na 1a. toca, salta e cai na 2a., salta e vai para o chão; - Do chão, o sapo salta e cai na 1a. toca, salta e cai na 3a., salta e vai para o chão; - Do chão, o sapo salta e cai na 2a. toca, salta e cai na 3a., salta e vai para o chão; - Do chão, o sapo salta e cai na 2a. toca, salta e vai para o chão. Para três tocas, temos 5 possibilidades. Mas... e se fossem quatro tocas? Em vez de enumerarmos as possibilidades, observemos que o sapo, no máximo, dará 5 saltos. Se encontrarmos/contarmos todas as partições de 5 em 1 e 2, partições estas em que a ordem é importante, teremos: 5 = 1 + 1 + 1 + 1 + 1 = = 2 + 1 + 1 + 1 = = 1 + 2 + 1 + 1 = = 1 + 1 + 2 + 1 = = 1 + 1 + 1 + 2 = = 2 + 2 + 1 = = 2 + 1 + 2 = = 1 + 2 + 2 Conseguimos oito partições, o que significa que o sapo terá oito possibilidades quando houver quatro tocas. Curiosamente de novo: 1 toca ---> 2 possibilidades ---> F(3) 2 tocas ---> 3 possibilidades ---> F(4) 3 tocas ---> 5 possibilidades ---> F(5) 4 tocas ---> 8 possibilidades ---> F(6), em que F(n) é o enésimo número de Fibonacci. Assim, quando houver n tocas (ou n degraus, no problema original), o sapo terá F(n+2) maneiras de chegar ao chão (ou ao topo da escada). Abraços, Rafael de A. Sampaio ----- Original Message ----- From: "Claudio Buffara" <[EMAIL PROTECTED]> To: "Lista OBM" <[EMAIL PROTECTED]> Sent: Sunday, May 09, 2004 7:49 PM Subject: [obm-l] Dominos e Fibonacci 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 =========================================================================