Faz um certo tempo que eu n�o vejo uma solu��o t�o brilhante como essa :- o
Em uma mensagem de 22/02/05 20:46:25 Hora padr�o leste da Am. Sul, [EMAIL PROTECTED] escreveu:
Acho que eu sei fazer o problema: ao inv�s de contar cortes, eu vou
contar pinturas do tabuleiro de preto e branco de tal forma que as
duas componentes geradas s�o conexas e t�m a mesma �rea. Como as
pinturas
OOOO XXXX
XXOO OOXX
XOOX OXXO
XXXX OOOO
s�o evidentemente induzidas pelo mesmo corte, temos que dividir o
resultado da contagem por 2 ao final.
A observa��o inicial � que se as duas componentes s�o conexas, o corte
s� pode tocar a fronteira do tabuleiro duas vezes -- uma para entrar,
outra para sair. Logo, a interse��o da componente branca com o "anel"
formado pelos 12 quadrados exteriores � conexa (e analogamente para a
parte preta):
****
*..* (anel formado pelos quadrados externos)
*..*
****
Essa interse��o pode ter quatro, cinco, seis, sete ou oito quadrados
brancos, j� que as �reas s�o iguais. Evidentemente, por causa da
dualidade das cores, o n�mero de tabuleiros com quatro quadrados
brancos e com oito quadrados brancos � o mesmo (idem para cinco e
sete).
Caso I -- 4 quadrados brancos:
==============================
Neste caso, todos os quatro quadrados centrais devem ser brancos, e
basta escolher onde come�a a "fita" de quadrados brancos no anel. Logo
temos 12 possibilidades.
Caso II -- 5 quadrados brancos:
===============================
Neste caso, tr�s quadrados centrais s�o brancos, e o formato da fita
externa pode ser de dois tipos, dependendo do ponto de come�o desta
(eu estou fixando o sentido hor�rio):
1211
1..2
2..1
1121
# Subcaso 1 -- 8 possibilidades
OOOO
X..O
X..X
XXXX
Neste caso, o �nico caso imposs�vel � o representado no diagrama:
OOOO
XOXO
XOOX
XXXX
Logo temos 8*3 = 24 possibilidades neste caso.
# Subcaso 2 -- 4 possibilidades
XOOO
X..O
X..O
XXXX
Novamente, o �nico caso imposs�vel � o representado no diagrama:
XOOO
XOXO
XOOO
XXXX
Logo temos 4*3 = 12 possibilidades neste caso.
No total, temos 24+12 = 36 possibilidades para o caso II.
Caso III -- 6 quadrados brancos:
================================
Neste caso, dois quadrados centrais s�o brancos, e o formato da fita
externa pode ser novamente de dois tipos:
1121
2..1
1..2
1211
# Subcaso 1: 8 possibilidades
OOOO
X..O
X..O
XXXX
Neste caso, as quatro pinturas centrais que n�o desconectam os
quadrados centrais s�o poss�veis, logo temos 8*4 = 32 possibilidades.
# Subcaso 2: 4 possibilidades
OOOO
O..O
X..X
XXXX
A �nica pintura que n�o desconecta quadrados que � imposs�vel � esta:
OOOO
OXXO
XOOX
XXXX
Logo temos 3*4 = 12 possibilidades.
Logo no caso III temos 32+12 = 44 possibilidades.
======================================================================
Logo, no total, temos (12+36+44+36+12)/2 = 140/2 = 70 cortes.
[]s,
--
F�bio Dias Moreira
[]s,
Rafael
"Se enxerguei mais longe foi por estar sentado aos ombros de gigantes." (Isaac Newton)
