Em uma das colunas passadas, analisamos o ‘problema do xilindró’, que se passava em um tabuleiro. Este mês, voltamos ao tabuleiro, mas com um problema bem diferente e que ilustra uma técnica matemática interessante. Pegue seu tabuleiro de xadrez (preto e branco mesmo, pois, desta vez, não será preciso pintá-lo; mas, se ainda estiver pintado, não tem problema…) e distribua quantas peças quiser sobre ele, ocupando tanto as casas brancas quanto as pretas, podendo até mesmo preenchê-lo totalmente (64 peças). Regra: uma peça por casa.
O jogo é o seguinte: se uma casa estiver vazia, mas duas ou mais vizinhas dela estiverem ocupadas, então ela tem que ser ocupada por uma peça, como indicado na figura ao lado.
O algoritmo do jogo: 1) localize no tabuleiro as casas vazias que têm duas ou mais vizinhas ocupadas; 2) ponha peças nessas casas marcadas; 3) volte ao passo 1. O objetivo é partir de uma configuração inicial de modo que, depois de repetir certo número de vezes os passos 1, 2 e 3, o tabuleiro esteja completamente coberto. Primeira pergunta: existe essa configuração inicial? Segunda pergunta: qual o menor número de casas que devem ser ocupadas para realizar nosso objetivo?
Resposta da primeira pergunta: sim. E é até fácil encontrar uma configuração inicial. Por exemplo, ocupe todas as casas menos uma. Esta terá, pelo menos, dois vizinhos ocupados (caso em que ela é um canto). Depois de um movimento, voilà ! Acabou o jogo. Mas, para isso, usamos 63 peças! A pergunta mais interessante é: qual será o menor número do qual podemos partir?
Bem, a resolução dessa parte requer um pouquinho de engenhosidade. Olhe de novo a figura. Quando colocamos a peça sobre a casa do meio, dois lados das casas já ocupadas ‘desaparecem’, mas, com isso, acabamos introduzindo dois lados. Isso significa que o perímetro total das peças fica o mesmo (se chamarmos de ‘L’ o lado de uma casa, teremos na figura acima, tanto antes quanto depois do acréscimo da peça, um perímetro total igual a 8L). No caso de três casas vizinhas ocupadas, ‘desaparecem’ três lados, sendo que apenas um é introduzido. Portanto, o perímetro total fica duas unidades menor (no caso, passa de 12L para 10L). Finalmente, no caso de quatro vizinhas ocupadas, quatro lados ‘somem’, sem que se introduza nenhum. Assim, o perímetro total passa de 16L para 12L.
Resumo: o perímetro total fica o mesmo ou diminui, mas nunca aumenta.
“Ótimo… e daí?”, perguntaria o leitor. Aqui entra o argumento final: como o perímetro total permanece constante ou diminui, olhando para a configuração final, podemos dizer qual é o menor valor possível para o perímetro inicial. O perímetro final, quando todo o tabuleiro está coberto, é 8L + 8L + 8L + 8L = 32L. Agora, o que nos resta é tentar encontrar uma configuração inicial de perímetro 32L que resolva nosso problema. 
Aqui entra um pouco de arte e… bem, sorte, pois só mostramos que, no início, o perímetro é de, pelo menos, 32L, mas não que deva ser exatamente 32L. Mas hoje é nosso dia de sorte. A configuração da figura ao lado resolve nosso problema:
Você pode ver que, a partir dessa configuração, cobrimos o tabuleiro depois de sete movimentos. Este é apenas o segundo de muitos problemas que se passam em um tabuleiro. Portanto, cuidem dele com carinho. O tabuleiro vai voltar!
Marco Moriconi ( moriconi@cienciahoje.org.br )
Instituto de Física,
Universidade Federal Fluminense.
Desafio:
E se o tabuleiro for 6 por 8? Qual é a solução?
Solução do desafio anterior :
O problema dos copos é muito parecido com o problema da festa. No início, temos três copos para baixo e zero para cima (está vendo por que o zero é uma grande invenção?). A cada movimento, viramos: a) dois para cima; ou b) dois para baixo; ou c) um para cima e um para baixo. Em cada um desses movimentos, o número de copos para cima é alterado em + 2, – 2 ou 0, o que mantém a paridade inicial (par). Portanto, jamais conseguiremos chegar a + 3, que é ímpar! Na coluna anterior, perguntei por que o argumento usado no problema do ponto fixo não é 100% correto. Resposta: porque nem sempre a sombra está totalmente contida na sombra anterior! Ela pode ser igual, por exemplo. Mas, apesar disso, confie em mim: o teorema está certo.
