The Alcuin number of a graph
By Péter Csorba, Cor Hurkens and Gerhard Woeginger
Proceedings of the 16th European Symposium on Algorithms (2008)
Abstract: We consider a planning problem that generalizes Alcuin’s river crossing problem (also known as: The wolf, goat, and cabbage puzzle) to scenarios with arbitrary conflict graphs. We derive a variety of combinatorial, structural, algorithmical, and complexity theoretical results around this problem.
Introduction: The Anglo-Saxon monk Alcuin (735–804 A.D.) was one of the leading scholars of his time. He served as head of Charlemagne’s Palace School at Aachen, he developed the Carolingian minuscule (a script which has become the basis of the way the letters of the present Roman alphabet are written), and he wrote a number of elementary texts on arithmetic, geometry, and astronomy. His book “Propositiones ad acuendos iuvenes” (Problems to sharpen the young) is perhaps the oldest collection of mathematical problems written in Latin. It contains the following well-known problem.
A man had to transport to the far side of a river a wolf, a goat, and a bundle of cabbages. The only boat he could find was one which would carry only two of them. For that reason he sought a plan which would enable them all to get to the far side unhurt. Let him, who is able, say how it could be possible to transport them safely?
In a safe transportation plan, neither wolf and goat nor goat and cabbage can be left alone together. Alcuin’s river crossing problem differs significantly from other mediaeval puzzles, since it is neither geometrical nor arithmetical but purely combinatorial. Biggs mentions it as one of the oldest combinatorial puzzles in the history of mathematics. Ascher states that the problem also shows up in Gaelic, Danish, Russian, Ethiopian, Suaheli, and Zambian folklore. Borndorfer, Grotschel & Lobel use Alcuin’s problem to provide the reader with a leisurely introduction into integer programming.
Click here to read this article from the Hungarian Academy of Sciences
By Péter Csorba, Cor Hurkens and Gerhard Woeginger
Proceedings of the 16th European Symposium on Algorithms (2008)
Abstract: We consider a planning problem that generalizes Alcuin’s river crossing problem (also known as: The wolf, goat, and cabbage puzzle) to scenarios with arbitrary conflict graphs. We derive a variety of combinatorial, structural, algorithmical, and complexity theoretical results around this problem.
Introduction: The Anglo-Saxon monk Alcuin (735–804 A.D.) was one of the leading scholars of his time. He served as head of Charlemagne’s Palace School at Aachen, he developed the Carolingian minuscule (a script which has become the basis of the way the letters of the present Roman alphabet are written), and he wrote a number of elementary texts on arithmetic, geometry, and astronomy. His book “Propositiones ad acuendos iuvenes” (Problems to sharpen the young) is perhaps the oldest collection of mathematical problems written in Latin. It contains the following well-known problem.
A man had to transport to the far side of a river a wolf, a goat, and a bundle of cabbages. The only boat he could find was one which would carry only two of them. For that reason he sought a plan which would enable them all to get to the far side unhurt. Let him, who is able, say how it could be possible to transport them safely?
In a safe transportation plan, neither wolf and goat nor goat and cabbage can be left alone together. Alcuin’s river crossing problem differs significantly from other mediaeval puzzles, since it is neither geometrical nor arithmetical but purely combinatorial. Biggs mentions it as one of the oldest combinatorial puzzles in the history of mathematics. Ascher states that the problem also shows up in Gaelic, Danish, Russian, Ethiopian, Suaheli, and Zambian folklore. Borndorfer, Grotschel & Lobel use Alcuin’s problem to provide the reader with a leisurely introduction into integer programming.
Click here to read this article from the Hungarian Academy of Sciences
Related Posts
Subscribe to Medievalverse