Re: [obm-l] 3 problemas em aberto

[Faelccmm@xxxxxxx]

Valeu, Fábio ! 

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, fabio@dias.moreira.nom.br 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)