Enigmatics |
|
Posted on: Thursday 11/29, 2007; 1:09 PM This Enigma problem can be solved by using a very simple analytic approach which I give at the end of this posting. But first I give a much more flexible approach to illustrate the use of one of the Mathematica packages. Solution 1: Brute force approach using the Combinatorica package Load the Combinatorica package. Define a large enough grid graph size that the solution is contained within it. Build a directed grid graph which allows movement only rightwards and upwards. Note that the starting node is at the bottom-left hand corner. This type of directed structure forces all paths from the bottom left node to each other node to also be shortest paths. Compute the shortest path length from the bottom left corner node to each of the nodes in the graph. Unfortunately, to obtain this result, one has to compute the entire matrix of shortest paths between all pairs of nodes, and then extract the first row. Because of the directed structure of the graph all paths are also shortest paths. Generate a list of distinct shortest path lengths. For each distinct shortest path length generate a list containing the number of distinct paths to each node that has this shortest path length. Extract the two cases where the same number of paths occurs 4 times. Since the solution lies in the quadrant opposite the starting node it must have a relatively large number of paths, so it can be selected by inspection of this result.
Solution 2: Quick approach using the known number of paths in a directed grid graph Compute a table each of whose entries is the number of paths from the top-left node of a directed (rightwards or downwards) grid graph. The three 6-fold paths mentioned in the first part of the problem can be seen in the correct positions in the table (i.e. (1,5), (5,1) and (2,2), where the top-left corner is (0,0)). The 4-times repeated solution(s) found above can be seen elsewhere in the table, and the larger solution lies in the lower right quadrant. |
Blogged from |
||||
