Sem solução

Artigo de Luiz Dal Monte Neto, em que explica por que o quebra-cabeça conhecido como problema das canalizações não tem solução.

Por Da Redação SEGUIR SEGUINDO
Atualizado em 31 out 2016, 18h49 - Publicado em 30 nov 1991, 22h00

Luiz Dal Monte Neto

Desde quando iniciei minha colaboração nessa seção, há dois anos e meio, tenho recebido muitas cartas de vários pontos do país, repletas de sugestões e perguntas sobre jogos, quebra-cabeças e passatempos em geral. No início, quando o volume de correspondência era pequeno, tratei de responder a todas, escrevendo pessoalmente aos remetentes. Hoje, devido à quantidade de cartas, isso não é mais possível. Entretanto, os leitores podem ter certeza de que elas continuam sendo lidas com o mesmo interesse e cada uma delas é analisada e comparada com outras para que seja possível detectar as dúvidas mais freqüentes.

Isso me ajuda a planejar os assuntos dos próximos artigos, procurando responder ao maior número delas. É uma ajuda inestimável dos leitores, além de um grande estímulo. No âmbito dos quebra-cabeças, por exemplo, uma das consultas mais comuns diz respeito à célebre questão de gás, água e eletricidade, também conhecida como o problema das canalizações. Seu enunciado é o seguinte: dadas três residências, A, B e C e três estações de distribuição de gás, água e eletricidade como ligar cada casa a cada uma das estações, de modo que as linhas não se cruzem?
Naturalmente, a questão está confinada ao plano, isto é, as linhas não podem sair do papel. Muitos já viram esse pequeno quebra-cabeça, mas poucos sabem que ele foi proposto em 1917 pelo inglês Henry Ernest Dudeney (1847-1930), um dos maiores problemistas de todos os tempos.

Numa das cartas que recebi, o remetente se dizia muito curioso, pois um amigo lhe disse que vira a solução nesta seção, mas não se lembrava mais dela. Deve ter havido algum mal-entendido, por duas razões: além de não termos abordado esse assunto anteriormente, o problema não tem solução. Alguns autores propõem a solução, que contraria o enunciado, no qual não se prevêem ligações entre as casas ou entre estações. Arriscam-se, assim, à justa ira do leitor.
Se imaginarmos esse problema sobre a superfície de uma esfera, poderíamos supor que, graças ao recurso de dar a volta ao “mundo”, haveria uma solução. Mas, não: ele permanece tão insolúvel quanto antes. Entretanto, não se pode generalizar para qualquer superfície de uma rosca ou de uma câmara de pneu – ou do sólido conhecido com o sofisticado nome de toro – é perfeitamente possível traçar as conexões, redimindo em partes as trapalhadas dessas três estatais. O leitor não quer tentar? Há um seguro contra impaciência na seção de soluções, mas certamente não será preciso usá-lo.

Não é verdade que os quebra-cabeças insolúveis não dão prazer. Para alguns deles foram descobertas demonstrações de impossibilidade tão engenhosas e elegantes que conseguem despertar mais júbilo que muitos problemas solucionáveis. Um exemplo famoso é o dos dominós sobre o quadriculado. Naturalmente, é elementar cobrir um quadriculado 8 por 8 casas com 32 peças de dominó, de modo que cada peça ocupe dois quadrados adjacentes. Contudo, se retirarmos previamente dois quadrados de cantos opostos, como arrumar 31 peças sobre as 62 casas remanescentes?

Continua após a publicidade

O que torna esse problema especialmente torturante é a sua aparência fácil – o senso comum parece garantir que ele possui uma solução, enquanto todas as tentativas vão falhando. O diabo é que dezenas e mesmo centenas de tentativas falhas não constituem um prova de impossibilidade. Nesse caso, só uma “visão” repentina e nítida pode aliviar a ansiedade acumulada. Uma “visão” que foi proporcionada pela demonstração de Ralph E. Gomory, com uma simplicidade acachapante. Antes de mais nada, Gomory pinta alternadamente o quadriculado, gerando um tabuleiro de xadrez com dois cantos a menos, que serão da mesma cor.

O tabuleiro fica, portanto, com 32 quadrados pretos e apenas 30 brancos. Cada peça de dominó, por outro lado, seja onde for colocada, terá de cobrir obrigatoriamente dois quadrados adjacentes, ou seja, um branco e um preto. Assim, 31 peças deveriam cobrir 31 quadrados de cada cor. Como o tabuleiro só dispõe de 30 quadrados brancos, a solução é impossível. E se, em vez dos quadrados de cantos opostos, retirássemos quaisquer outros dois, mas de cores diferentes? Haveria solução? O mesmo Ralph mostrou que sim, em 1962, na revista Scientific American.

Basta dividir o tabuleiro, de modo a criar um “caminho” com 1 quadrado de largura e 64 de comprimento, que comece e termine no mesmo ponto. A retirada de dois quadrados de cores opostas seccionará esse caminho em duas partes (ou uma, se eles forem adjacentes). Em qualquer caso, cada pedaço conterá quantidade igual de casas brancas e pretas, isto é, o total será um número par de quadrados e poderá ser preenchido com os dominós. Consequentemente, também o tabuleiro.

Luiz Dal Monte Neto é arquiteto e designer de jogos e brinquedos