Escrito por Samuel Prieto
Colorações para resolver problemas de tabuleiro.
Muitas vezes econtramos problemas em que precisamos determinar se um tabuleiro pode ou não ser coberto de uma determinada maneira, separar suas casas em categorias pode ajudar. Essa técnica é apelidada coloração. A mais comum (e que usaremos no exemplo) é a coloração de um tabuleiro de xadrez. Uma das vantagens dessa é que um dominó sempre combre um casa branca e uma casa preta no tabuleiro.
Exemplo 1: É possível cobrir completamente o tabuleiro abaixo apenas com dominós 2x1 sem sobreposição?
Já tentou sozinho resolver? então vamos lá:
Solução: Vamos colorir o tabuleiro como se fosse um tabuleiro de xadrez:
Sabemos que cada peça de dominó cobre exatamente uma casa branca e uma casa preta. Mais espeficicamente, ela cobre a mesma quantidade de cada tipo de casa. Logo seja D o número de dominós usados em uma possível cobertura, devemos ter D casas brancas e D casas pretas. Porém voltando a figura, perecem haver mais casar pretas que bracas, e motivados por isso à contar, descobrimos que há de fato 16 casas pretas e 12 casas brancas, então não pode ser possível cobrir completamente o tabuleiro, e terminamos.
Exemplo 2:Determine quais dos seguintes tabuleiros podem ser cobertos com peças do tamanho apresentado, que podem ser rotacionadas, sem sobreposição:
a) Tabuleiro 6x6 com peças 4x1
b) Tabuleiro 8x8 com L-Quadriminós (Peça que semelhante ao movimento do cavalo no xadrez, tem 4 peças e forma uma letra L)
C) Tabuleiro 9x9 com L-Quadriminós
d) Tabuleiro 8x9 só com Pecas 4x1, depois só com L-Quadriminós
Solução:
a) adotamos uma estratégia similar a coloração xadres, mas quando precisamos de mais grupo, chamada coloração de diagonais. Tentamos seprar o tabuleiro em 4 grupos (cores), tal que qualquer peça colocad tenha uma peça de cada grupo. Observer então a seguinte coloração:
(sim, eu sei, sou um artista). Observe que qualquer peça 4x1 colocada no tabuleiro irá cobrir uma casa de cada cor, logo se fosse poddível cobrir o tabuleiro, deveriamos ter a mesma quantidade de cores de cada peça, mas um contagem revela que há 8 casas azuis e 10 casas vermelhas, logo é impossível cobrir o tabuleiro da maneira descrita.
b) Se primeiro tentarmos demonstrar que é impossível realizar tal cobertura, não encontramos nenhuma cobertura que ajude. Isso é um sinal que talvez seja possível cobri o tabuleiro, entçao dedique algum tempo a tentar faze-lo (uma ótima dica é não tentar colorir o tabuleiro por inteiro, mas dividi-lo em partes menores). Apresentamos a cobertura que funciona:
Percebemos inicialmente que ao unir dois L-Quadriminós sa seguinte maneira, obtemos uma cobertura para um tabuleiro 2x4:
Tentamos então separar o tabuleiro 8x8 em mini tabuleiros 2x4, o que é facil:
Logo já sabemos como cobrir cada uma dessas pequenas partes e o problema está completo.
c) A resposta é não e o motivo nem se quer involve tabuleiros ou colorações, mas apenas divisão com resto... (isso foi a dica, fica como exercício)
Exercícios:
1. Resolva as letra (c) e (d) do exemplo anterior
2. (Seletiva Fortaleza – Rioplatense/2012 – Nível A) Benjamim tem 25 peças A e 25 peças B, cujos formatos estão mostrados abaixo :
Com as 50 peças, Benjamim pretende cobrir um tabuleiro completamente, sem deixar buracos e nem fazer sobreposições. Ele sabe que cada quadradinho da peça A e que cada quadradinho da peça B tem 1cm² de área. Sabendo que ele pode girar as peças do jeito que ele quiser, podendo inclusive “inverter” qualquer peça, pergunta-se: a) Se o tabuleiro for 8x8(ou seja, ele tiver 8 cm de comprimento por 8 cm de largura), é possível que ele consiga cobrir todo o tabuleiro?
b) Se o tabuleiro for 8x9, é possível que ele consiga cobrir todo o tabuleiro?
c) Se o tabuleiro for 9x9, é possível que ele consiga cobrir todo o tabuleiro?
d) Se todas as casas acima de uma diagonal do tabuleiro forem retiradas (veja figura abaixo), é possível que ele consiga cobrir todo o tabuleiro?
Observação: Note que as duas peças abaixo são as mesmas, pois uma foi invertida para obter a outra.
3. Suponhamos que no item d da questão anterior, Benjamim tivesse exatamente duas peças do tipo C (figura abaixo) para ajudar a cobrir o tabuleiro. Nesse caso, mostre uma forma de ele cobrir totalmente o tabuleiro. (Dica: Note que, pelo resultado da coloração xadrez do item anterior, podemos ter uma boa ideia de possíveis locais onde devemos colocar as duas peças do tipo C.)
4. Usando apenas L-tetraminós, é possível cobrir totalmente um tabuleiro 6 x 6, sem deixar buracos, nem fazer sobreposições?
5. (OBM/2012 – N2 – 2ª fase – Q1) João gosta de verificar propriedades do jogo de xadrez em um tabuleiro 5 × 5. Num de seus experimentos, João coloca um cavalo na casa inferior esquerda do tabuleiro 5 × 5. Qual o número mínimo de movimentos do cavalo para que ele possa chegar a qualquer casa do tabuleiro 5 × 5?