Problema das três casas

O chamado problema das três casas, conhecido também como água, gás e eletricidade ou problema das três utilidades, é um quebra-cabeça matemático clássico, que pode ser declarado como segue:

Suponha que haja três casas em um plano (ou superfície de uma esfera) e cada uma precisa ser ligada às empresas de gás, água e eletricidade. O uso de uma terceira dimensão ou o envio de qualquer uma das conexões através de outra empresa ou casa não é permitido. Existe uma maneira de fazer todos os nove ligações sem qualquer uma das linhas que se cruzam?

O problema é um quebra-cabeça matemático abstrato que impõe restrições que não existiriam em uma situação prática de engenharia.

História

Henry Dudeney afirma que o problema é "tão antigo quanto as colinas... muito mais velho do que iluminação elétrica, ou mesmo gás";[1] uma revisão da história do problema é dada por Kullman que afirma que a maioria das referências publicadas para o problema o caracterizam como "muito antigo".[2]

Solução

O gráfico de utilidade, também conhecido como o gráfico de Thomsen ou K_3,3

A resposta para o enigma estrito colocado acima é não; É impossível ligar as três casas com as três diferentes utilidades sem pelo menos uma das ligações cruzarem com as outras. Perguntas mais generalizadas podem ter respostas diferentes.[3]

Referências

1. Dudeney, Henry (1917). Amusements in mathematics. [S.l.]: Thomas Nelson 
2. Kullman, David (1979). «The Utilities Problem». Mathematics Magazine. 52 (5): 299–302. JSTOR 2689782. 
3. Gas Water Electric Puzzle from puzzles.nigelcoldwell.co.uk

Ligações externas

• Luiz Dal Monte Neto; Sem solução - super.abril.com.br

Ver também

• Sete pontes de Königsberg