Dodecahedron Space Station

You're on Space Station Dodecahedron (shaped exactly like a regular dodecahedron), where each vertex is a research node, and the edges are tubes which connect the nodes.

To fix a critical failure in life support systems, you must travel by connecting tubes, visiting each node of the space station exactly once, and then return to your starting node.

Is this possible?

Hint : The vertex graph of a dodecahedron is provided below.

Yes No

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

11 solutions

João Areias
Aug 20, 2018

This problem is asking if there is a Hamiltonian path on a dodecahedron. We know that every platonic solid has a Hamiltonian path. Here they are:

Source: Wolfram Mathword

contradictory question. ONLY "ONCE" then RETURN to the original node..... You are now at the original node TWICE. Hmmmmmm

J William Mignault - 2 years, 9 months ago

Log in to reply

You count up the "once"s before returning. After you're done "visiting each node of the space station exactly once," then you stop counting and THEN return. ;-)

C . - 2 years, 9 months ago

Log in to reply

That's the correct interpretation, and it makes the solution very easy (but it is probably not intended that way).

A Former Brilliant Member - 2 years, 9 months ago

Log in to reply

@A Former Brilliant Member Except that is exactly what it says, so it would be logical that it was intended.

Chris Cheek - 2 years, 9 months ago

GRAPH METHOD we can straight forward put the concept of 'eularian bridges' according to which in a graph if we call travel all the edges only once and come back to the starting point if and only if the no. of odd nodes is even. odd nodes-a node connected to odd no. of edges

gutloo gupta - 2 years, 9 months ago

Log in to reply

I've made this exact mistake myself... The thing is that in this problem we don't need to travel all EDGES only once, we just need to visit all nodes.

Also, you're not stating the condition correctly. There is an eulerian cycle (that comes back to the starting point) iff the number of odd nodes is ZERO. There is an eulerian path (that doesn't necessarily come back to the starting point) iff the number of odd nodes is at most two. (And FWIW in absolutely any graph, by the fact that each edge connects two nodes, there will always be an even number of odd nodes.)

C . - 2 years, 9 months ago

I think you are mistaking the eulerian path with the hamiltonian path . The eulerian path is the problem of visiting every edge and is as easy as you described to compute. The hamiltonian path is the problem of visiting every node and is actually NP-complete.

João Areias - 2 years, 9 months ago

thanks for correcting me i didn't know about hamiltonian paths so thanks

gutloo gupta - 2 years, 9 months ago

"Here they are"

Adrian Self - 2 years, 9 months ago

Isn't this the "Hamiltonian cycle" problem, since you are required to return to the initial node?

Omer Sarac - 2 years, 9 months ago

Log in to reply

yes, yes it is!

João Areias - 2 years, 9 months ago
David Vreken
Aug 19, 2018

Here is one possible path:

Ohhhh each NODE once, ignoring vertices.

I continue to fail to read the questions right.

Kevin Higby - 2 years, 9 months ago

Log in to reply

Jajaja it also happens to me usually

Diego Salcedo Tolosa - 2 years, 9 months ago

The nodes are the vertices...

Adrian Self - 2 years, 9 months ago

I thought I was supposed to connect the nodes with the tubes as well, so that would be impossible.

Victor NG - 2 years, 9 months ago
Sarim Khan
Aug 20, 2018

Does it matter where the start is?)

Igor Sokolov - 2 years, 9 months ago

Log in to reply

nope - its a loop

Thomas Duncan - 2 years, 9 months ago

Very professional. I love it!

Simon The Great - 2 years, 9 months ago

voted for art :)

Laszlo Kocsis - 2 years, 9 months ago

It's important to note that Hamilton path exists iff there's even (except 0) number of vertices that has odd number of edges connected to them.

In this problem all 20 vertices are odd edged. 20 is even, that means path exists.

This is the only answer using a theorem and not relying on other concepts. Great answer.

George Zoto - 2 years, 9 months ago

Brilliant Answer. It doesn't rely on brute force or esoteric facts. The only rule used applies to ALL networks.

Peter Quinn - 2 years, 9 months ago

This answer is incorrect. Try making a graph which does not follow this rule, where there's an odd number of vertices with an odd number of edges connected to them.

Daniel Baton - 2 years, 9 months ago

Log in to reply

Hint: It's impossible. Any edge will connect to 2 vertices, hence summing the number of edges connected to each vertex will always yield an even number. If there were an odd number of vertices with an odd number of edges connected to them, this sum would be odd, which isn't possible.

Daniel Baton - 2 years, 9 months ago
Raphael Ra
Aug 20, 2018

George Grills
Aug 20, 2018

The dodecahedron may be observed in the vertex graph as three concentric "rings". Starting from any node in either the center "ring" or outer "ring", the "ring" is traversed until the last node of the "ring" is reached, thus completing the "circumference", and then the traveler moves to the next ring. In this manner, all nodes may be visited only once.

But you have to end at starting position.

C Fortgens - 2 years, 9 months ago

Log in to reply

agreed. I missed the requirement that you must end where you begin!

George Grills - 2 years, 9 months ago
Fiyin Olatunbosun
Aug 24, 2018

A Hamiltonian path exists if every node has an even number of edges or if an even number of nodes has odd number of edges. The dodecahedron satisfies this condition... so it's possible.

Matt Westover
Aug 23, 2018

Correct me if my intuition here is incorrect but this problem is similar to the Bridges of Königsberg problem and thus Euler's solution to that problem applies to this one. But kudos are due to those who mapped a solution.

Anna Pendoti
Aug 23, 2018

This is a variation of the Hamiltonian Path Problem. The original one has no start or finishing points. However, this adds a twist to it as you must determine that one exists with a specific point as starting and finishing point.

THE VARIATION IS CALLED A HAMILTONIAN CYCLE

Mohammad Farhat - 2 years, 9 months ago
Dhabal Ch Mandal
Aug 22, 2018

Use the coloring principle

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...