Enigmatics

Enigma 1469

Posted on: Thursday 29/11, 2007;  3:27 PM

Load the Combinatorica package for doing operations on graphs.

"BE3405338857_1.gif"

Derive the formula for triangular numbers.

"BE3405338857_2.gif"

"BE3405338857_3.gif"

Generate a list of triangular numbers less than 1000.

"BE3405338857_4.gif"

"BE3405338857_5.gif"

Split each of the triangular numbers into its constituent digits.

"BE3405338857_6.gif"

"BE3405338857_7.gif"

Compute and display the adjacency matrix for the allowed transitions between numbers.

"BE3405338857_8.gif"

"BE3405338857_9.gif"

Define a function for iterating the adjacency matrix, and normalise its output to bound the size of the matrix elements. This will be used to discover zero rows/columns in the iterated adjacency matrix, which correspond to nodes that do not belong to a cycle.

"BE3405338857_10.gif"

Compute and display the iterated adjacency matrix.

"BE3405338857_11.gif"

"BE3405338857_12.gif"

Delete the triangular numbers that correspond to zero rows in the iterated adjacency matrix, because they do not contribute to the sought after cycle.

"BE3405338857_13.gif"

"BE3405338857_14.gif"

Compute and display the new adjacency matrix, and its iterated form.

"BE3405338857_15.gif"

"BE3405338857_16.gif"

Repeate the above process for zero columns in the new adjacency matrix.

"BE3405338857_17.gif"

"BE3405338857_18.gif"

HamiltonianCycle is not designed to work on directed graphs, so the following step is not strictly valid.

Exhaustively delete all possible 1 or 2 triangular numbers and look for a Hamiltonian cycle in the resulting adjacency matrix.

"BE3405338857_19.gif"

Extract the cases in which a Hamiltonian cycle was found.

"BE3405338857_20.gif"

"BE3405338857_21.gif"

Only the 3rd case is a valid Hamiltonian cycle. Cases 1, 2 and 4 violate the adjacency matrix condition at the end of the cycle (e.g. {3, 7, 8}, {3} cannot be a part of a Hamiltonian cycle because 8≠3). However, HamiltonianCycle is not designed to work on directed graphs, so problems such as this are to be expected.

The correct solution is case 3.

"BE3405338857_22.gif"

"BE3405338857_23.gif"

The number of digits in this cycle is

"BE3405338857_24.gif"

"BE3405338857_25.gif"

This is not actually the solution to the stated problem which asks for the maximum number of digits in the cycle, not the maximum number of triangular numbers in the cycle.

Permalink   Notebook

Recent Posts
21/12, 2007; 4:40 PM:
Enigma 1474
14/12, 2007; 1:36 PM:
Enigma 1473
9/12, 2007; 12:40 PM:
Enigma 1472
2/12, 2007; 11:55 AM:
Enigma 1471
1/12, 2007; 5:33 PM:
Enigma 1467
29/11, 2007; 3:27 PM:
Enigma 1469
29/11, 2007; 2:12 PM:
Enigma 1468
29/11, 2007; 1:09 PM:
Enigma 1465
27/11, 2007; 8:39 PM:
Enigma 1462
27/11, 2007; 8:38 PM:
Enigma 1464
27/11, 2007; 8:35 PM:
Enigma 1463
27/11, 2007; 8:23 PM:
Enigma 1461
27/11, 2007; 8:19 PM:
Enigma 1460
27/11, 2007; 8:14 PM:
Enigma 1459
27/11, 2007; 8:09 PM:
Enigma 1458
27/11, 2007; 7:42 PM:
Welcome

Archive


Links
COMMENTS

 

Blogged from
A WorkLife FrameWork by
Scientific Arts

All material on this website Copyright © 2008, Stephen Luttrell.