(U)Ma Temática Elementar por José Carlos Santos - Será sempre possível?

No mês passado deixámos aqui um problema: dado um tabuleiro de xadrez e dadas peças de dominó, cada uma das quais é do tamanho de dois dos quadrados do tabuleiro, se escolhermos dois quadrados de cores opostas será sempre possível cobrir o resto do tabuleiro com peças de dominó? Sim, é sempre possível.

 

Se pensarmos bem, isto não é um problema. É, isso sim, uma família de problemas: para cada dois quadrados que considerarmos, como é que devemos proceder para resolver o problema? Nas duas figuras abaixo, vemos dois desses problemas:

          

 

É claro que é perfeitamente possível conseguir-se resolver o problema no caso do tabuleiro da esquerda sem que se consiga resolvê-lo no caso do tabuleiro da direita. Ou ao contrário. Ou não resolver nenhum. Afinal, o que é que garante que o problema tem solução? Tudo o que foi visto no mês passado foi que o problema não tem solução caso os quadrados sejam da mesma cor. E, mesmo que tenha, é perfeitamente possível resolver o problema relativo à figura da esquerda de uma maneira totalmente distinta da usada para resolver o problema no caso da direita.

 

Mas vamos ver que, não só o problema tem, de facto, sempre solução, como há uma maneira uniforme de o resolver. Isto foi provado por um executivo da IBM, Ralph Gomory, e baseia-se na próxima figura:

 

 

Para resolver o problema, basta ir colocando as peças de dominó ao longo da linha em ziguezague que se vê na figura. O facto de termos excluído dois quadrados da mesma cor garante que o número de quadrados que vai de um dos quadrados em falta até ao seguinte é par, pelo que não há qualquer problema ao tentarmos colocar as tais peças. Se, por exemplo, tentarmos resolver o primeiro dos problemas anteriores por este método, então o que obtemos é:

 

Agora que este problema está resolvido, podemos complicá-lo. E se agora excluirmos quatro quadrados do tabuleiro, dois brancos e dois pretos? Será que o problema tem sempre solução? Não, pois agora há um novo obstáculo: se mantivermos um dos cantos do tabuleiro mas excluirmos os seus dois vizinhos mais próximos, é claro que o problema não tem solução. E acontece que este é o único obstáculo. Ou seja, se excluirmos do tabuleiro quatro quadrados tais que:

 

• dois são brancos e dois são pretos;

• se excluirmos um canto, então também excluímos pelo menos um dos seus dois vizinhos mais próximos

 

então o problema tem solução. Só que ainda não apareceu nenhum Gomory para provar isto. A única demonstração conhecida deste facto é complexa e obriga a considerar uma data de casos. Por isso, se o leitor tiver algum tempo livre e se interessar por esse assunto, já sabe…