[22/2/2005, [EMAIL PROTECTED]: > on 22.02.05 13:31, Fábio Dias Moreira at [EMAIL PROTECTED] wrote: >> [22/2/2005, [EMAIL PROTECTED]: >>> [...] 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
pgpAevOg4IV1l.pgp
Description: PGP signature