O enigma das três casas , também chamado de enigma da água, gás e eletricidade , é um jogo matemático cuja análise usa um teorema de topologia ou teoria dos gráficos . Este problema não tem solução. Georges Perec cita-o em 1978 no seu livro Je me souviens : “Lembro-me das horas que passei, na terceira classe, creio, tentando abastecer três casas com água, gás e eletricidade, sem a passagem dos canos (não há solução porque contanto que você fique em um espaço bidimensional; este é um dos exemplos elementares de topologia, como as pontes de Königsberg , ou a coloração de mapas ) ” .
Esse enigma já foi colocado por Henry Dudeney em 1917 em seu livro Amusements in mathematics . Ele especifica que "há meia dúzia de quebra-cabeças tão antigos quanto o mundo, que reaparecem constantemente" . O do artigo é aquele que ele chama de água, gás e eletricidade . É popularizado por Martin Gardner , que o apresenta em seu Sexto Livro de Jogos de Matemática .
Existem duas abordagens para demonstrar a inexistência de uma solução conectando cada uma das três casas diretamente aos três fornecedores. A primeira abordagem que mostra a impossibilidade usa o teorema de Jordan , indicando que se desenharmos um loop em um plano, o complemento do loop , ou seja, a parte não desenhada do plano, consiste em dois conectados por arcos , um limitado (o dentro do loop) e o outro não (fora do loop). A segunda abordagem, mais geral, usa a fórmula de Euler para gráficos planares . É um passo na prova do teorema chave dos grafos planares, devido a Kazimierz Kuratowski .
Em forma de história, o enigma é expresso da seguinte forma:
“Um loteamento de três casas deve ser equipado com água, gás e eletricidade. Os regulamentos proíbem o cruzamento de tubos por razões de segurança. Como devo fazer isso? "
A historiette tem muitas variações. Encontramos, por exemplo, este: "Ele tem ... 3 carros, que devem poder estacionar indiferentemente nas vagas 1, 2 ou 3 ... Ele gostaria de desenhar estradas ligando cada carro a cada um dos sites (um total de 9 estradas distintas) para que cada veículo possa ir a qualquer um desses locais, mas, para evitar colisões, esses caminhos não devem em caso algum se cruzar ou ser confundidos (mesmo que parcialmente). Estes caminhos podem passar atrás de parques de estacionamento e automóveis, e ter qualquer forma, mas não devem cruzar os relvados (nem claro outros veículos) ” .
Esse problema também pode ser visto de forma abstrata como um gráfico , o que permite que seja estudado matematicamente. Um grafo é formado por um conjunto de pontos, chamados de nós ou vértices , alguns dos quais são conectados por elos (também chamados de arestas ). No caso do enigma, existem dois conjuntos de nós: o conjunto M tendo três nós para as três casas (em azul na figura ao lado), e o conjunto F tendo três nós para a chegada de gás, água e eletricidade ( em vermelho na figura ao lado). O enigma pede que haja um elo entre cada nó de M e cada nó de F , de forma que dois elos não se cruzem: uma forma possível de organizar esses elos é mostrada na figura ao lado com os elos em verde. Um grafo no qual todos os nós de um conjunto de m elementos devem estar ligados aos de um conjunto de n elementos é chamado de grafo bipartido completo , denotado por K m, n . Um gráfico no qual dois links não se cruzam é chamado de plano . A questão é: K 3.3 é um gráfico planar?
Um primeiro passo, para elucidar o enigma, consiste em fazer testes . Isso leva a uma dupla observação. Rapidamente, quem tenta resolver o enigma quase chega lá , ou seja, consegue lançar oito tubos, mas o último resiste. A segunda observação é que existem muitas possibilidades diferentes para testar.
Intuitivamente, parece óbvio que alguns deles são equivalentes. Duas tentativas de forma que seja possível deformar continuamente os tubos para passar da primeira para a segunda correspondem de fato à mesma tentativa. Essa equivalência tem um nome na matemática, é chamada de homotopia . Acontece que essa noção, difícil de formalizar com precisão, dificilmente é necessária para resolver o enigma. Apesar dessa observação, ainda há uma grande quantidade de tentativas possíveis. O tubo que liga a primeira casa ao gás (seguindo a ordem sugerida na ilustração no parágrafo das Declarações ) pode passar entre a água e a eletricidade, mas também passar entre a primeira casa e o fornecedor de água, ou mesmo descer e contornar a segunda e terceiras casas na parte inferior.
Uma rápida revisão conclui que existem infinitas possibilidades. O tubo que liga a primeira casa à eletricidade pode começar contornando as três casas n vezes e depois ligar a eletricidade. Esses n truques não oferecem nenhuma esperança de solução, mas, à primeira vista, não parece fácil encontrar um bom critério para eliminar as tentativas desnecessárias, o que torna o enigma um pouco confuso. Percorrer um número infinito de possibilidades é dificilmente praticável.
Todas as tentativas desta natureza conduzem, na melhor das hipóteses, à colocação de oito tubos, então torna-se impossível ir mais longe. Esse ponto comum pode sugerir que a abordagem correta consiste em partir de um raciocínio diferente. Esta boa abordagem é baseada em um conceito e um teorema suficientemente intuitivo para que uma demonstração não seja considerada possível antes do século E XIX. Uma reflexão mais aprofundada mostra que não é esse o caso e que são suficientes para construir uma prova facilmente compreensível da inexistência de uma solução.
O conceito-chave da prova é conectividade. Uma ilustração do conceito é dada pelo arquipélago das Ilhas Canárias na imagem ao lado. Uma ilha está ligada por arcos , ou seja, para qualquer par de pontos da ilha, existe um caminho que vai de um ponto a outro sem sair da ilha. Por outro lado, o encontro de duas ilhas não está ligado por arcos: não existem caminhos que permitam passar entre dois pontos sem se molhar, se estiverem em duas ilhas diferentes. Uma ilha é um componente conectado por arcos : é um conjunto máximo de pontos entre os quais existe um caminho. Um arquipélago consiste, portanto, em vários componentes conectados por arcos , ou seja, 5 na imagem ao lado.
Em termos matemáticos, se A é um conjunto dotado de uma topologia e se, para quaisquer dois pontos de A , existe um caminho em A que conecta os dois pontos, diz-se que A está conectado por arcos .
Um segundo conceito é o de fronteira . No exemplo do arquipélago, a fronteira corresponde à costa, ou seja, a todos os pontos que tocam simultaneamente uma ilha e o mar. Em termos mais matemáticos, um ponto está na fronteira de um conjunto E quando um disco está centrado neste ponto e de raio estritamente positivo toca o conjunto E e seu complemento.
O teorema-chave da prova é ainda mais confuso em aparente simplicidade. Em essência, indica que não é possível ir da Suíça para a França sem cruzar a fronteira. Para colocá-lo em termos mais matemáticos, um pouco de vocabulário é útil.
Para estabelecer a prova, é necessário introduzir a noção de curva de Jordan , também chamada de renda simples . Esta curva é uma linha contínua no plano, que não faz interseção. Na figura à direita, a borda em preto é um exemplo de curva de Jordan. Um círculo também é uma curva de Jordan, pois é sempre uma linha contínua sem se cruzar. Por outro lado, um 8 não é, pois há uma cruz no centro do 8.
O teorema de Jordan trata do complemento de uma curva S de Jordan . O teorema considera parte do plano que não contém S . Isso indica que ele contém dois componentes arcwise ligado adicionais, cuja borda é a curva S . No exemplo ao lado, um componente é azul enquanto o outro é vermelho e a borda é preta. Embora o resultado pareça intuitivamente óbvio, sua demonstração não é. Na verdade, demorou mais de meio século para obtê-lo. O elemento chave do teorema está na definição de conectividade na seção anterior: considere um ponto a na área azul e um ponto b na vermelha. Se se deseja ir de a para b , é necessário sair da zona azul e uma fronteira é cruzada. Da mesma forma, a França pode corresponder a um componente conectado por arcos, a Suíça a outro, e não é possível ir de uma cidade na Suíça a uma cidade na França sem cruzar a fronteira. Raciocinar em termos de componentes conectados por arcos e bordas, ou mesmo ilhas e litorais, permite evitar a complexidade combinatória.
Colocar um oleoduto equivale a proibir uma área do espaço. Se um conjunto de tubos formar um loop, aplicam-se as ideias anteriores. Desenhando a solução em uma folha de papel, podemos recortar as duas áreas separadas, separá-las e tentar resolver o enigma nas diferentes ilhas assim obtidas.
O princípio do raciocínio é pelo absurdo . Supomos que existe uma solução, mostramos que essa existência contradiz o teorema de Jordan. Deduzimos que ele não pode existir porque o teorema de Jordan nunca é contradito. São utilizadas as seguintes notações: M 1 , M 2 , M 3 designam as três casas, F 1 o fornecedor de água, F 2 o da electricidade e F 3 o do gás.
O primeiro objetivo é separar o espaço em dois componentes conectados por arcos, ou seja, criar duas ilhas distintas. Como se assume que existe uma solução, é possível considerar o tubo que liga M 1 a F 1 , ao qual adicionamos aquele que liga F 1 a M 2 , ao qual adicionamos aquele que liga M 2 a F 2 , junto a F 2 a M 3 , depois M 3 a F 3 e , a seguir, F 3 a M 1 . Eles são ilustrados na figura à esquerda. Obtemos uma curva de Jordan contendo, em ordem, os pontos M 1 , F 1 , M 2 , F 2 , M 3 , F 3 e novamente M 1 . Se nada nos garante que a configuração de solução do enigma (que supomos existir) é de fato a da esquerda, sabemos pelo menos uma coisa: esses tubos formam uma curva de Jordan contendo na ordem anterior, as três casas e as três fornecedores.
Essa curva divide o plano em dois componentes conectados por arcos, que podem ser considerados duas ilhas distantes. Cada um desses dois componentes conectados por arcos possui uma borda contendo todas as casas e todos os fornecedores. Cada um desses dois componentes conectados por arcos é análogo à figura à direita. Analógico aqui significa que os conjuntos estão conectados por arcos e têm a mesma borda.
Se o resultado não parece chocante para o componente azul, pode parecer mais surpreendente para a rosa. O componente rosa corresponde mais a um continente infinitamente vasto atravessado por um mar interior do que a uma ilha. Como os dois elementos principais são a conectividade e o limite, isso não importa muito. Para estarmos convencidos disso, podemos imaginar esta transformação do plano chamada inversão , que deixa o círculo invariante, transforma o interior em exterior e vice-versa. Esta transformação não se dirige ao centro do círculo. Mas, para o enigma, adicionar um ponto isolado não muda nada quanto à existência ou não de uma solução. É fácil contornar isso, para a direita ou para a esquerda. Outra maneira de ver isso é imaginar a solução do enigma na esfera e não no plano. Ao colocar a curva de Jordan no equador, a semelhança entre as duas ilhas se torna evidente. A figura na parte inferior direita mostra que uma esfera sem seu pólo norte pode ser vista, usando uma projeção estereográfica , como um plano. Os dois quebra-cabeças em um plano ou esfera são, portanto, equivalentes.
A partir de agora, colocar qualquer novo tubo resulta em um golpe de cinzel que gera uma nova ilha. Essa fragmentação do espaço está na origem da impossibilidade. A vantagem de tal abordagem é que ela evita qualquer combinação. Como mostra o parágrafo anterior, na ordem correta, as seis primeiras poses são, de certo ponto de vista, forçadas . Seja como for, a colocação dos primeiros seis tubos sempre resulta na mesma configuração topológica. Sob a condição de desmembrar o espaço em ilhas de forma que a costa contenha os nós (casas e fornecedores), é possível limitar-se ao estudo de uma única configuração, para o resto do raciocínio.
A tubulação que fornece eletricidade para a primeira casa está em um dos dois componentes conectados por arcos no parágrafo anterior. Note que há um . Este componente A contém uma linha que liga M 1 a F 2 , situado para o interior de um consistindo de todos os pontos que ou todos os rosas azuis, mas nunca verdes. Obtemos uma nova curva de Jordan composta pela reta M 1 F 2 , depois pelas retas F 2 M 3 F 3 M 1 . Finalmente, obtemos a reta M 1 F 2 M 3 F 3 M 1 . Ele define um novo componente conectado por arcos, denotado A 1 . Pode-se perguntar se esta nova ilha contém os pontos F 1 e M 2 . Já sabemos que eles não estão na linha F 2 M 3 F 3 M 1 . Também não podem estar localizados na linha M 1 F 2 porque esta linha está localizada dentro de A , ou seja, na ilha A e não na costa, mas os pontos F 1 e M 2 não estão localizados na ilha em si, mas na a fronteira. O mesmo motivo indica que eles não podem ser localizados dentro de A 1 . Obtemos também uma ilha A 2 , cuja orla é formada por tubos que conectam: M 1 F 1 M 2 F 2 M 1 . O teorema de Jordan nos assegura ainda que essas duas zonas são de fato ilhas distintas, ou seja, componentes conectadas por arcos disjuntos.
O espaço agora está fragmentado em três ilhas, duas das quais contêm apenas quatro nós. Agora vamos colocar o cano que conecta a segunda casa ao gás. Ele está localizado em um dos três componentes conectados por arcos. Este componente conectado por arcos tem uma borda contendo M 2 e F 3 . Nem A 1 nem A 2 têm esta propriedade. É, por conseguinte, o componente ligado por arcos que não foi cortado pelo tubo de ligação M 1 a F 2 que contém esse tubo. Mais uma vez, com o ponto de vista adotado, o golpe é forçado . Se denotarmos por B 1 e B 2 essas duas novas componentes conectadas por arcos, ambas têm como fronteira uma curva de Jordan e suas fronteiras passam, para B 1 pelos pontos M 1 F 1 M 2 F 3 M 1 e para B 2 por M 2 F 2 M 3 F 3 M 2 .
O espaço agora está fragmentado em quatro ilhas, vendedores e casas estão todos na costa e nenhuma ilha tem mais do que quatro. Além disso, sabemos, para cada ilha, a natureza exata dos fornecedores e casas no litoral. Agora é uma questão de conectar a terceira casa à água. Uma rápida revisão dos diferentes limites mostra que nenhum deles contém a terceira casa M 3 e a água F 1 .
Este último tubo percorre pelo menos dois componentes ligados por arcos (ou seja, passa de uma ilha a outra sem passar pelo mar). Este resultado está em contradição com o teorema de Jordan. Ela termina a demonstração com o absurdo.
Este enigma entra no ramo matemático denominado teoria dos grafos e pode ser tratado pela fórmula de Euler . Esta fórmula é um ingrediente da prova do teorema fundamental dos gráficos planares. Um gráfico é um conjunto de pontos , às vezes chamados de nós ou vértices , conectados uns aos outros por arestas ou links . Um gráfico é chamado de "plano" se for possível representá-lo em um plano. Dois links só podem se cruzar na localização de um nó. Nem todos os gráficos são planos, este enigma fornece um contra-exemplo. A origem do estudo de grafos planares de uma demonstração do desejo do teorema de quatro cores no meio do XIX ° século. O teorema-chave é obra de Kazimierz Kuratowski e data de 1930: caracteriza, entre os gráficos, aqueles que são planos, e portanto se aplica ao caso particular do enigma.
Para entender o raciocínio da teoria dos grafos, uma definição é útil. Uma face de um gráfico plano é um componente conectado por arcos do complemento do gráfico no plano. Cada face possui uma borda composta de arestas, o número dessas arestas é chamado de grau de uma face. Se f denota o número de faces do gráfico, n é seu número de nós e tem o número de arestas, a fórmula de Euler afirma que, para um grafo planar conectado não vazio:
.(Um gráfico é conectado se houver sempre um conjunto de arestas permitindo ir de um nó a outro.) Além disso, um cálculo rápido mostra que a soma dos graus das diferentes faces é igual a duas vezes o número de arestas em um coplanar gráfico. Já na situação das três casas, qualquer curva de Jordan que delimite uma face passa por pelo menos quatro pontos do gráfico, portanto, qualquer face do gráfico é de grau pelo menos 4. Na verdade, não há cano conectando uma casa a ela. - mesmo, então o grau um não é possível. Não há dois tubos conectando a mesma casa ao mesmo fornecedor, o grau dois ainda é impossível. O grau três pressupõe que duas casas ou dois fornecedores estão ligados por um pipeline, o que sempre é impossível. Isso dá a marcação:
.Ao aplicar este aumento à fórmula de Euler, obtemos:
.No entanto, existem nove arestas, três por casa e seis nós, dos quais três são casas e três são fornecedores. O aumento leva então, no caso de um gráfico planar, a uma contradição: nove é menor que oito. Essa contradição mostra que o grafo procurado não pode ser plano.
A impossibilidade de resolver o enigma é uma consequência do teorema de Jordan. Uma geometria para a qual existe uma solução deve, portanto, admitir curvas de Jordan que não dividam o espaço em dois componentes conectados por arcos. Conforme mostrado no parágrafo intitulado Topologia geométrica , a busca por uma solução em uma esfera é fútil, um método rápido para se convencer disso é perceber que o teorema de Jordan é válido nesta geometria.
Por outro lado, o teorema não se aplica se o espaço não for orientável . Em um espaço não orientável, o lado direito de algumas curvas acaba virando o lado esquerdo. Em outras palavras, o conceito de direita e esquerda não tem significado nesse espaço. É o caso de uma tira de Möbius . A linha equidistante das duas arestas possui esta propriedade. Faz sentido colocar as três casas e os três fornecedores nessa linha, como na figura à esquerda. Os primeiros seis tubos não cortaram a geometria em dois componentes conectados por arcos.
Para entender o que acontece depois que esses seis primeiros tubos são colocados, a maneira mais fácil é construir uma fita Möbius, desenhar os vários nós e realmente cortar a fita. Obtemos a figura no canto superior direito (não mostramos a dupla torção induzida pelo corte, uma vez que não altera a resolução do enigma). A fita torna-se uma única fita nova, com o dobro do comprimento e a metade da largura. Uma das bordas da faixa de opções agora contém dois conjuntos de seis nós, um após o outro.
Por uma questão de simplicidade, é mais fácil deformar o cilindro obtido. Nós apertar a fronteira não contendo os nós até essa fronteira é reduzida a um ponto, em seguida, adicione este ponto (vimos anteriormente que isso não muda a resolução do enigma) para obter um cone . O achatamento deste cone, que ainda não altera a existência ou ausência de uma solução, dá a figura no canto inferior direito. Torna-se fácil descobrir como colocar os três últimos tubos. A solução no canto inferior direito é a ilustrada à esquerda, uma vez que as transformações inversas tenham sido realizadas. .
A faixa de Möbius é um exemplo de superfície que não satisfaz o teorema de Jordan porque não é orientável. Outras superfícies são orientáveis e, no entanto, não satisfazem o teorema. Este é o caso do toro . Existe desta vez, não um, mas dois tipos de curvas de Jordan cujo complemento é conectado por arcos. Por isso, é possível resolver o quebra-cabeça até com quatro casas e quatro vendedores. Considerar uma geometria contendo um orifício , como o toro, permite a representação de um gráfico não plano. Qualquer gráfico é representado em uma superfície com um número suficientemente alto de orifícios , também chamado de gênero da superfície. Em tal superfície, e sob a condição de fazê-lo corretamente, existem duas curvas de Jordan que não criam novas faces, a equação de Euler é então escrita n - a + f = 0. Se houver quatro casas e quatro fornecedores, o gráfico é composto por oito nós e dezesseis arestas, o que implica a existência de oito faces. O número médio de arestas por face é o dobro do número de arestas, então encontramos quatro como o valor médio. Como esse também é o número mínimo de arestas para uma face, a solução só tem faces com quatro arestas.
A primeira curva de Jordan é mostrada na figura superior esquerda. Quanto à faixa de Möbius, obtemos um cilindro, mostrado à direita. Desta vez, os nós não estão todos no topo, mas uma série está na borda superior e outra na borda inferior. A técnica anterior, de transformar o cilindro em disco, equivaleria a identificar os diferentes nós em um único ponto, o que não é aceitável. Por outro lado, é possível estabelecer uma ligação entre o nó M 1 localizado na parte inferior (com as notações anteriores M 1 corresponde à primeira casa. As casas são ilustradas em azul nas figuras) e o nó F 2 ( que designa o segundo fornecedor. Os fornecedores são apresentados a vermelho nas figuras). Este link é mostrado em verde na figura no canto superior direito. Obtemos então uma figura comparável a um disco. Este disco, mostrado no canto inferior direito, tem dezoito nós. Cada nó é representado duas vezes, com exceção dos nós M 1 e F 1 que são representados três vezes. A área superior é mostrada em cinza claro e a área inferior em cinza escuro. Nessa forma de disco, é fácil encontrar a configuração certa.
É questionável se existe uma solução para cinco fornecedores e cinco casas. O mesmo cálculo mostra que o número médio de arestas por face é igual a dez terços, ou seja, estritamente menor que quatro. No entanto, quatro é o mínimo de arestas para construir uma face para este enigma. A busca por uma solução é, portanto, inútil.
Construção da soluçãoUm raciocínio simples permite determinar a configuração correta e sem tentativa e erro. A primeira curva de Jordan fornece oito links. O nono link transforma a pergunta em um problema simples. Existem ainda sete links a serem colocados e já sabemos que cada face (ou seja, cada componente conectado por arcos do complemento) é delimitada por exatamente quatro links.
Em sua forma de disco, existem dezoito nós, que são repetições dos oito nós presentes na forma de toro. Eles são repetidos duas vezes, com exceção dos nós M 1 e F 2 que são repetidos três vezes. Na forma do disco, adicionar um link, para criar faces contendo quatro links, resulta na colocação de um tubo que salta dois nós para se conectar ao próximo. Como, afinal, são estas as únicas faces que existem, não adianta procurar outros tipos de assentamento de tubos. Colocar um link torna então inacessíveis, na forma de disco, os dois nós que ele envolve.
Ainda falta remontar a solução no toro. A convenção escolhida é representar um lado da primeira curva de Jordan em cinza escuro e o outro em cinza claro. Os tubos que ficam próximos à primeira curva de Jordan permanecem da mesma cor, os demais são aqueles que circundam o toro , como o nono tubo. Obtemos a primeira figura à esquerda.
Esta solução ainda dificilmente é satisfatória para a compreensão genuína de como os tubos são organizados no toro. A representação geométrica é mais simples ao posicionar os nós de uma forma mais geométrica . Vamos colocar o toro plano em um plano horizontal. No círculo de maior altitude, vamos colocar 4 nós em duas diagonais ortogonais, de forma que uma diagonal suporte duas casas e as outras dois fornecedores. O círculo corresponde aos primeiros quatro tubos. No círculo de baixa altitude, agimos da mesma forma, então giramos os quatro novos nós de um quarto de volta, o círculo de baixa altitude corresponde a quatro tubos adicionais. Ao conectar um nó de dentro ao nó localizado exatamente abaixo, obtemos mais quatro tubos. Para os quatro últimos, imagine que os tubos são elásticos, conectamos, por meio de quatro tubos, os quatro nós superiores aos quatro nós inferiores pelo lado de fora, então uma rotação de meia volta é aplicada às extremidades inferiores dos quatro últimos nós. Essa configuração é mostrada na figura inferior. As oito faces, dezesseis arestas e oito nós são mais facilmente visíveis. Os oito links escuros correspondem à primeira curva de Jordan.