MathDB
Escaping is always possible

Source: IMOC 2023 C2

September 9, 2023
combinatorics

Problem Statement

A square house is partitioned into an n×nn \times n grid, where each cell is a room. All neighboring rooms have a door connecting them, and each door can either be normalor inversive. If USJL walks over an inversive door, he would become inverted-USJL,and vice versa. USJL must choose a room to begin and walk pass each room exactly once. If it is inverted-USJL showing up after finishing, then he would be trapped for all eternity. Prove that USJL could always escape.