Hamiltonian Paths Revisited

On the 6th February 2021, I posted about Hamiltonian Paths and Knight's Tours. That was over two years ago now but today I have the opportunity to revisit the topic of Hamiltonian paths because the number associated with my diurnal age, 26996, is a member of OEIS A003778:

A003778

Number of Hamiltonian paths in \(P_5 \times P_n \).

In the case of 26996, \(n=6\).  Figure 1 shows such a \(5 \times 6 \) grid.

Figure 1

A Hamiltonian path is one that passes through every vertex exactly once. One example of such a path is shown in Figure 2. Note that in this 2D grid connections between vertices or nodes are made up-down and left-right but not diagonally.

Figure 2

In the case of a \(5 \times 6\) grid, there are 26996 such paths that can be drawn. The number of paths increases rapidly as the number of points increases. Here are the initial values:

• \(5 \times 1 \rightarrow 1\)
• \(5 \times 2 \rightarrow 22\)
• \(5 \times 3 \rightarrow 132\)
• \(5 \times 4 \rightarrow 1006\)
• \(5 \times 5 \rightarrow  4324\)
• \(5 \times 6 \rightarrow 26996\)
• \(5 \times 7 \rightarrow  109722\)
• \(5 \times 8 \rightarrow 602804\)
• \(5 \times 9 \rightarrow 2434670\) 
• \(5 \times 10 \rightarrow 12287118\)

Here is a permalink to some Python code that will plot a Hamiltonian path through a grid of specified size. Figure 3 shows the output in the case of a \(5 \times 6\) grid:

[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 5), (1, 4), (1, 3), (1, 2), (1, 1), (1, 0), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 5), (3, 4), (3, 3), (3, 2), (3, 1), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5)]

Figure 3

This YouTube video does a good job of explaining in simple terms the difference between a Hamiltonian path and an Euler path. For the latter, the path must traverse every edge exactly once whereas in the former it is every vertex that must be traversed.

There is a 36-term linear recurrence mentioned in the OEIS A003778 comments which is the closest thing to a formula that seems to be available for calculating the number of possible paths. Hamiltonian paths and cycles are intimately connected with the travelling salesman problem as this site explains:

Travelling Salesman Problem (TSP): 

Given a set of cities and the distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point. Note the difference between Hamiltonian Cycle and TSP. The Hamiltonian cycle problem is to find if there exists a tour that visits every city exactly once. Here we know that Hamiltonian Tour exists (because the graph is complete) and in fact, many such tours exist, the problem is to find a minimum weight Hamiltonian Cycle. 

Figure 4

For example, consider the graph shown in the Figure 4 on the right side. A TSP tour in the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80. The problem is a famous NP-hard problem. There is no polynomial-time know solution for this problem. 

The site goes to provide programming solutions to this particular instance of the TSP but the Python3 solution doesn't work. However, the minimum cost Hamiltonian tour is  80 and 1-2-4-3-1 is one solution. This YouTube video offers a useful tutorial on how to draw graphs, such as the one shown in Figure 3, using SageMath.

I discovered an interesting site called Graph Online that allows you to create graphs and find Hamiltonian and Eulerian paths and cycles as well as Adjacency and Incidence Matrices. Figure 5 shows the Hamiltonian path that it came up with for the graph that I drew. No Hamiltonian cycle is possible.

Figure 5

Figure 6 shows a Eulerian path. No Eulerian cycle is possible. The site will display and analyse many other types of graphs. I've just focused on two here.

Figure 6

Digitally Distinct (2D) and Doubly Digitally Distinct (3D) Numbers

A Digitally Distinct Number or 2D number is a term that I concocted to describe a number that has:

• no repeated digits  
• an additive digital root that is different to any of its digits

The number associated with my diurnal age today, 26870, is one such number since it clearly has no repeated digits and its additive digital root is 5.

The numbers 0 to 9 do not qualify because they are identical to their additive digital roots. However, 12 has an additive digital root of 3 and thus it is the first 2D number and begins a run of seven consecutive such numbers viz. 12, 13, 14, 15, 16, 17 and 18. The percentage of such numbers declines with their size. Here is a summary:

• 0 -10 0.00%
• 0 - 100 56.0%
• 0 - 1000 50.4%
• 0 - 10000 31.0%
• 0 - 100000 16.2%
• 0 - 1000000 6.99%

Once a number has more than nine digits, it cannot be a 2D number because at least one digit would then repeat. The upper limit must be below 987,654,320, a number that has an additive digital root of 8 and is thus not a 2D number. I excluded 987,654,321 because additive digital roots lie between 1 and 9 and all those digits are taken. The question that must be asked is what is the largest 2D number? It can contain no more than nine digits and one of those must be zero. Testing revealed that:

• no nine digit number containing the digit 9 can be a 2D number
• 876,543,210 qualifies as a 2D number since it has a digital root of 9

So it is that 876,543,210 is the largest 2D number although all of the 8 x 8! = 322,560 (leading zeros not allowed) possible permutations are of course 2D numbers.

In the range between 26500 and 27000, the percentage of 2D numbers is 17.2%. The numbers are (with my diurnal age shown in bold):

26503, 26504, 26508, 26509, 26513, 26514, 26517, 26518, 26530, 26531, 26539, 26540, 26541, 26548, 26549, 26571, 26578, 26580, 26581, 26584, 26587, 26589, 26590, 26593, 26594, 26598, 26703, 26704, 26708, 26715, 26730, 26740, 26748, 26749, 26751, 26758, 26780, 26784, 26785, 26789, 26794, 26798, 26803, 26805, 26807, 26809, 26814, 26815, 26830, 26834, 26839, 26841, 26843, 26845, 26847, 26850, 26851, 26854, 26857, 26859, 26870, 26874, 26875, 26879, 26890, 26893, 26895, 26897, 26904, 26905, 26908, 26935, 26938, 26940, 26945, 26947, 26950, 26953, 26954, 26958, 26974, 26978, 26980, 26983, 26985, 26987

Here is a permalink to the algorithm that I used to generate these numbers. 

An interesting extension is to consider the multiplicative digital root which is the single digit reached when multiplying the digits of the number together (the results can range from 0 to 9). I've concocted the term Doubly Digitally Distinct or 3D for numbers that satisfy the following criteria:

• no repeated digits
• an arithmetic digital root that is different to any of its digits
• a multiplicative digital root that is different to any of its digits and also to the arithmetic digital root

Applying these criteria to the same range of numbers as earlier (26500 to 27000), we find 11.6% of numbers satisfy. These are:

26513, 26514, 26517, 26518, 26531, 26539, 26541, 26548, 26549, 26571, 26578, 26581, 26584, 26587, 26589, 26593, 26594, 26598, 26715, 26748, 26749, 26751, 26758, 26784, 26785, 26789, 26794, 26798, 26814, 26815, 26834, 26839, 26841, 26843, 26845, 26847, 26851, 26854, 26857, 26859, 26874, 26875, 26879, 26893, 26895, 26897, 26935, 26938, 26945, 26947, 26953, 26954, 26958, 26974, 26978, 26983, 26985, 26987

The number 26870 does not qualify as a 3D number because its multiplicative digital root is 0 and that is one of the digits of the number. In fact, any number containing a zero cannot be a 3D number. However, the nearby 26874 and 26875 both qualify as they have additive digital roots of 9 and 1 respectively and multiplicative digital roots of 0. A similar table to that shown above but this time for 3D numbers looks like this.

• 0 -10  0.00%
• 0 - 100 33.0%
• 0 - 1000  26.7%
• 0 - 10000 14.9%
• 0 - 100000 7.61%
• 0 - 1000000 2.78%

Here is a permalink that can be used to generate the statistics in this table. The first 3D number is 23 and it begins a run of three consecutive such numbers: 23, 24 and 25. We see that:

• 23 has an additive digital root of 5 and a multiplicative digital root of 6
• 24 has an additive digital root of 6 and a multiplicative digital root of 8
• 25 has an additive digital root of 7 and a multiplicative digital root of 0

However, the next number 26 has an additive digital root of 8 and a multiplicative digital root of 2 which is one of the digits of the original number. Thus it does not meet the criteria. The question remains as to what is the largest 3D number. It cannot contain more than eight distinct digits. Testing revealed that:

• no eight digit number containing the digit 9 is a 3D number
• 87,654,321 qualifies as a 3D number
• It has a arithmetic digital root of 9
• it has a multiplicative digital root of 0

So 87,654,321 is the largest 3D number although any of the 8! = 40,320 permutations of those digits will also be a 3D number.

ADDENDUM 

October 30th 2020

It occurred to me that it would also be interesting to look at the "complement" of 2D and 3D numbers. The complement of 2D numbers I will define as numbers that have at least one repeated digit and whose arithmetic digital root is one of the digits of the number. The complement of 3D numbers I will define as numbers that have at least one repeated digit and whose arithmetical digital root and multiplicative digital roots are digits of the number.

Here is a permalink to an algorithm that will identify complementary 3D numbers in the range up to 40,000. I have also made an entry in my Bespoken For Sequences. Such numbers comprise 8.01% of the range. Here are the initial members: 0, 100, 118, 181, 188, 200, 299, 300, 400, 500, 600, 700, 800, 811, 818, 881, 899, 900, 909, 929, 989, 990, 992, 998, 1000.

Numbers like 1000 clearly qualify for membership so let's take the less obvious 998. The number has one repeated digit (9) and its arithmetic digital root is 8 while its multiplicative digital root is also 8. Thus it qualifies too. Clearly such complementary 2D and 3D numbers have no upper bound unlike the 2D and 3D numbers themselves. 

A Spider-Fly Problem with a Surprising Solution

I’ve long been familiar with the spider and fly problem and its solution. Although, after reading this article, I realised that I had been focused on an incorrect solution. This was indeed surprising to realise that I’d been deluded all these years. The problem can be stated as follows: a spider and a fly are on opposite walls of a 30 × 12 × 12 meter room. The spider is 1 meter above the floor, the fly is 1 meter below the ceiling. They are both 6 meters from adjacent walls, as shown in Figure 1. If the fly does not move, what is the shortest distance the spider can crawl to reach it?

Figure 1

A sensible first attempt would be to travel straight up (or down) and across. For example, straight up the spider’s wall (11 meters), along the roof (30 meters) and down to the fly (1 meter). See Figure 2. This gives a total distance of 42 meters.

Figure 2

What I believed to be the shortest path is shown in Figure 3 and it is clearly not the shortest path!

Figure 3

In fact the shortest path requires the spider to cross five of the six internal surfaces and this is shown in Figure 4. The shortest path can be seen to be 40 metres.

Figure 4

The site from which this information is taken has some nice animated gifs of the rectangular prism’s unfolding, so the reader is encouraged to visit. The author of the article is Russell Lim, a high school teacher in Melbourne.

Dali and the Unfolded Hypercube

Figure 1

In April of 1984, as a birthday present from my father, I acquired a TR-80 computer from Tandy with 32Kb of RAM and a keyboard but no disk drive. Data input and output were via a cassette tape. Display was via a connected TV. Using this I began my BASIC programming and one of my first creations was a simulation of a projectile being launched to hit a target. The essential formulae for the projectile's motion are:$$x(t)=v_0 \cos(\theta) \cdot t \text{ and } y(t)=v_0 \sin(\theta) \cdot t - 0.5 g t^2$$where we have:

• \(x(t)\) is horizontal position of projectile after time \(t\) with \(x=0\) when \(t=0\)
• \(y(t)\) is vertical position of projectile after time \(t\) with \(y=0\) when \(t=0\)
• \(v_0\) is initial velocity at time \(t=0\)
• \(\theta\) is angle of projection
• \(g\) is deceleration due to gravity \(\approx \) -9.8 \(ms^{-2}\)

Figure 1 shows the situation with an angle of 60° and an initial velocity fo 6 \(ms^{-1}\). What has all this to do with unfolding hypercubes? Well, April of 1984 marked my return to Mathematics after a long absence. In August of that year, I began my training as a Mathematics teacher and one of the assigned projects was an assignment on some aspect of Mathematics. I chose Mathematics and Art, a choice which led to me to the unfolded hypercube. In the University library, I came across Salvator Dali's 1954 Crucifixion (Corpus Hypercubus). See Figure 2.

Figure 2: source

It is a large oil painting, with dimensions of 194.3 cm × 123.8 cm (76.5 in × 48.7 in). Figure 3 shows the net of a hypercube (or tesseract).

Figure 3: source

What reminded me of my youthful investigation into the realm of the hypercube was a Mathologer video that I watched today titled The Iron Man hyperspace formula really works.

Figure 4 shows a screenshot that demonstrates information about the number of vertices, edges and faces in an \(n\)-dimensional cube where \(n\) varies from 0 to 4. Looking at it, we see that a zero dimensional "cube" consists of only a single point or vertex. The number of vertices is shown by the coefficients of the \(x^0\) terms, coloured red. A one dimensional "cube", corresponding to a line, has two vertices and one edge. The number of edges is shown by the coefficients of the \(x^1\) terms, coloured green. A two dimensional "cube", corresponding to a square, has four vertices, 4 edges and one face. The number of faces is shown by the coefficients of the \(x^2\) terms. The familiar three dimensional cube has 8 vertices, 12 edges and 6 faces, plus one cube. The number of cubes is shown by the coefficients of the \(x^3\) terms. The four dimensional hypercube has 16 vertices, 32 edges, 24 faces, 8 cubes and one hypercube. The vertices, edges, faces and cubes can be counted using the net shown in Figure 2.

Figure 4: source

Figure 5 shows another screenshot where a more general version of Euler's polyhedron formula is displayed. It begins with one dimension where a line of finite length does indeed have two end points or vertices. Thus V=2. For two dimensions, the number of vertices equals the number of edges e.g. consider a square. Thus V=E. For three dimensions, we have the familiar V-E+F=2 and for the hypercube we have V-E+F-C=0 because as can be seen in Figure 4, V=16, E=32, F=24 and C=8.

Figure 5: source

However, getting back to Dali's hypercube, I just finished watching an interesting talk about Dali from an American mathematician who met the artist on a number of occasions. The video is titled Math Encounters -- Encountering Salvador Dali in the Fourth Dimension. 

The video was uploaded in March of 2014 and the mathematician, Tom Banchoff, is still alive and now aged 83. He born on April 7th 1938. He has written a book, titled Beyond the Third Dimension Geometry, Computer Graphics, and Higher Dimensions, a digital copy of which I've managed to acquire. It was first published in 1990. The cover is shown in Figure 6.

Figure 6

The author makes mention of his book in this talk and mentions also Flatland which is a classic that I remember reading many years ago but exactly when I can't recall. Here is a little more about this 1884 book:

This masterpiece of science (and mathematical) fiction is a delightfully unique and highly entertaining satire that has charmed readers for more than 100 years. The work of English clergyman, educator and Shakespearean scholar Edwin A. Abbott (1838-1926), it describes the journeys of A. Square, a mathematician and resident of the two-dimensional Flatland, where women-thin, straight lines-are the lowliest of shapes, and where men may have any number of sides, depending on their social status. 

Through strange occurrences that bring him into contact with a host of geometric forms, Square has adventures in Spaceland (three dimensions), Lineland (one dimension) and Pointland (no dimensions) and ultimately entertains thoughts of visiting a land of four dimensions—a revolutionary idea for which he is returned to his two-dimensional world. Charmingly illustrated by the author, Flatland is not only fascinating reading, it is still a first-rate fictional introduction to the concept of the multiple dimensions of space. "Instructive, entertaining, and stimulating to the imagination." — Mathematics Teacher.

Figure 7 shows the frontispiece to the original publication. Dali was probably familiar with this book as he was very interested in such dimensional adventures. 

Figure 7

Speaking of Flatland's two dimensions, what would a hypercube look like in Flatland? One way it could appear is shown in Figure 8. I got this image from an interesting web page about hypercubes.

Figure 8: source

Figure 9 gives a clearer idea of why this is so. The shadow of the tesseract, itself the 3D shadow of the hypercube, is shown falling on a two dimensional surface.

Figure 9: source

To end this post, I'll return to Mathologer and his YouTube channel. In July of 2017, he posted an interesting video about hypercube shadows that's well worth a look.