any ideas ?

Am I missing something? Suppose $n$ is even and all the doors are inversive. Then, he would have to pass through $n^2 - 1$ doors and hence will finish as inverted-USJL every time?

Snark_Graphique wrote: Am I missing something? Suppose $n$ is even and all the doors are inversive. Then, he would have to pass through $n^2 - 1$ doors and hence will finish as inverted-USJL every time? Oops, my bad. It is given that there exists a normal door.

bump this

Question, I keep seeing "bump" everywhere. What does it mean? how_to_what_to wrote: bump this

When a reply is posted in a thread the thread is "bumped" to the top of the forum. Sometimes users like to bring a thread back into discussion but don't have anything to add, so instead of typing something random they type "bump".

Ah, thank you!

If $n$ is even: Consider some normal door. It is not hard to show that there is a cycle (where USJL visits each room once and returns to its starting room) that uses the normal door. If this cycle also uses an inversive door, consider the two paths obtained by "cutting" the cycle at the normal and inversive door respectively: the parity of number of inversive doors in these paths are different, so one of them will allow USJL to escape. If this cycle uses normal doors only, just cut the cycle at any door and that will create a path for USJL to escape. If $n$ is odd: Label the rooms $(1,1), \dots, (n,n)$. Also color the rooms black and white in checkerboard fashion so that the four corners are white. Suppose that USJL cannot escape. We claim that if two doors connect to the same black room and form a right angle with each other (i.e. the three rooms connected by the doors form an L-shape), then they must be the same type. To prove this, suppose the black room is $(i,j)$ where $i$ is even and $j$ is odd ($i,j \geq 2$), and the two doors also connect to $(i-1,j)$ and $(i,j-1)$ respectively. Note that the path \[ A : (i-1,j) \twoheadrightarrow (1,j) \twoheadrightarrow (1,1) \to (2,1) \twoheadrightarrow (2,j-1) \to (3,j-1) \twoheadrightarrow (3,1) \to (4,1) \twoheadrightarrow (4,j-1) \to \dots \to (i,j-1) \](where $P \twoheadrightarrow Q$ means to go from $P$ to $Q$ in a horizontal/vertical line where $P$ and $Q$ are in the same row/column) passes through all rooms in $\{ (x,y) : x \leq i, y \leq j \} \setminus \{(i,j)\}$, and the path \begin{align*} B : &(i,j) \to (i,j+1) \twoheadrightarrow (1,j+1) \to (1,j+2) \twoheadrightarrow (i,j+2) \to \dots \to (i,n) \\ &\to (i+1,n) \twoheadrightarrow (n,n) \to (n,n-1) \twoheadrightarrow (i+1,n-1) \to (i+1,n-2) \twoheadrightarrow (n,n-2) \to \dots \to (n,1) \end{align*}passes through all rooms in $\{(x,y) : x>i \lor y > j\}$. So the two paths \[ (i-1,j) \stackrel{A}\to (i,j-1) \to (i,j) \stackrel{B} \to (n,1) \]and \[ (i,j-1) \stackrel{A^{-1}}\to (i-1,j) \to (i,j) \stackrel{B} \to (n,1) \](where $A^{-1}$ is the "reverse" of path $A$) visits all rooms exactly once, and the only difference in the doors used are the two aforementioned doors. If they are different types, then one of these paths will allow USJL to escape. So they must be the same type. Now consider any path through all the rooms. Since it starts and ends on white rooms, it must enter and exit each black room exactly once. By applying the claim above (twice if the doors are opposite each other), the two doors used must be of the same type, so USJL will remain normal after returning to a white room and can escape.