Prêt à perdre des neurones ? Les maisons de Dudeney

BONJOUR À TOUS ! Vous allez bien ?

Ce week-end, je vous propose une énigme du célèbre Henri Dudeney parue pour la première fois dans son livre Amusements of Mathematics en 1917 : l’énigme des trois maisons de Dudeney.

Voici son énoncé : trois familles voisinent se détestant mutuellement ont besoin, comme toute personne, d’eau, d’électricité et de gaz et doivent donc accéder quand elles le veulent aux trois usines. Vous êtes le maire de la ville où habitent ces familles. Elles vous demandent de l’aide pour l’accès aux usines et expliquent qu’elles souhaitent que vous construisiez les routes d’accès de chacune des maisons à chacune des usines, cependant, elles ne doivent pas se croiser pour éviter tout problème.

Plus clairement, dans le schéma ci-contre, il faut que chaque maison soit reliée à chaque usine sans qu’aucun trait de liaison n’en croise un autre.

MAIS, avant que vous n’essayiez (c’est assez tentant je l’avoue), ceci est IMPOSSIBLE.

L’insolubilité des trois maisons de Dudeney a (Malheureusement ?) été démontrée.

Afin de la prouver, il a fallu étudier la théorie des graphes.

Un graphe demeure, en simple, un ensemble de sommets reliés par des arêtes. Un graphe se dit planaire lorsque ses arêtes ne se croisent jamais (comme dans l’image ci-contre à droite). Nous cherchons donc pour notre énigme un graphe planaire.

En théorie des graphes, pour les graphes planaires, nous connaissons une formule, celle d’Euler :

S + R = A + 2

Où S = Nombre de sommets ; R = Nombre de régions du graphe ; A = Nombre d’arêtes

Ci-dessous un graphe légendé avec une région, un sommet et une arête :

Par exemple ci-dessus, le graphe a 6 régions (l’extérieur du graphe compte comme une région), 5 sommets et 9 arêtes. Vérifions la formule d’Euler :

S + R = 5 + 6 = 11

A + 2 = 9 + 2 = 11

S + R = A + 2

Revenant à nos moutons avec nos nouvelles connaissance, il nous faut pour nos familles un graphe planaire qui doit posséder 6 sommets (3 usines et 3 maisons donc 6 sommets) et 9 arêtes (3 chemins x 3 maisons). Donc puisque S + R = A + 2 ; 6 + R = 9 + 2 ce qui nous amène au fait qu’il doit y avoir 5 régions.

Puisque chaque arête intervient dans la délimitation de 2 régions, on aura une moyenne de 3,6 arêtes par régions (pour les curieux : 2A/R = 2 x 9 / 5 = 3,6). De cette manière, chaque région doit être délimitée par 3 régions au moins ; mais, cette dernière affirmation impliquerait que soient reliés des usines entre elles ou des maisons entre elles, ce qui reste contre les règles de l’énigme. Il reste donc impossible de résoudre l’énigme, vous avez avec moi démontrer que les trois maisons de Dudeney est insoluble, BRAVO !

Pour faire passer le temps, vous pouvez toujours quand même essayer de démontrer l’indémontrable, mais, enre nous, ça risque de se terminer en…

À lundi tout le monde ! Camille Jordan ça vous dit ?