My attempt at Question 19 from the Haselbauer-Dickheiser Test

The Haselbauer-Dickheiser Test can be found at http://matrix67.com/iqtest/.

In this blog post, I will study Question 19 from this test.

The question is about giving numerical values to symbols, so that the given equations hold.

Below I present the original question for your convenience:

Please do not read the rest of this article, if you want to attempt to solve this question on your own. The rest of this article describes my attempt at solving this question and you should not read it, unless you want to or you do not mind coming across relevant ideas, spoilers, hints, solutions, and strong opinions concerning this test.

You have been warned and I now consider that you continue to read knowing that what you come across for the rest of this article may forever spoil things for you and/or present strong opinions against this test.

Last warning: please do not read this blog post, unless you are certain that you know what you are doing. If you are not sure, then it would be best if you stopped reading at this point.

OK. If you are here, it means that you want to know my opinion. Well, ok then!

To cut a long story short, my opinion is that the test is highly inappropriate. In this blog post, I will focus on the study of question 19.

This is not a bad question, but I fail to see what it has to do with a test that measures intelligence. It is easy for someone to do some trial and error attempts in order to find the solution. I suppose the test had to had an easy question to tackle. But there are some sinister things going on concerning this question and I am about to bring them forth.

But first, let me provide the answer.

This is a nice question that allows the solver to draw in a piece of paper and try out things and make different attempts. But I do not know how the test was administered. You will shortly understand why I am saying this. This question seeks an answer and it makes clear that the answer is higher than 17. Any attempt, no matter how naive, at solving the problem will not provide a number much bigger than 17. So, by trying different numbers like 18, 19, … the solver is about to find the solution, thus gaming the system.

But since I do not know how the test was actually administered, I will leave this point at that.

But even then, the test expects a number. Giving a number willy nilly, does not say anything. Giving a picture with a path drawn, writing an answer that proves your thinking, posting a blog post like this one, does say something. So, again how was this test administered? I do not know, but I am afraid that the answer might be highly disturbing.

Back to the answer. Below, I provide two images.

First image:

 

Second image:

From the two images above, we can see that the answer is 19. The minimum numbers of streets to walk on in order to cross all of them is 19. And this is the answer and if you need a little more explaining (do not worry about the word “little”, I am going to provide a whole lot more of explaining in the rest of this blog post) you can observe the two images.

Indeed, you might observe that I provide two equivalent solutions. Two, because there are two images. But wait! In each image, you see that I start from the left and I stop at the right. Or vice versa. The path may be the same but does it count as one or two solutions depending on the direction of travel? I should say that it does not. Your opinion may differ and it is all right. We will discuss more about this later on, anyway.

In both images, the start and stop points are on the left and right middle buildings. But on the first image we observe a point where the path crosses itself. This is like the center of a swastika. When you reach this point, you can go straight or turn 90 degrees. Does this count as two separate solutions or one? Either way, we all know what we are talking about and what we see here concerning the path taken.

But this goes for the second image as well. See that in the same building that is the center of the swastika, the path does not cross itself? I made it so that you can understand the path more clearly. But in reality, it can cross itself, and so different paths and solutions arise, each with 19 steps.

So, in the first image, when you reach the node in the second row and second column from the left, then you can go straight or turn 90 degrees. In the second image, when you reach this node, you can go up or down.

So, the answer is 19, all is ok and we can go and watch Chesapeake Shores (or is it Cheesypeake Shores? Chesapeake Whores? I can never remember!)

And you can stop reading here and all is well. But If you want to go the distance, well, please stay a little longer, dear reader. There are some things that need more explaining and there are some sinister things going on as well.

How am I sure that the minimum is 19?

I will answer, but first let me say something else, that will help me arrive at the answer for the question I just posed.

One of the sinister things concerning this question is that it does not state if we are allowed to choose where to start and where to end our path. Are we allowed? The question supposes that we are, but someone would not know that. But then, how do I know that the question allows that?

I know because this question is about the mathematical subject called Graph Theory and Graphs. And the problem presented here is a common problem in Graph Theory and all common assumptions apply.

And this gives an unfair advantage to someone who knows Graph Theory compared to someone who doesn’t. A huge chasm. A hugely unfair advantage.

Graph Theory makes me certain that the minimum is 19. Someone who does not know Graph Theory would have a hard time to prove that 19 is the minimum, whereas it is easy for me. As I said: Unfair advantage. And I have a problem with unfair advantages. A very big problem.

Anyway, this puzzle pertains to graphs and graphs have their terminology and their common assumptions that make sense in this area of Mathematics.

Here are some links that may help, especially the one about the Seven Bridges of Konigsberg. That Wikipedia article alone is enough to explain what is going on in this question.

Seven Bridges of Königsberg

Eulerian path

Hamiltonian path

Route inspection problem

Graph (discrete mathematics)

Graph theory

To explain something and/or to tell a story, sometimes the most difficult thing is to find where to begin. Our story begins when Euler visited the town of Konigsberg. There, the town folk had a pet peeve. Or a question. Or both. They had healthy inquiring minds. Or not. Anyway, their town is depicted in the map below and the good people of Konigsberg wanted to know if one could go to all four land areas by crossing each of the seven bridges exactly once.

I said that the town folk had healthy inquiring minds, but I am not so sure. To me, it seems obvious that this cannot be done. I cannot find a path that would go to all land areas and traverse each bridge only once. But the town folk either did not have a map like the above (highly improbable), or they were way more inquiring than me and needed a mathematical proof for the possibility or impossibility of such a feat.

Anyway, Euler heard about the problem and thought that this was an interesting problem for him to solve. And solve it he did. He proved that this is impossible. He proved that it is impossible to visit all four land areas by traversing each bridge only once.

How Euler thought and went about solving this problem is crucial for us in order to understand why the answer I gave in the test puzzle is 19 and it is certain that it is 19.

But before I get to that, I must stress that the town folk cared about a path but did not care about which land would be the beginning and which land would be the end of the path. They just wanted a path that would traverse all bridges, each bridge exactly once and visit all land areas.

This notion is an important notion in Graph Theory and is named in honor of Euler as Eulerian path. So, in retrospect, the town folk wanted to know if a Eulerian path exists. And the question of this puzzle is almost the same. It states that there is no Eulerian path and asks us to find the minimum number of bridge traversals we have to make. In the Konigsberg problem, we have land areas and bridges. In this puzzle, we have buildings and streets, respectively.

but the common understanding is that when we are dealing with Eulerian paths, we are not choosy about which is the starting point and which is the finishing point. Of course, in the street cleaner example that the puzzle is all about, let me tell you, the street cleaner would definitely like to have a saying as to where her work would start and where it would end: I guess as close to her home as possible. But the puzzle assumes what is usually assumed in such graph problems. Thus, it is inappropriate for “general consumption”.

But I guess that it would make a great question for a mathematician interested in graphs. Below I will try to explain what is going on in this puzzle, but it will help if you know a few things about graphs already, like studying the links that I provided above.

So, in this puzzle, what we have in front of us is a graph. The nodes (or vertices) of the graph are the buildings. The edges of the graph are the streets. This graph is an undirected connected graph. “Undirected” means that the edges have no direction (for each edge there are two nodes, but not a beginning and an ending node, just two nodes). “Connected” means that no “islands” exist. There is always a path from a node to another node, but it might be through another node. This is why I did not characterize the graph as “complete”. It is not “complete”. Not all possible edges exist. This graph is just “connected”.

So we have an undirected connected graph and we want to study the Eulerian paths. Actually, we know that there are no Eulerian paths, but we want to find the minimum next best path.

Before we get to that, I would just like to bring your attention to the difference between Hamiltonian and Eulerian paths. A Hamiltonian path is one that visits each node once. A Eulerian path is one that visits each edge once. And in both, it does not matter where we begin and where we end.

When Euler studied the Seven Bridges of Konigsberg, he understood a few very important concepts. He understood that what plays the defining role is the number of bridges (edges) that each land (node) has attached. The number of edges that are connected to a node is called the degree of the node. And it is the most important thing in order to study the existence of the Eulerian paths.

You see, Euler understood that during a walk, the path you go along traversing land areas and bridges, will bring you in and out of land areas. Let us exclude the beginning and ending land area for a moment. All other land areas will be visited by going in one bridge and leaving in another (a different one, a different bridge) since we do not want to traverse the same bridge twice. And so he realized that for a Eulerian path to exist, all intermediate nodes in the path have to have an even degree, that is, an even number of edges connected to them. Now for the beginning and ending node, they have to be both of either odd or even degree. If one of them is of odd degree and the other one is of even degree, then a Eulerian path does not exist.  If there are two nodes of odd degree, then anyone of them will be the beginning node and then the other will have to be the ending node of the Eulerian path. If there are zero nodes of odd degree, then a Eulerian path definitely exists.

So, for a Eulerian path to exist, all nodes have to be of even degree, or two nodes have to be of odd degree, In the latter case, each one of them can be the beginning node of the path, but once we chose the beginning node, the other node has to be the ending node of the path.

Now we have all the concepts we need to solve the puzzle in the most mathematical and precise way there is.

The Seven Bridges of Konigsberg did not have a Eulerian path because the corresponding graph contained 4 nodes and each one of those had an odd degree.As you can see in the map, three land areas had three bridges connected to them and one land area had five bridges connected to them. So, all land areas had an odd number of bridges connected to them. I wish I could go to Konigsberg  and scream to the ear of each town folk: “Hey baster, there is no Eulerian path, because in this connected graph, there are four nodes and all have an odd degree. Get it? No? You need to have zero or two nodes of odd degree in order to have a Eulerian path! Get it now? You stupid %@^&!”.

The same goes for the corresponding graph for this puzzle. There is no Eulerian path, because there are six nodes of odd degree. The following image depicts these six nodes by having circles around them. I circled them and I also used the green color for the nodes on the far left and far right and the red color for the nodes in the upper an lower part. I did this in order to facilitate the discussion that is going to follow.

In the solutions that I gave, I always start and finish at the green nodes. And I always traverse twice the two pairs of red nodes, the pair in the upper part and the pair in the lower part. This is not coincidental. By traversing the red nodes twice, it is as if I create another edge among them. It is as if I create another street. Please note that in the two images that depict the solutions that I gave, the pairs of the nodes have another red line going backwards and in a slight angle. This means that I traversed this path twice. And it can equivalently mean that I created another street between these two buildings. And by doing so, I changed the degree of the nodes (buildings) from odd to even.

Thus, it only takes one more edge between the two upper middle nodes and one more edge between the lower middle modes to turn this graph in to one with two nodes of odd degree (the nodes circled with green color). And this is why all solutions start and end in these two green nodes. Because, by traversing twice the red nodes edge, it is as if I created another edge, thus making them into even degree nodes, thus leaving the green circled nodes to be the only two odd degree nodes, so they had to be the beginning and ending node of the Eulerian path that was just created by the virtual addition of the two new nodes that my double traversing made.

Now, one may ask if we can have another pair of the six odd degree nodes as the beginning and ending node. The answer is that we cannot. Actually we can create an edge between any two of them and another edge between any other two of them, thus leaving again only two nodes with an odd degree. But the edges that we will draw will not be 1 kilometer long. There will be lengthier. So, although we can create a Eulerian path by leaving any two odd degree nodes, the only case that we can do so and with the minimum distance is if we connect the adjacent pairs of the red nodes.

And this is how I know that the solutions that I gave are optimal, that the beginning and ending building are those on the middle far left and right and that the minimum path needed to traverse all streets is 19 kilometers long.

Advertisements

About Dimitrios Kalemis

I am a systems engineer specializing in Microsoft products and technologies. I am also an author. Please visit my blog to see the blog posts I have written, the books I have written and the applications I have created. I definitely recommend my blog posts under the category "Management", all my books and all my applications. I believe that you will find them interesting and useful. I am in the process of writing more blog posts and books, so please visit my blog from time to time to see what I come up with next. I am also active on other sites; links to those you can find in the "About me" page of my blog.
This entry was posted in Education. Bookmark the permalink.