HMMT 十一月 2022 · 冲刺赛 · 第 8 题

HMMT November 2022 — Guts Round — Problem 8

[7] Kimothy starts in the bottom-left square of a 4 by 4 chessboard. In one step, he can move up, down, left, or right to an adjacent square. Kimothy takes 16 steps and ends up where he started, visiting each square exactly once (except for his starting/ending square). How many paths could he have taken? ◦ ◦

解析

[7] Kimothy starts in the bottom-left square of a 4 by 4 chessboard. In one step, he can move up, down, left, or right to an adjacent square. Kimothy takes 16 steps and ends up where he started, visiting each square exactly once (except for his starting/ending square). How many paths could he have taken? Proposed by: Richard Qi Answer: 12 Solution: The problem is asking to count the number of cycles on the board that visit each square once. We first count the number of cycle shapes, then multiply by 2 because each shape can be tra- versed in either direction. Each corner must contain an L-shaped turn, which simplifies the casework. In the end there are only two valid cases: the path must either create a U shape (4 possible orienta- tions) or an H shape (2 possible orientations). Thus, the answer is 2(4 + 2) = 12. ◦ ◦