Re: Domino

["Ralph Teixeira" <ralph@xxxxxx>]

    Mas ajudou sim, David! Com os casos que voce citou em maos, podemos
atacar agora o caso m x n com m e n impares, m divisivel por 3.

    Se m=3 entao pode-se mostrar que eh impossivel preencher o tabuleiro;
voce pode fazer por inducao, analisando as 3 possibilidades de cobrir um dos
cantos, observando como cobrir o canto "proximo adjacente" e reduzir 3 x n
para 3 x (n-2); note que 3 x 1 certamente nao dah. Analogamente, se n=3
tambem nao dah para cobrir o tabuleiro.

    Assim, suponha m,n>=5, impares, e m divisivel por 3, isto eh, m=6a+9 e
n=2b+5 com a,b>=0. Entao:

    i) O retangulo 6a x n voce jah mostrou como fazer, certo?
    ii) O outro pedaco eh 9 x 2b+5. O pedaco 9 x 2b voce tambem jah mostrou
como fazer, neh?
    iii) Entao soh falta cobrir o pedaco 9 x 5, o que pode ser feito por
tentativa e erro com 15 triminos... Tente voce mesmo, eh rapido achar uma
configuracao que presta. Aqui estah uma achada rapidinho:


1 1 2 2 3 3 4 5 5
1 6 6 2 7 3 4 4 5
8 8 6 7 7 9 9 a a
8 b c d d 9 e a f
b b c c d e e f f

    (esse pedaco aqui em cima soh fica diretinho se voce estiver usando uma
fonte de largura fixa, mas acho que deu para entender, neh?)

    Pronto, feito! Qualquer tabuleiro pode ser coberto, desde que um dos
lados seja divisivel por 3, mas nenhum deles seja 3.
    Abraco,
        Ralph

----- Original Message -----
From: "David Daniel Turchick" <dturchic@colband.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Thursday, December 27, 2001 1:09 PM
Subject: Re: Domino


Ops! Você pediu justamente m e n ímpares! Às vezes é bom ler o enunciado
direito antes de tentar resolver...
Obrigado, Bruno, por me avisar da minha besteira, e desculpa aí ao pessoal
da lista!

-----Mensagem original-----
De: David Daniel Turchick <dturchic@colband.com.br>
Para: obm-l@mat.puc-rio.br <obm-l@mat.puc-rio.br>
Data: Quinta-feira, 27 de Dezembro de 2001 12:10
Assunto: Re: Domino


Olha, tentar, eu tentei, mas aposto que onde eu cheguei vários chegaram...
Mostrei que é necessário que m ou n sejam múltiplos de 3: a área do
tabuleiro deve ser múltipla da área do triminó, e 3 é primo), e para fixar
as idéias, impus que fosse o m=3a.
É suficiente que n seja par: se n=2b, divida o tabuleiro em b faixas mX2 e
preencha cada faixa com a retângulos 3X2, que podem claramente ser
"triminomizados".
É suficiente n ímpar >1 e m par: seja a=2c, então m=6c, e seja n=2b+1, então
dividimos o tabuleiro em b-1 faixas mX2 (com as quais você já sabe o que
fazer) e 1 faixa mX3, a qual você preenche com 3c retângulos 2X3.
Então o que falta é o caso m e n ímpares.

Espero ter ajudado (mas aposto que não ajudei!).
David

-----Mensagem original-----
De: Carlos Stein Naves de Brito <carlosstein@uol.com.br>
Para: obm-l@mat.puc-rio.br <obm-l@mat.puc-rio.br>
Data: Quinta-feira, 27 de Dezembro de 2001 00:54
Assunto: Domino



Please, alguem tenta pra mim... Obrigado!
Em que casos um tabuleiro mxn(m,n impares) pode ser coberto por triminos que
sao tres quadradinhos que formam um bumerangue.