Re: [obm-l] Dominos e Fibonacci

["Rafael" <cyberhelp@xxxxxxxxxx>]

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" <claudio.buffara@terra.com.br>
To: "Lista OBM" <obm-l@mat.puc-rio.br>
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
=========================================================================