HMMT 二月 2025 · COMB 赛 · 第 5 题

HMMT February 2025 — COMB Round — Problem 5

In an 11 × 11 grid of cells, each pair of edge-adjacent cells is connected by a door. Karthik wants to walk a path in this grid. He can start in any cell, but he must end in the same cell he started in, and he cannot go through any door more than once (not even in opposite directions). Compute the maximum number of doors he can go through in such a path.

解析

In an 11 × 11 grid of cells, each pair of edge-adjacent cells is connected by a door. Karthik wants to walk a path in this grid. He can start in any cell, but he must end in the same cell he started in, and he cannot go through any door more than once (not even in opposite directions). Compute the maximum number of doors he can go through in such a path. Proposed by: Derek Liu Answer: 200 Solution: This is simply asking for the longest circuit in the adjacency graph of this grid. Note that this grid has 4 · 9 = 36 cells of odd degree, 9 along each side. If we color the cells with checkerboard colors so that the corners are black, then 20 of these 36 cells are white. An Eulerian circuit uses an even number of doors from each cell, so at least one door from each of these cells goes unused. No door connects two white cells, so at least 20 doors are unused, leaving at most 2 · 10 · 11 − 20 = 200 doors crossed. To see this is achievable, we first delete the bottom-right cell and its 2 doors, as well as the top-left cell and its 2 doors. This leaves 8 odd-degree cells along each side of the grid; we can delete 4 doors along each to cover all remaining odd-degree cells, for 20 total doors deleted. The resulting graph is con- nected and has no odd-degree cells, so it must have an Eulerian circuit. This circuit is our desired path.