This problem was proposed by Dominic Yeo, United Kingdom. The statement proposed to IMO 2018 is as follows: Vlad the Impaler likes to entomb his enemies underneath his castle in a network of $2N$ torture chambers, each with three doors. These are connected by a number of corridors, which only meet at the torture chambers, but can pass over and around each other with staircases and tunnels. Dan III of Wallachia wakes up in one corridor, and starts crawling in one direction, trying to escape. So that he doesn't get lost, whenever he arrives at a torture chamber, he always exists through the door to the left of the door he entered. Eventually, Dan realises that he has passed down every corridor in both directions (and so knows he cannot escape). For which values of $N$ is this possible?

This question was also posted on Math Stack Exchange. Here is the answer. (First part for odd $n$ is my solution, the second part, for even $n$ is Will Orrick's) For odd N Of course, cases $N=3$ and $N=5$ work ($N$ must be $\geq 2$ for the graph to make sense, so we cannot discuss about $N=1$). Here are $2$ configurations which show that $N=3$ and $N=5$ work: See the image here: https://i.stack.imgur.com/79a5B.png (For some reason I cannot add photos) We will now show that if $N_1$ and $N_2$ work, then $N_1+N_2+1$ works. Suppose we have $2$ graphs $G_1$ and $G_2$, one with $2N_1$ vertices and the other with $2N_2$ vertices, which both work. Select $2$ vertices which are connected from $G_1$, $v_1$ and $v_2$ and $2$ vertices that are connected from $G_2$, $u_1$ and $u_2$. Add $2$ more vertices, $w_1$ and $w_2$. If we prove we can connect some vertices such that the new graph works (which has $2\cdot(N_1+N_2+1)$), we proved that if $N_1$ and $N_2$ are valid numbers, then so is $N_1+N_2+1$. We will do the folowing operations: - erase the edge between $v_1$ and $v_2$ - erase the edge between $u_1$ and $u_2$ - connect $v_1$ and $w_1$ - connect $v_2$ and $w_2$ - connect $u_1$ and $w_1$ - connect $u_2$ and $w_2$ - connect $w_1$ and $w_2$ So from this initial configuration See the image here: https://i.stack.imgur.com/wVjVT.png we reach this configuration See image here: https://i.stack.imgur.com/1chWC.png I will not actually explain step by step why it works, but a simple analysis of the trip the car will make with these new little changes will, indeed, confirm that this new graph works. Thus, $N_1$, $N_2$ work implies that $N_1+N_2+1$ works. We have shown $3$ and $5$ work, so every odd $N$ works. $\text{ }\blacksquare$ --- For even N We show that there can be no such tour for even $N$. Embed the graph in a two-dimensional surface. In order for the notion "clockwise" to be well-defined, the surface must be an orientable one. Now the number of vertices is $2N$ and the number of edges is $3N$. If a tour like the one you've described exists, then the embedding can be regarded as a map with a single face (that has $6N$ sides). But the generalization of Euler's formula, $$ V-E+F=2-2g, $$must hold, where $g$ is the genus of the surface on which the graph is embedded. So we get $$ 2N-3N+1=2-2g. $$This is a contradiction if $N$ is even. $\text{ }\blacksquare$ Edit: The desired embedding is achieved by drawing the graph on a sphere with handles, which is an orientable surface. To explain this a bit more, start by drawing the graph on the sphere. There will, in general, be some crossings of edges. The graph should be drawn in accordance with the specified clockwise ordering of edges at each vertex (roundabout). To enforce this ordering, even a planar graph may sometimes need to be drawn with edge crossings. Remove or reroute edges (without violating edge-ordering constraints) until there are no more crossings. This can be done in such a way that the graph remains connected. Now add the removed edges back, one at a time: if an edge can be drawn within a single face, do so. (The face will be divided into two faces.) If it cannot, the insertion points of the edge lie in two different faces. Cut holes in each of these faces and join the holes with a tube. In this process the faces started as two surfaces each homeomorphic to a disk and ended as a single surface homeomorphic to a cylinder. Now route the edge across the cylinder, which cuts the cylinder so it is again homeomorphic to a disk. Once all edges have been added back, we have the desired embedding of the graph in an orientable surface. This is a 2-cell embedding, meaning all faces are homeomorphic to disks, a property that is necessary in order to apply Euler's formula. The ideas in this sketch come from the short article, J. H. Lindsay, An Elementary Treatment of the Imbedding of a Graph in a Surface. The American Mathematical Monthly 66(2) (1959) 117-118. and from Jack Edmond's masters thesis Edmonds, John Robert (1960). A combinatorial representation for oriented polyhedral surfaces. University of Maryland. A quotation from the latter: Quote: Theorem 2. Given a connected linear graph with an arbitrrarily specified cyclic ordering of the edges to each vertex, there exists a topologically unique, two-sided polyhedron Whose edges and vertices are the given graph and whose clockwise edge orderings at each vertex (with respect to one of the sides) are as specified. These ideas have a long history, going all the way back to Lothar Heffter in the 1890s. The notion of associating an embedding with a specification of the edge orderings at each vertex of a graph now goes by the name [rotation system](https://en.wikipedia.org/wiki/Rotation_system). If you want to try out the ideas, you can verify that there are essentially three different rotation systems for $K_4$, producing three different embeddings, one spherical (genus $0$) embedding with four triangular faces and two toroidal (genus $1$) embeddings, each with two faces—either a triangle and a nonagon or a quadrilateral and an octagon.