PUZZLE: FROG AND THE LOTUS PATH

In the king’s miraculous gardens in Ardapasia, there is a miraculous lake on which, exactly once every year, seven miraculous lotus flowers blossom.

Because they are miraculous, the lotus flowers bloom in an improbably straight and evenly spaced line, as one can see here.

The garden becomes even more miraculous when one learns of the existence of the king’s frog.

When the lotuses bloom, the frog appears, as if out of nowhere, and lands on one of the flowers.

The frog will then start jumping to other lotus flowers, always jumping by either three or five flowers. For instance, if the frog lands on the second lotus, then it might jump from there to the fifth or seventh lotus, and so on.

According to the customs and the everlasting tradition, the frog’s duty and privilege is to first land on a lotus from which it can embark on a journey, proceeding as indicated above, to visit each lotus once and once only.

This means, of course, that the starting point and the finishing point will be different.

Which lotuses can serve as starting points for the king’s frog?

The only lotus flowers the king’s frog can use as a starting point are 3 and 5.

If one connects two lotuses by a line, as below, wherever it is possible for the frog to make a jump that satisfies the above conditions, the path and the two possible starting points become clear.

Indeed, one has connected those numbers that are a distance of three or five apart.

One has thus constructed a graph with vertices 1, 2, …, 7 with edges drawn. A Hamiltonian path in a graph is a way to connect the vertices so that one passes through each vertex exactly once.

The graph above, therefore, consists of a Hamiltonian path: 3–6–1–4–7–2–5. The king’s frog can jump along this path starting at 3 and ending at 5, or the other way around.

A **Hamiltonian path** is a traversal of a (finite) graph that touches each vertex exactly once. If the start and end of the path are neighbors (i.e. share a common edge), the path can be extended to a cycle called a **Hamiltonian cycle**.

**History of the Hamiltonian Cycle**

The Hamiltonian cycle was named after Sir William Rowan Hamilton who, in 1857, invented a puzzle-game which involved hunting for a Hamiltonian cycle. The game, called the Icosian game, was distributed as a dodecahedron graph with a hole at each vertex. To solve the puzzle or win the game one had to use pegs and string to find the Hamiltonian cycle — a closed loop that visited every hole exactly once.

**Applications of Hamiltonian cycles and Graphs**

A search for Hamiltonian cycles isn't just a fun game for the afternoon off. It has real applications in such diverse fields as computer graphics, electronic circuit design, mapping genomes, and operations research.

For instance, when mapping genomes scientists must combine many tiny fragments of genetic code (“reads”, they are called), into one single genomic sequence (a ‘super string’). This can be done by finding a Hamiltonian cycle or Hamiltonian path, where each of the reads are considered nodes in a graph and each overlap (place where the end of one read matches the beginning of another) is considered to be an edge. In a much less complex application of exactly the same math, school districts use Hamiltonian cycles to plan the best route to pick up students from across the district. Here students may be considered nodes, the paths between them edges, and the bus wishes to travel a route that will pass each students house exactly once.