Essayer One Stroke gratuitement sur iPhone
Puzzles infinis. Difficulté adaptative. Aucune pub forcée.
Comment une simple question sur une promenade dominicale a inventé toute une branche des mathématiques
Au XVIIIe siècle, la ville de Königsberg (aujourd'hui Kaliningrad, en Russie) a été construite sur les deux rives de la rivière Pregel, avec deux grandes îles au milieu. Sept ponts reliaient ces quatre masses continentales.
Les citoyens avaient une question simple :Est-il possible de traverser la ville à pied, en traversant chacun des sept ponts exactement une fois, sans traverser deux fois aucun pont ?
Rive Nord (A)
/ | \
b1 b2 b3
/ | \
Île | Île
(B)----b4----(C)
\ | /
b5 b6 b7
\ | /
Rive Sud (D)
7 ponts reliant 4 continents
Pouvez-vous traverser chaque pont exactement une fois ?Les gens ont essayé et échoué pendant des années. Personne n'a pu trouver un itinéraire. Mais personne non plus ne pouvait prouver que c'était impossible — jusqu'à ce qu'un mathématicien nommé Léonhard Euler relève le défi en 1736.
Le génie d'Euler a été de réaliser que la configuration exacte de la ville n'avait pas d'importance. Ce qui comptait, c'était le structure des connexions – quelles masses continentales étaient reliées à lesquelles et par combien de ponts.
Il a supprimé tous les détails géographiques et a réduit le problème à son essence :
A (3 ponts) --- B (5 ponts) | | C (3 ponts) --- D (3 ponts) Chaque lettre = une masse continentale (sommet) Chaque connexion = un pont (bord) Nombre = combien de ponts touchent cette masse continentale
Ce fut la naissance de ce que nous appelons aujourd'hui un graphique — un ensemble de sommets (nœuds) reliés par des arêtes. Euler venait d'inventer théorie des graphes.
Euler a remarqué quelque chose de crucial concernant le nombre de ponts touchant chaque masse continentale (ce que nous appelons maintenant le diplôme de chaque sommet) :
Les quatre masses continentales possèdent un nombre impair de ponts. Euler a prouvé que cela rendait le problème impossible.
Son raisonnement : si vous traversez un territoire (en entrant par un pont et en sortant par un autre), vous utilisez des ponts. deux à la fois. Ainsi, toute masse continentale qui n'est pas votre point de départ ou d'arrivée doit avoir un même nombre de ponts. Un chemin qui traverse chaque pont une fois peut avoir au maximum deux sommets de degrés impairs (le début et la fin).
Königsberg a quatre sommets de degrés impairs. Par conséquent, aucune solution n'existe.
Le théorème d'Euler nous a donné les règles exactes pour savoir quand un parcours "en un seul temps" est possible :
Chaque jeu de réflexion en un seul coup, y compris One Stroke - est construit sur ces règles. Lorsque l'algorithme de génération procédurale de One Stroke crée un nouveau puzzle, il utilise le théorème d'Euler pour garantir mathématiquement que chaque puzzle a au moins une solution.
Lorsque vous jouez à un puzzle en un seul trait, vous résolvez le même type de problème qu'Euler a résolu en 1736. Vous faites de la théorie des graphes – vous ne le savez peut-être pas.
L’idée apparemment simple d’Euler sur les ponts a lancé tout un domaine des mathématiques. La théorie des graphes est désormais essentielle pour :
Tout a commencé avec une question sur sept ponts dans une ville prussienne – et un mathématicien qui a vu l’élégante structure cachée en dessous.
Il s'agit d'un célèbre puzzle mathématique datant de 1736. La ville de Königsberg possédait sept ponts reliant deux îles et deux zones continentales. La question : peut-on traverser la ville à pied en traversant chaque pont exactement une fois ? Euler a prouvé que c'était impossible car les quatre continents possédaient un nombre impair de ponts.
La solution d'Euler est considérée comme le premier théorème de la théorie des graphes, une branche des mathématiques désormais fondamentale pour l'informatique, l'analyse de réseaux, le routage GPS et la conception de jeux de réflexion. Chaque jeu de réflexion en un seul coup est un descendant direct de cette preuve de 1736.
Les énigmes en un seul trait posent la même question fondamentale que les Sept Ponts : pouvez-vous parcourir chaque chemin exactement une fois sans revenir sur vos pas ? Le théorème d'Euler fournit les règles mathématiques permettant de déterminer quand cela est possible. Des jeux comme One Stroke utilisent ces règles pour générer des énigmes dont la résolution est garantie.
Königsberg est maintenant Kaliningrad, en Russie. Deux des ponts d'origine ont été détruits pendant la Seconde Guerre mondiale et d'autres ont été reconstruits. La ville moderne a une disposition de pont différente, mais la vision mathématique qu'Euler a dérivée des sept ponts originaux reste intemporelle.
Puzzles infinis. Difficulté adaptative. Aucune pub forcée.