OLIMPÍADA BRASILEIRA DE MATEMÁTICA – NÍVEIS I E II – SEMANA OLÍMPICA

Salvador, 19 a 26 de janeiro de 2001

COBERTURAS DE TABULEIROS COM “POLIMINÓS”

Onofre Campos
[email protected]

Todos nós sabemos o que é um dominó. Um tabuleiro de Xadrez, o mesmo utilizado

no jogo de Damas, também deve nos ser familiar. O que nós vamos estudar aqui são as
coberturas de tabuleiros usando dominós, considerando que um dominó é uma peça de
tamanho 1  2 e que um tabuleiro de xadrez tem dimensões 8  8 (8 linhas e 8 colunas).
Entenda que cada peça de nosso dominó cobre exatamente duas casas do tabuleiro. Dessa
forma cobrir um tabuleiro significa cobrir cada casa do tabuleiro com dominós sem que as
peças de superponham nem sobrem espaços vazios. Um problema bastante simples é o de
cobrir um tabuleiro 8  8 com peças 2  1. Para nós, é mais interessante considerar o seguinte
problema:

Problema 1 Se removermos duas casas diagonalmente opostas de um tabuleiro de Xadrez,

ainda é possível cobrir as 62 casas restantes com 31 dominós?

Solução:

As casas do tabuleiro são pintadas alternadamente de branco e preto. Como podemos

notar, um tabuleiro de Xadrez, de dimensões 8  8, possui 32 casas de cada cor e duas casas
diagonalmente opostas têm a mesma cor. Suponha que as duas casas removidas sejam ambas
brancas. Então, o novo tabuleiro ficará com 32 casas pretas e 30 brancas (Fig. 01). Mas como
cada dominó cobre uma casa de cada cor, é impossível preenchermos o tabuleiro com
dominós, uma vez que seria necessário o mesmo número de casas de cada cor.

Fig. 01

Neste problema, tivemos que analisar a coloração do tabuleiro. Em alguns problemas,

entretanto, esta coloração das casas (alternadamente de branco e preto) não será suficiente, e
teremos que arranjar outra coloração para o tabuleiro. Antes disso, vamos analisar o seguinte
problema:
 Semana Olímpica – Níveis I e II – Prof.: Onofre Campos

Problema 2 É possível cobrirmos um tabuleiro de Xadrez com dominós se removermos uma

casa de cada cor, não importando quais as casas?

Solução:

Agora faz sentido pensarmos em uma possível cobertura, visto que agora temos o
mesmo número de casas brancas e pretas. De fato, é possível, bastando considerarmos o
seguinte tabuleiro:

Fig. 02

Observe que dividindo o tabuleiro dessa forma obtemos um ciclo que contém todas as
casas do tabuleiro. Além disso, como as casas estão pintadas alternadamente de branco e
preto, se retirarmos uma casa de cada cor, o número de quadrados ao longo do ciclo entre as
duas casas removidas é par (em qualquer um dos dois sentidos que percorrermos o ciclo). Isso
completa a demonstração, visto que cada dominó cobre duas casas.

Suponha, agora, que ao invés de dominós tenhamos poliminós, que são peças obtidas
unindo-se quadrados 1  1 lado a lado. Por exemplo, podemos formar triminós (Fig. 03)

Fig. 03

Ou ainda, tetraminós como na figura a seguir:

Fig. 04

Os pentaminós são, em número, 12 e os hexaminós 35. Em geral, se n  7, o número

de n-minós aumenta muito, embora não se conheça uma fórmula para calculá-los.

Veja que para cobrirmos um tabuleiro com triminós, é necessário que o número de
casas do tabuleiro seja um múltiplo de 3; com tetraminós, o número de casas deve ser
múltiplo de 4, e assim por diante, embora essas condições não sejam suficientes.

Problema 3 É possível cobrirmos um tabuleiro 8  8 com 21 L-triminós se removermos do

tabuleiro uma casa qualquer?

2
 Semana Olímpica – Níveis I e II – Prof.: Onofre Campos

Solução:

Sim, é possível, como descrevemos a seguir. Retiremos uma casa do tabuleiro. Então,
dividindo o novo tabuleiro em quatro subtabuleiros menores 4  4, a casa removida deve estar
em um destes subtabuleiros. Em seguida, dividimos o subtabuleiro do qual retiramos a casa
em quatro outros subtabuleiros menores 2  2. Novamente, a casa retirada pertence a um dos
quatro quadradinhos 2  2 obtidos. (Fig. 05). Com um L-triminó, completamos o quadradinho
2  2 que continha a casa retirada. Agora, no subtabuleiro 4  4 colocamos 3 L-triminós, um
em cada canto e outro L-triminó completando o tabuleiro 4  4. Resta-nos agora, cobrir as
outras três partes do tabuleiro, que são quadrados 4  4. Isto pode ser feito de modo análogo,
como mostra a Fig. 06.

Fig. 05 Fig. 06

Como afirmamos antes, uma condição necessária para que haja uma cobertura de um
tabuleiro com n-minós é que o número de casas do tabuleiro seja múltiplo de n. No entanto,
esta condição não é suficiente, como mostra o próximo teorema .

Um L-tetradominó é uma peça do formato a seguir, onde cada quadradinho tem lado 1.

Teorema Sejam m e n inteiros maiores que 1. Se um tabuleiro de dimensões m  n pode ser

coberto com L-tetradominó então mn é múltiplo de 8.

Demonstração:

Suponha que o tabuleiro possua m linhas e n colunas e que haja uma cobertura com L-
tetradominós. Como cada L-tetradominó possui 4 casas, então o número de casas do tabuleiro
deve ser múltiplo de 4. Logo, m e n não podem ser ambos ímpares. Suponha que n seja par.
Então o tabuleiro possui um número par de colunas. Vamos pintar as colunas alternadamente
de branco e preto (Fig. 07). O interessante desta idéia é que independente de como as peças
são colocadas, cada peça cobre exatamente 3 casas de uma cor e uma casa da outra. Sejam b e
p, respectivamente, as quantidades de peças que cobrem exatamente 3 casas brancas e 3 casas
pretas. Como o número de casas brancas é igual ao número de casas pretas (porque há tantas
colunas brancas quanto pretas), o número de casas brancas é igual a 3b + p e o número de
casas pretas e igual a 3p + b, devemos ter 3b + p = 3p + b, de onde concluímos que b = p. Isso
significa dizer que temos um número par de L-tetradominós, cada um dos quais com 4 casas.
Logo o tabuleiro deve ter um número de casas múltiplo de 8.

3
 Semana Olímpica – Níveis I e II – Prof.: Onofre Campos

...
...
...
...
...
...
...
Fig. 07

PROBLEMAS PROPOSTOS

1. Mostre como cobrir um tabuleiro 8  3 usando L-tetradominós.

2. Demonstre a recíproca do teorema mostrado acima.

3. É possível cobrirmos um tabuleiro 8  8 usando 21 triminós “retos” se retirarmos uma casa

qualquer do tabuleiro?

4. Mostre que é impossível cobrir um tabuleiro 10  10 usando L-tetradominós. Mostre o

mesmo para tetraminós “retos”.

5. Uma sala de forma retangular está sendo ladrilhada com cerâmicas em forma de retângulos
2  2 e 1  4. Um das cerâmicas quebrou , de modo que só é possível substituí-la por uma do
outro tipo. Mostre que é impossível ladrilhar novamente a sala rearranjando as cerâmicas.

6. É possível empacotar 250 tijolos de dimensões 1  1  4 em uma caixa de dimensões

10  10  10?

7. Um quadrado 7  7 é cortado em figuras de três tipos:

(1) (2) (3)

Prove que dentre essas figuras há exatamente uma consistindo de quatro quadradinhos.