An Eulerian Map Problem

[SLD]

Ok. There are four “rooms” and there are 9 gates arranged as above. You must simply find a path can start or end anywhere and can cross over a previous path, but must go through each gate precisely one time. Ignore the path that this moron started. The only solutions are those that start and end in the two lower rooms because those have odd numbers of gates. There are only two of them, so there are undeniably solutions. But how many unique ones? And how do you actually demonstrate that without drawing them all out. That is prove it to a blind person.

 

[Spacetime Inhabitant]

I think that there must be some restrictive condition that is missing from your text above, because in stated text solving for a path is ridiculously easy, including by extending the path already partially drawn, and it can be done without crossing any previous path. Maybe that you can only cross any blue line only once?

 

[bilby]

I think that there must be some restrictive condition that is missing from your text above, because in stated text solving for a path is ridiculously easy, including by extending the path already partially drawn, and it can be done without crossing any previous path. Maybe that you can only cross any blue line only once?

I understood that the words "room" and "gate" imply that your path cannot cross any blue line at all. To enter or exit one of the four "rooms", your path must use a "gate".

 

[Spacetime Inhabitant]

I think that there must be some restrictive condition that is missing from your text above, because in stated text solving for a path is ridiculously easy, including by extending the path already partially drawn, and it can be done without crossing any previous path. Maybe that you can only cross any blue line only once?

I understood that the words "room" and "gate" imply that your path cannot cross any blue line at all. To enter or exit one of the four "rooms", your path must use a "gate".

That makes sense, as then the situation in the diagram does not lead to a solution, as SLD said.

 

[steve_bank]

Learn something new every day. Good post, thanks for sometime new.

Eulerian path - Wikipedia

en.wikipedia.org

In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

When I was a kid an older cousin laid this on me and I spent days trying to solve it.

Connect three lines from each box to each circle without crossing lines.

 

[SLD]

I think that there must be some restrictive condition that is missing from your text above, because in stated text solving for a path is ridiculously easy, including by extending the path already partially drawn, and it can be done without crossing any previous path. Maybe that you can only cross any blue line only once?

I understood that the words "room" and "gate" imply that your path cannot cross any blue line at all. To enter or exit one of the four "rooms", your path must use a "gate".

That makes sense, as then the situation in the diagram does not lead to a solution, as SLD said.

Yes, I said go through each gate precisely once. You can’t go into or out of a room without going through a gate.

 

[Bomb#20]

Ok. There are four “rooms” and there are 9 gates arranged as above. You must simply find a path can start or end anywhere and can cross over a previous path, but must go through each gate precisely one time. Ignore the path that this moron started. The only solutions are those that start and end in the two lower rooms because those have odd numbers of gates. There are only two of them, so there are undeniably solutions. But how many unique ones? And how do you actually demonstrate that without drawing them all out. That is prove it to a blind person.

Count

Show

I count 240 solutions.

Explanation

Show

The top left and top right rooms are effectively the same room; the wall and gate between them are irrelevant. Label the three rooms n, w and e for North, southWest and southEast. Assume without loss of generality the path will start in w and end in e. A 2 or 3 before a room label means we have a choice of gates to go through to get to the next position. The 2(...) notation means the contents of the parentheses can optionally be run through in reverse order. A blank space means we're outside the building.

There are five basic categories of solution:

2w 2(2(we3n) 2nn) e
2w 2(2(e3n) 2nn) we
2w 2(2(ew) 3n2n) ne
we 2(2ww 3n2n) ne
we3n 2(2ww 2nn) e

Each category has 24 variations because of the choices of gates, making 120 ways to get from w to e; and the same paths can all be run from e to w.

 

[Bomb#20]

Count

Show

I count 240 solutions.

Gah! I can't count the multipliers in my own formulas. Make that

Show

384