Different ways to go from one point to another

Question

I found this problem in my book "Riddles and Reason" and after several attempts I still have no idea how to tackle it.

The problem is as follows:

The figure from below shows a truncated pyramid. How different ways can you go from from point 𝐴 to point 𝐺 without going through by the same vertex more than once by traveling only the segments shown and without going through 𝐻?

The choices given are:

1. 11
2. 9
3. 12
4. 10

Does a way to solve this with a graphic exist? Is assigning numbers to each vertex the right approach? There isn't any hint given. What sort of logic should be used here?

I am not very familiar with combinatorics. The method that should work best for me uses multiplication, but I can't figure out how to do so. If combinatorics simplifies this problem, include it alongside another solution so I can compare methods.

Answer 1

I don't think there's anything super-clever you can do. The important thing is to be systematic so you know you aren't missing any possibilities. The overall approach I would take is a "depth-first search".

1. Draw the network of vertices and edges on a piece of paper. Leave out H which you aren't allowed to use. Give names to all the vertices -- might as well be A through G since there are the right number of vertices for that.

2. Now just enumerate possible paths in alphabetical order. To do this, start at A, try each of its three neighbours in alphabetical order, and for each of those ... enumerate possible paths from there to G, in alphabetical order.

If you're good at keeping track of things in your head, you can do it mentally. If not, do it on paper.

(In general, "find an ordering and then enumerate things in increasing order according to that ordering" is a useful tactic for counting things systematically without missing any. So is "depth-first search", i.e., "once you find a solution, look next for a solution that has as much as possible of its beginning the same as that one".)

Answer 2

I wrote a program to do this and it gave me the answer of 11

static void Test()
    {
        int[][] numbers = new int[8][];

        //numbers[1] will contain all of the points connected to point 1
        //numbers[2] will contain all of the points connected to point 2
        //and so on...


        numbers[1] = new int[]{2, 3, 4}; // A
        numbers[2] = new int[]{1, 5};
        numbers[3] = new int[]{1, 5, 6};
        numbers[4] = new int[]{1, 5, 6};
        numbers[5] = new int[]{2, 3, 4, 7};
        numbers[6] = new int[]{3, 4, 7};
        numbers[7] = new int[]{5, 6}; // G
        

        int currentSpot = 1;
        bool[] visited = new bool[8];

        List<int[]> sequences = new List<int[]>(); //contains a list of the previous sequences

        for (int i = 0; i < 1000000; i++) //repeat 1 million times
        {
            Array.Clear(visited, 0, visited.Length); //make it so that no points have been visited

            currentSpot = 1; //start at point 1

            List<int> chain = new List<int>(); //will store all the numbers of spots that have been visited

            chain.Add(1); //mark point 1 as visited
            visited[1] = true;

            while(true)
            {
                int r = random.Next(0, numbers[currentSpot].Length); //generate a random point that is linked to current point

                currentSpot = numbers[currentSpot][r]; //move to a random point that is linked to current point
                chain.Add(currentSpot); //add this to the chain

                if (visited[currentSpot] == true) break; //if already visited point, break
                visited[currentSpot] = true; //mark current point as visited

                if (currentSpot == 7)
                {
                    bool work = true;

                    for (int k = 0; k < sequences.Count; k++)
                    {
                        if (sequences[k].SequenceEqual(chain.ToArray())) work = false; //check if the current sequence has already been found
                    }

                    if (work)
                    {
                        // if the sequence is a new way to get to 7, then add it to the list of sequences
                        sequences.Add(chain.ToArray());
                    }

                    break;
                }
            }
        }

        Console.WriteLine(sequences.Count); // prints the number of unique paths found
        clock.Stop();
        Console.WriteLine("Solving time is " + clock.Elapsed.TotalMilliseconds + " ms");
    }

One thing you might have noticed is that I completely disregarded point H and all of its connections to other points.

Answer 3

Picture-driven Explanation

Answer:

11

Explanation:

You can draw the figure as the following 2-dimensional graph:

Note: The location labeled $X$ is meant to represent two edges going through each other, not an intersection.

Since vertex $H$ cannot be used, it and the edges that connect to it can be removed, making the graph planar (no crossing edges):

The two edges on the left can be combined into one to simplify the graph a bit:

Now, we can find all paths by exhaustion. Starting with paths that begin going up from vertex $A$, we have the following three paths:

For paths that start going diagonally up and right from vertex $A$, there are four paths:

Finally, for paths that start going right from vertex $A$, there are four paths, shown across two pictures:

The total number of paths is 11. Any other paths violate the conditions set forth by the problem.