Maths Puzzle: Froggy went a-courting along a Hamiltonian path

17 Oct 2016

Image: iMoStudio/Shutterstock

Maths can be found in all sorts of surprising places. It can be found in childhood toys, like the Rubik’s cube. It can be found in the smallest snowflake. It can even be found in the completely made up kingdom of Ardapasia.

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.

Maths: Hamilton lotuses

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?

This puzzle is posted in honour of Hamilton Day (16 October), for named Irish physicist, astronomer and mathematician Sir William Rowan Hamilton, who made numerous important contributions to classic mechanics, optics and algebra.

Hamilton Day celebrates Hamilton’s discovery of quaternion algebra, made while walking along the Royal Canal, Dublin, from Dunsink Observatory to the Royal Irish Academy on 16 October 1843. So excited was he by his discovery that he scratched his equation on the wall of Broom Bridge, Cabra.

Scroll down for the solution to this week’s puzzle.

Hamilton: frog on pond

The king’s frog, mulling over its next move. Image: Artur Synenko/Shutterstock

Solution:

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.

Hamiltonian path

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.

This week’s maths puzzle was part of the XVII Lithuanian Mathematics Olympiad, fifth and sixth classes. Secondary school students in Ireland who wish to participate in Olympiads are encouraged to attend free Mathematics Enrichment Programmes organised as part of the Irish Mathematical Olympiad.

Want stories like this and more direct to your inbox? Sign up for Tech Trends, Silicon Republic’s weekly digest of need-to-know tech news.

Kirsty Tobin was careers editor at Silicon Republic

editorial@siliconrepublic.com