Tabuleiros! Eles não vão nos deixar assim tão cedo. Ainda mais porque o resultado da coluna passada é o trampolim para outro resultado fascinante.

Recapitulando: em ‘Passeios em tabuleiros’ (CH 432), mostramos que, em um tabuleiro N x M, no qual um dos dois lados é par, sempre existe um ciclo hamiltoniano, isto é, um caminho fechado que pode ser executado andando uma casa de cada vez na horizontal ou vertical. Vamos chamá-los de tabuleiros pares.

E qual é o tal resultado fascinante?

Considere um tabuleiro par e pinte as casas alternadamente de preto e branco. Da coluna ‘Caminhos proibidos’ (CH 385), sabemos que, se removermos duas casas da mesma cor em um tabuleiro par, é impossível cobri-lo com peças de dominó, que são retângulos 1 x 2.

E se removermos casas de cores diferentes? Será que muda alguma coisa?

Vamos relembrar o argumento de por que é impossível cobrir o tabuleiro com peças de dominó quando retiramos duas casas da mesma cor. Antes da retirada dessas casas, o número de casas brancas e pretas é igual. Depois de retirarmos duas casas da mesma cor, haverá duas casas a mais da outra cor.

Portanto, fica impossível cobrir o tabuleiro com peças de dominó, porque cada uma delas cobre duas casas de cores diferentes. Se o tabuleiro ficou todo coberto, então, necessariamente, o número de casas brancas é igual ao número de casas pretas.

Antes de prosseguirmos, a dica de sempre: experimente com um caso simples. Por exemplo, desenhe um tabuleiro 3 x 4, pinte as casas alternadamente de preto e branco, mas, agora, remova duas casas de cores diferentes – não importa a posição delas.

Será que você consegue cobrir esse tabuleiro com peças de dominó?

Você, talvez, tenha chegado à seguinte conjectura: é sempre possível cobrir um tabuleiro par com peças de dominó, mesmo que tenhamos removido dele duas casas de cores diferentes.

Mas como provar isso? Aqui, entram nossos ciclos hamiltonianos.

Vimos, na coluna anterior, que é sempre possível traçar um ciclo hamiltoniano em um tabuleiro par. Tracemos um desses ciclos. Agora, vamos remover as casas de cores diferentes.

Primeira observação: o número total de casas continua sendo par depois da remoção. Segunda observação: o ciclo hamiltoniano ‘se quebra’ em dois trechos, como um ‘laço’ que sofreu dois cortes. Em tempo: um desses trechos pode ter ‘tamanho zero’, se removermos casas adjacentes no ciclo.

Observação final: como estamos tirando casas de cores diferentes, cada trecho do ciclo hamiltoniano tem um número par de casas. Por quê? (veja ‘Desafio’)

Juntando essas três observações, podemos chegar ao nosso resultado. Como cada trecho é um caminho e tem um número par de casas, basta parear casas consecutivas ao longo desse caminho e colocar um dominó sobre cada par, cobrindo nosso tabuleiro ‘quebrado’ (figura).