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
=========================================================================
