0

Let n be an integer with n ≥ 2. Consider a building in the shape of a cube. The inside of the building is divided up into n^3 rooms, all of them in the shape of a cube and all of them having the same size. Between any two adjacent rooms, there is a door. (Thus, each room has 3, 4, 5 or 6 doors. The rooms with 6 doors have one door in the ceiling to the room above, one door in the floor to the room below, and four doors in the horizontal walls to the rooms on the same level.) Is it possible to make a tour of the building, passing through each door exactly once? Does the answer depend on n?

I think there does not exist such a path, and the answer does not depend on n. I also think, that I have to user Euler's Theorem.

Giorgia
  • 7

1 Answers1

0

We can just convert this into a graph where each room is a vertex and each door is an edge. Since the corner rooms each only have $3$ doors, and $3$ is odd, there is no Eulerian path (note that there are $8$ corner rooms and $8>2$).

This is because there only exists an Eulerian path if at most $2$ vertices have odd degree. Please see here for more information about Eulerian paths and circuits.

Peter Woolfitt
  • 21,114