Re: [obm-l] 3 problemas em aberto

[Fábio Dias Moreira <fabio@xxxxxxxxxxxxxxxxxxx>]

[22/2/2005, claudio.buffara@terra.com.br]:
> on 22.02.05 13:31, Fábio Dias Moreira at fabio@dias.moreira.nom.br wrote:
>> [22/2/2005, claudio.buffara@terra.com.br]:
>>> [...] O terceiro dah pra fazer no
>>> braco, mas obviamente o legal eh achar uma forma esperta de enumerar os
>>> cortes. Eu pensei no numero de solucoes de x+y+z+w=8 com algumas restricoes
>>> mas me enrolei.
>> 
>> Se a sua idéia é a que eu estou pensando, o seguinte corte não parece
>> ser representado por nenhuma solução:
>> 
>> OOOO
>> XXOO
>> XOOX
>> XXXX
>> 
>> []s,
>
> Precisamente onde eu empaquei. O problema eh aquele X na posicao (2,2) e nao
> adianta girar o quadrado...
> [...]

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

PGP signature