2
$\begingroup$

I've 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 $A$ to point $G$ without going through by the same vertex more than once by traveling only the segments shown and without going through $H$?.

Sketch of the problem

The alternatives given are:

$\begin{array}{ll} 1.&\textrm{11}\\ 2.&\textrm{9}\\ 3.&\textrm{12}\\ 4.&\textrm{10}\\ \end{array}$

Does it exist a way to solve this using a graphic or something? (perhaps this might be the best method for understanding this), is the right approach assigning numbers to each vertex?. There isn't any hint given. What sort of logic should be used here?.

I am not very familiar with combinatorics so if it uses them, perhaps the method which best fit me is one which use multiplication which I think maybe is the way to approach this, but I don't know how. But if combinatorics does make it less complicated it could accompany the answer so I could compare the methods. Can someone help me with this?.

$\endgroup$
2
$\begingroup$

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".)

| improve this answer | |
$\endgroup$
  • $\begingroup$ I am still unable to understand how to do the procedure. Perhaps can you show an example of how to do that?. I mean to account for the possibilities. How would a diagram such as this would look like? $\endgroup$ – Chris Steinbeck Bell Aug 2 at 8:13
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ @hawsic Gee I don't have yet the ability to do a program such as you made. Maybe a better way to do this is to write a flux diagram to understand the logic which is behind the program and the language which it was made into. Perhaps can you add this?. It would help a lot to understand. $\endgroup$ – Chris Steinbeck Bell Aug 2 at 8:11
  • $\begingroup$ I tried to comment the program enough so that someone could get a general idea of what is happening. $\endgroup$ – hawslc Aug 3 at 16:58
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Aside from the spoilers policy on this community which has me in the need to put the pointer over the blank spaces. I'm still confused about how to understand the method from exhaustion. Can you increase the picture quality of your drawings?. Do all your paths cross through all the vertex?. The different colors superimposed over another do not let me to distinguish if they do travel through all the vertex. $\endgroup$ – Chris Steinbeck Bell Aug 2 at 8:20
  • $\begingroup$ By following your first drawing I can see that you account for the paths individually but they do not travel through all the vertex of the graph. But wouldn't this make a transgression to the condition asked?. This is my major confusion. Or is it that they allow skipping some vertex with just the condition of not going through them more than once?. Is that the intended meaning?. $\endgroup$ – Chris Steinbeck Bell Aug 2 at 8:25
  • $\begingroup$ The problem does not require that every vertex is visited. It only requires that no vertex is visited more than once. The colored paths I drew are not quite on the paths only so that the paths can be differentiated. $\endgroup$ – Skylar Aug 2 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.