[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
