Problème du dessin de l'enveloppe
Le problème du dessin de l'enveloppe ou de la maison, parfois appelé maison de Saint-Nicolas (de l'allemand « Haus vom Nikolaus »), est un jeu mathématique qui consiste à dessiner une enveloppe (ou une maison) constituée de 8 segments sans lever le crayon ni repasser sur un trait déjà dessiné.
En Allemagne
En Allemagne, le jeu est connu sous le nom de « Haus vom Nikolaus » (« maison de Saint-Nicolas »). Le dessin de la maison s'accompagne d'un dicton dont chaque syllabe est prononcée à chaque trait de construction : « Das - ist - das - Haus - vom - Ni - ko - laus »[1].
Mathématiques
D'un point de vue mathématique, le problème du dessin de l'enveloppe est un problème de la théorie des graphes. L'objet du problème est la recherche d'une chaîne eulérienne dans le graphe ci-contre.
Le graphe n'admet pas de cycle eulérien car deux sommets sont de degré impair (les sommets 1 et 2 qui sont tous les deux de degré 3), ce qui signifie que l'on ne peut en aucun cas terminer le dessin en revenant à son point de départ. En revanche, il admet des chaînes eulériennes dont les extrémités sont nécessairement les sommets 1 et 2.
En partant du sommet 1, il y a 44 façons de dessiner l'enveloppe et seulement 10 façons de « perdre ». Par symétrie, le nombre de possibilités en partant du sommet 2 est identique.
Les 44 façons de dessiner l'enveloppe en partant du sommet 1.
Les 10 façons de « perdre » en partant du sommet 1.
Notes et références
- (de) Manfred Nitzsche, Graphen für Einsteiger : Rund um das Haus vom Nikolaus, Wiesbaden, Vieweg + Teubner, , 248 p. (ISBN 978-3-8348-0813-4, OCLC 362924418, lire en ligne), p. 1.