3
$\begingroup$

You are going to build $8$ train stations and the railroads with it in an area. But you are asked to build these stations and their railroads in a very efficient way where there has to be the least number of intersection points on the railroad for the safety and most relaxed schedule and these all stations are also needed to be connected directly to each other as well. So;

What is the minimum number of crossing points possible? Draw a map of your solution.

Do not forget, only two railroads can intersect at the same point, otherwise it will not be safe at all passing more than two trains at the same point!

For example if this question was asked for 4 stations, the answer will be $0$ as shown below:

enter image description here

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ My opinion is that thing kind of puzzle isn't interesting. It sounds like a puzzle to someone who doesn't have the knowledge and it is trivial to those who know the theory, i.e., a knowledge quiz. I'd appreciate it more, at least, if there was an aha moment, or maybe some clever symmetry your average Joe is able to come up with to simplify the problem. And if there is indeed something like that, the accepted (and only answer) failed to illustrate it. $\endgroup$
    – Reti43
    Oct 8, 2017 at 23:03
  • $\begingroup$ @Reti43 actually this is a smart puzzle if you think over it by urself. i hsd found the answer by myself, u are free to check the answer or find the answer of urself and compare it with the actual result... i was convinced with my own answer even i did not know the optimal result. so if u check the answer first and judge the question, you do it in a wrong way in my opinion. $\endgroup$
    – Oray
    Oct 9, 2017 at 9:39
  • $\begingroup$ We have to agree to disagree, which is why I stated that as being my opinion. Besides, I arrived at the exact same solution with the starting thought of having a square inside another (4 + 4 nodes) and realising most of the crossings would occur in connecting the inner with the outer nodes. And while all the connections fell into place logically, there was no intuitive proof that my starting position was optimal. We could have people post their answers and without a formal proof, the best we could do is "we haven't found a better solution than X's". But maybe I'm missing something. $\endgroup$
    – Reti43
    Oct 9, 2017 at 12:01
  • $\begingroup$ Oray, I have to agree with Reti here. The fact that calculating 128*234 is difficult without using mathematics doesn't make it interesting. To pose this as a riddle just because some of the people won't know there is a theory about it doesn't save the situation. $\endgroup$
    – George Menoutis
    Jul 6, 2018 at 18:05

1 Answer 1

Reset to default
7
$\begingroup$

Basically you are asking what the crossing number is of the complete graph with 8 nodes. Below is a picture taken from the online book, Handbook of Graph Drawing and Visualization, chapter 2. The crossing number, i.e. the minimum number of crossings, is 18. enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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