MathDB

C2

Part of 2023-IMOC

Problems(1)

Escaping is always possible

Source: IMOC 2023 C2

9/9/2023
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.
combinatorics