Icosian game

Last updated July 02, 2024

The icosian game is a mathematical game invented in 1856 by Irish mathematician William Rowan Hamilton. It involves finding a Hamiltonian cycle on a dodecahedron, a polygon using edges of the dodecahedron that passes through all its vertices. Hamilton's invention of the game came from his studies of symmetry, and from his invention of the icosian calculus, a mathematical system describing the symmetries of the dodecahedron.

Hamilton sold his work to a game manufacturing company, and it was marketed both in the UK and Europe, but it was too easy to become commercially successful. Only a small number of copies of it are known to survive in museums. Although Hamilton was not the first to study Hamiltonian cycles, his work on this game became the origin of the name of Hamiltonian cycles. Several works of recreational mathematics studied his game. Other puzzles based on Hamiltonian cycles are sold as smartphone apps, and mathematicians continue to study combinatorial games based on Hamiltonian cycles.

Game play

A Hamiltonian cycle on a dodecahedron

Planar view of the same cycle

The game's object is to find a three-dimensional polygon made from the edges of a regular dodecahedron, passing exactly once through each vertex of the dodecahedron. A polygon visiting all vertices in this way is now called a Hamiltonian cycle.) In a two-player version of the game, one player starts by choosing five consecutive vertices along the polygon, and the other player must complete the polygon.^[1]

Édouard Lucas describes the shape of any possible solution, in a way that can be remembered by game players. A completed polygon must cut the twelve faces of the dodecahedron into two strips of six pentagons. As this strip passes through each of its four middle pentagons, in turn, it connects through two edges of each pentagon that are not adjacent, making either a shallow left turn or a shallow right turn through the pentagon. In this way, the strip makes two left turns and then two right turns, or vice versa.^[2]

One version of the game took the form of a flat wooden board inscribed with a planar graph with the same combinatorial structure as the dodecahedron (a Schlegel diagram),^[3] with holes for numbered pegs to be placed at its vertices. The polygon found by game players was indicated by the consecutive numbering of the pegs.^[4]^[5] Another version was shaped as a "partially flattened dodecahedron", a roughly hemispherical dome with the pentagons of a dodecahedron spread on its curved surface and a handle attached to its flat base. The vertices had fixed pegs. A separate string, with a loop at one end, was wound through these pegs to indicate the polygon.^[5]

The game was too easy to play to achieve much popularity,^[6]^[7]^[8] although Hamilton tried to counter this impression by giving an example of an academic colleague who failed to solve it.^[8] David Darling suggests that Hamilton may have made it much more difficult for himself than for others, by using his theoretical methods to solve it instead of trial and error.^[6]

Background

At the time of his invention of the icosian game, William Rowan Hamilton was the Andrews Professor of Astronomy at Trinity College Dublin and Royal Astronomer of Ireland, and was already famous for his work on Hamiltonian mechanics and his invention of quaternions.^[9] The motivation for Hamilton was the problem of understanding the symmetries of the dodecahedron and icosahedron, two dual polyhedra that have the same symmetries as each other. For this purpose he also invented icosian calculus, a system of non-commutative algebra which he used to compute these symmetries.^[10]

The name of the icosian game comes from the fact that the icosahedron has twenty faces, the dodecahedron has twenty vertices, and any polygon through all the vertices of the dodecahedron has twenty edges. Icosa is a Greek root meaning twenty.^[7]^[11] On a dodecahedron with labeled vertices, there are 30 different ways that these vertices could be connected to each other to form a Hamiltonian cycle. However, without the labels, all Hamiltonian cycles are symmetric to each other under rotations and reflections of the dodecahedron.^[12]

History

Both the icosian calculus and the icosian game were outlined by Hamilton in a series of letters to his friend John T. Graves in late 1856.^[10] Hamilton then exhibited the game at the 1857 Dublin meeting of the British Association for the Advancement of Science.^[13]^[14] At the suggestion of Graves,^[3] Hamilton sold its publishing rights to Jaques and Son, a London-based toy and game manufacturing company.^[10]^[13]

This company marketed Hamilton's game beginning in 1859,^[4] in both its handheld solid and flat forms,^[5] under the lengthy titles The Travellers Dodecahedron, or a voyage around the world, and (respectively) The Icosian Game, invented by Sir William Rowan Hamilton, Royal Astronomer of Ireland; forming a new and highly amusing game for the drawing room, particularly interesting to students in mathematics of illustrating the principles of the Icosian Calculus.^[4]

Several versions of the game were sold in Europe.^[12] However, it was not a commercial success.^[6]^[7]^[10] Hamilton received only a £25 licensing fee from Jaques and Son for his invention (present value £3200).^[12] Few original copies of the game are known to survive,^[15] but one is kept in the library of the Royal Irish Academy in Dublin,^[4] and another is included in the collection of the Conservatoire national des arts et métiers in Paris,^[3] both in the flat form of the game.^[3]^[4]

Legacy

Although Hamilton invented the icosian game independently, he was not the first to study Hamiltonian cycles. Knight's tours on chessboards, another puzzle based on Hamiltonian cycles, go back to the 9th century, both in India and in mathematics in the medieval Islamic world.^[16] At about the same time as Hamilton, Thomas Kirkman in England was also studying Hamiltonian cycles on polyhedra.^[17] Hamilton visited Kirkman in 1861, and presented him with a copy of the icosian game.^[10] Despite this related work, some of which was much earlier, Hamiltonian cycles came to be named for Hamilton and for his work on the icosian game.^[1]

The icosian game itself has been the topic of multiple works in recreational mathematics by well-known authors on the subject including Édouard Lucas,^[2] Wilhelm Ahrens,^[18] and Martin Gardner.^[12] Puzzles like Hamilton's icosian game, based on finding Hamiltonian cycles in planar graphs, continue to be sold as smartphone apps.^[19] Maker-Breaker games based on Hamiltonian cycles were introduced to combinatorial game theory in a 1978 paper by Václav Chvátal and Paul Erdős,^[20]^[21] and continue to be studied in mathematics.^[21]

Related Research Articles

<span class="mw-page-title-main">Regular icosahedron</span> Polyhedron with 20 regular triangular faces

In geometry, the regular icosahedron is a convex polyhedron that can be constructed from pentagonal antiprism by attaching two pentagonal pyramids with regular faces to each of its pentagonal faces, or by putting points onto the cube. The resulting polyhedron has 20 equilateral triangles as its faces, 30 edges, and 12 vertices. It is an example of the Platonic solid and of the deltahedron. The icosahedral graph represents the skeleton of a regular icosahedron.

<span class="mw-page-title-main">Icosidodecahedron</span> Archimedean solid with 32 faces

In geometry, an icosidodecahedron or pentagonal gyrobirotunda is a polyhedron with twenty (icosi) triangular faces and twelve (dodeca) pentagonal faces. An icosidodecahedron has 30 identical vertices, with two triangles and two pentagons meeting at each, and 60 identical edges, each separating a triangle from a pentagon. As such, it is one of the Archimedean solids and more particularly, a quasiregular polyhedron.

In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle through all its vertices". It was proposed by P. G. Tait and disproved by W. T. Tutte, who constructed a counterexample with 25 faces, 69 edges and 46 vertices. Several smaller counterexamples, with 21 faces, 57 edges and 38 vertices, were later proved minimal by Holton & McKay (1988). The condition that the graph be 3-regular is necessary due to polyhedra such as the rhombic dodecahedron, which forms a bipartite graph with six degree-four vertices on one side and eight degree-three vertices on the other side; because any Hamiltonian cycle would have to alternate between the two sides of the bipartition, but they have unequal numbers of vertices, the rhombic dodecahedron is not Hamiltonian.

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete; see Hamiltonian path problem for details.

The icosian calculus is a non-commutative algebraic structure discovered by the Irish mathematician William Rowan Hamilton in 1856. In modern terms, he gave a group presentation of the icosahedral rotation group by generators and relations.

<span class="mw-page-title-main">Truncated dodecahedron</span> Archimedean solid with 32 faces

In geometry, the truncated dodecahedron is an Archimedean solid. It has 12 regular decagonal faces, 20 regular triangular faces, 60 vertices and 90 edges.

In mathematics, combinatorial group theory is the theory of free groups, and the concept of a presentation of a group by generators and relations. It is much used in geometric topology, the fundamental group of a simplicial complex having in a natural and geometric way such a presentation. A very closely related topic is geometric group theory, which today largely subsumes combinatorial group theory, using techniques from outside combinatorics besides.

Ore's theorem is a result in graph theory proved in 1960 by Norwegian mathematician Øystein Ore. It gives a sufficient condition for a graph to be Hamiltonian, essentially stating that a graph with sufficiently many edges must contain a Hamilton cycle. Specifically, the theorem considers the sum of the degrees of pairs of non-adjacent vertices: if every such pair has a sum that at least equals the total number of vertices in the graph, then the graph is Hamiltonian.

In the mathematical field of graph theory, a quartic graph is a graph where all vertices have degree 4. In other words, a quartic graph is a 4-regular graph.

<span class="mw-page-title-main">Regular dodecahedron</span> Polyhedron with 12 regular pentagonal faces

A regular dodecahedron or pentagonal dodecahedron is a dodecahedron that is regular, which is composed of 12 regular pentagonal faces, three meeting at each vertex. It is one of the five Platonic solids. It has 12 faces, 20 vertices, 30 edges, and 160 diagonals. It is represented by the Schläfli symbol {5,3}.

In graph theory, toughness is a measure of the connectivity of a graph. A graph $G$ is said to be $t$ -tough for a given real number $t$ if, for every integer $k > 1$ , $G$ cannot be split into $k$ different connected components by the removal of fewer than $tk$ vertices. For instance, a graph is $1$ -tough if the number of components formed by removing a set of vertices is always at most as large as the number of removed vertices. The toughness of a graph is the maximum $t$ for which it is $t$ -tough; this is a finite number for all finite graphs except the complete graphs, which by convention have infinite toughness.

Václav (Vašek) Chvátal is a Professor Emeritus in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Quebec, Canada, and a visiting professor at Charles University in Prague. He has published extensively on topics in graph theory, combinatorics, and combinatorial optimization.

In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.

In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph. The generalized Petersen graph family was introduced in 1950 by H. S. M. Coxeter and was given its name in 1969 by Mark Watkins.

In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs. In the undirected case a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected.

In graph theory, a branch of mathematics, the Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges. It is a polyhedral graph, and is the smallest polyhedral graph that does not have a Hamiltonian cycle, a cycle passing through all its vertices. It is named after British astronomer Alexander Stewart Herschel, because of Herschel's studies of Hamiltonian cycles in polyhedral graphs.

In geometry, an enneahedron is a polyhedron with nine faces. There are 2606 types of convex enneahedron, each having a different pattern of vertex, edge, and face connections. None of them are regular.

In graph theory, a branch of mathematics, Fleischner's theorem gives a sufficient condition for a graph to contain a Hamiltonian cycle. It states that, if $is a 2-vertex-connected graph, then the square of is Hamiltonian. It is named after Herbert Fleischner, who published its proof in 1974.$

In the mathematical field of graph theory, the 26-fullerene graph is a polyhedral graph with V = 26 vertices and E = 39 edges. Its planar embedding has three hexagonal faces and twelve pentagonal faces. As a planar graph with only pentagonal and hexagonal faces, meeting in three faces per vertex, this graph is a fullerene. The existence of this fullerene has been known since at least 1968.

References

1 2 Bondy, J. A.; Murty, U. S. R. (1976), Graph Theory with Applications, North Holland, p. 53, ISBN 0-444-19451-7
1 2 Lucas, Édouard (1883), "Septième récréation – le jeu d'Hamilton", Récréations mathématiques (in French), vol. 2, Paris: Gauthier-Villars, pp. 201–227
1 2 3 4 Boutin, Michel (April 2018), "Les jeux dans les collections du Conservatoire national des arts et métiers de Paris, 1 – le Jeu icosien (1859) (1re partie)" (PDF), Bulletin de la Société archéologique, historique et artistique le Vieux papier (in French) (428): 433–441, archived (PDF) from the original on 2024-04-26, retrieved 2024-04-25
1 2 3 4 5 Turner, Gerard L'E. (October 1987), "Scientific toys", Presidential address, The British Journal for the History of Science , 20 (4): 377–398, doi:10.1017/s0007087400024195, JSTOR 4026415 ; see p. 395 and photo, Fig. 13, p. 397
1 2 3 Applegate, David L.; Bixby, Robert E.; Chvátal, Vašek; Cook, William J. (2011), The Traveling Salesman Problem: A Computational Study (PDF), Princeton Series in Applied Mathematics, vol. 17, Princeton University Press, pp. 18–20, ISBN 9781400841103, archived (PDF) from the original on 2021-05-06, retrieved 2024-04-25
1 2 3 Darling, David, "Icosian game", Encyclopedia of Science, archived from the original on 2024-04-25, retrieved 2024-04-24
1 2 3 Sowell, Katye O. (2001), "Hamilton's icosian calculus and his icosian game", Humanistic Mathematics Network Journal, 1 (24), Article 14, doi:10.5642/hmnj.200101.24.14, archived from the original on 2024-03-11, retrieved 2024-04-25
1 2 Graves, Robert Perceval (1889), "The Icosian Game", Life of Sir William Rowan Hamilton, vol. 3, Hodges, Figgis, & Co., and Longman's, Green, & Co., pp. 55–56
↑ Mukunda, N. (June 2016), "Sir William Rowan Hamilton: Life, achievements, stature in physics", Resonance, 21 (6): 493–510, doi:10.1007/s12045-016-0356-y
1 2 3 4 5 Biggs, Norman (1995), "The icosian calculus of today", Proceedings of the Royal Irish Academy , 95: 23–34, JSTOR 20490184, MR 1649815
↑ Borkar, Vivek S.; Ejov, Vladimir; Filar, Jerzy A.; Nguyen, Giang T. (2012), "1.1: The graph that started it all", Hamiltonian Cycle Problem and Markov Chains, International Series in Operations Research & Management Science, New York: Springer, pp. 3–4, doi:10.1007/978-1-4614-3232-6, ISBN 9781461432326
1 2 3 4 Gardner, Martin (May 1957), "Mathematical Games: About the remarkable similarity between the Icosian Game and the Tower of Hanoi", Scientific American , vol. 196, no. 5, JSTOR 24940862
1 2 Barnett, Janet Heine (2009), "Early Writings on Graph Theory: Hamiltonian Circuits and The Icosian Game", in Hopkins, Brian (ed.), Resources for Teaching Discrete Mathematics: Classroom Projects, History Modules, and Articles, Mathematical Association of America, pp. 217–224, doi:10.5948/upo9780883859742.028, ISBN 978-0-88385-974-2, archived from the original on 2024-04-25, retrieved 2024-04-25
↑ Hamilton, W. R. (1858), "On the icosian calculus", Report of the Twenty-Seventh Meeting of the British Association for the Advancement of Science, London: John Murray, p. 3, archived from the original on 2024-04-25, retrieved 2024-04-25– via Hathitrust
↑ Dalgety, James (July 2002), "The Icosian Game", The Puzzle Museum, archived from the original on 2024-01-21, retrieved 2024-04-25; includes color photographs of both original versions
↑ Watkins, John J. (2004), "Chapter 2: Knight's Tours", Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, pp. 25–38, ISBN 978-0-691-15498-5 .
↑ Biggs, N. L. (1981), "T. P. Kirkman, mathematician", The Bulletin of the London Mathematical Society , 13 (2): 97–120, doi:10.1112/blms/13.2.97, MR 0608093 .
↑ Ahrens, Wilhelm (1918), "XVII: Das Hamiltonische Dodekaederspiel", Mathematische Unterhaltungen und Spiele (in German), vol. 2, Leipzig: B. G. Teubner, pp. 196–210
↑ Fernau, Henning; Haase, Carolina; Hoffmann, Stefan (2022), "The synchronization game on subclasses of automata", in Fraigniaud, Pierre; Uno, Yushi (eds.), 11th International Conference on Fun with Algorithms, FUN 2022, May 30 to June 3, 2022, Island of Favignana, Sicily, Italy, LIPIcs, vol. 226, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 14:1–14:17, doi:10.4230/LIPICS.FUN.2022.14
↑ Chvátal, V.; Erdős, P. (1978), "Biased positional games" (PDF), Annals of Discrete Mathematics, 2: 221–229, doi:10.1016/S0167-5060(08)70335-2, MR 0500701
1 2 Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš; Szabó, Tibor (2014), "Chapter 6: The Hamiltonicity game", Positional Games, Oberwolfach Seminars, vol. 44, Basel: Birkhäuser / Springer, pp. 75–84, doi:10.1007/978-3-0348-0825-5_6, ISBN 978-3-0348-0824-8, MR 3524719