Cortando um quadrado sem machucar os dominós
22 de Janeiro de 2015
Problema 1. Imagine um quadrado de cartolina 6 × 6, composto por quadradinhos menores de lado 1. O quadrado grande é totalmente coberto por
domiós 1 × 2, cada um cobrindo dois quadradinhos que têm uma aresta em
comum, sem que haja superposição dos dominós. Prove que, para qualquer
cobertura deste tipo, sempre podemos encontrar uma linha paralela a um dos
lados que separa o quadrado em dois retângulos feitos de quadradinhos sem
cortar qualquer peça de dominó ao meio.
1
Explorando o problema
Este é um problema bastante difı́cil. Vamos começar lembrando rapidamente
de alguns conselhos passados.
Considere casos mais simples!
Neste caso, podemos considerar um quadrado 2 × 2 e ver que o resultado
vale. Para 3 × 3 fica claro que não dá, porque 32 = 9 é ı́mpar (mais sobre
sito a seguir).
Faça um desenho e veja se o enunciado quebra!
Isto é, faça um desenho tentando fazer com que qualquer linha vertical
ou horizontal cruze ao menos um dominó. Você vai ver que isto é muito
difı́cil.
Para casos especı́ficos, é fácil ver que o enunciado não quebra, isto é, que
tentar bloquear todas as linhas sempre gera buracos “impreenchı́veis”. No
entanto, provar que semmpre há um buraco deste tipo é muito difı́cil: ao
menos em princı́pio, há uma quantidade imensa de casos a considerar e não
há tempo de encontrá-los todos. O que isto sugere é que devemos evitar
estudar as especificidades de todas as coberturas válidas. Ao invés disto,
devemos buscar o que é comum a todas elas.
1
Procure invariantes!
Vamos observar algumas coisas que não variam. Primeiro é importante
observar que, numa cobertura válida cada dominó cobre duas unidades de
área do quadrado grande 6 × 6, logo o número total de dominós é 36/2 = 18.
Que outros invariantes podemos achar? Eis mais uma dica.
Para encontrar invariantes, busque relações entre os
números relevantes no problema.
Encontrar os tais números relevantes é o desafio, então vamos parar e
pensar. O nosso objetivo é mostrar que há uma linha paralela aos lados
do quadrado (que vamos supôr alinhados com os eixos coordenados, para
facilitar) que não corta qualquer dominó. Há 10 linhas deste tipo e parece
importante considerar, para cada linha 1 ≤ i ≤ 10, o número ni de dominós
cortados: afinal, nosso objetivo é precisamente provar que algum ni vale 0.
Evidentemente, cada ni depende da configuração em questão. O que
pode haver de invariante neles? Depois de alguma observação, um primeiro
dado salta aos olhos.
Para qualquer configuração,
10
X
ni = 18 = número de dominós.
i=1
Isto é verdade porque, em quaquer configuração, cada dominó é cortado
por exatamente uma das dez linhas. Logo, somando os números de cortes
para as linhas, obtemos o número total de dominós.
Que outros invariantes podemos encontrar? Já vimos em outros problemas que:
Paridades podem resultar em ótimos invariantes
invariantes!
O que há de paridade nas coberturas válidas? Observe cada ni (já decidimos que eles são as quantidades relevantes). Você certamente se convencerá
de algo que por enquanto é apenas uma conjectura.
Conjectura: os ni ’s são sempre pares!
Não é difı́cil ver que isto é verdade, mas provar é mais complicado.Pelo
princı́pio do wishful thinking, ou “pensar com a esperança de que tudo seja
2
simples”, nos daremos ao direito de acreditar provisoriamente na conjectura.
O ponto é que ela (associada a todo o resto que já vimos) basta para terminar
a demonstração! De fato, suponha (para chegar a uma contradição que cada
ni 6= 0). Como os ni ’s são pares, resulta que cada um deles vale ao
P menos 2;
mas então a soma dos 10 ni ’s é pelo menos vinte, o que contradiz i ni = 18.
A contradição implica que algum ni vale 0, CQD.
Para terminar, vamos apresentar uma prova da conjectura (as outras
afirmações acima são diretas e nos escusaremos de prová-las formalmente).
2
Prova da conjectura
Suponha que a i-ésima linha é horizontal (o caso vertical é análogo). Considere o retângulo R formado por todos os quadradinhos acima desta linha.
Este retângulo tem área 6k, onde k é o número de quadradinhos na vertical.
Seja y o número de dominós completamente contidos em R. Veja que 2y
quadradinhos de R são cobertos por estes dominós. Os demais quadrados
correspondem a metades de dominós (afinal, cada dominó cobre 2 quadrados), sendo que a outra metade deve estar no restante do quadradão. Segue
que o número de quadrados restantes é exatamente o número de dominós
cortados, que é ni . Portanto,
ni = 6k − 2y
é par.
Observação 1. Algum aluno com inclinação mais formal poderia dizer que
deverı́amos ter provado com mais detalhes que 2y + ni = 6k, isto é, que os
quadrados que sobram correspondem a dominós cortados. Você sabe fazer
isto
3