HMMT 十一月 2025 · 团队赛 · 第 8 题
HMMT November 2025 — Team Round — Problem 8
题目详情
- [50] Alexandrimitrov is walking in the 3 × 10 grid below. He can walk from a cell to any cell that shares an edge with it. Given that he starts in cell A , compute the number of ways he can walk to cell B such that he visits every cell exactly once. (Starting in cell A counts as visiting cell A .) A B
解析
- [50] Alexandrimitrov is walking in the 3 × 10 grid below. He can walk from a cell to any cell that shares an edge with it. Given that he starts in cell A , compute the number of ways he can walk to cell B such that he visits every cell exactly once. (Starting in cell A counts as visiting cell A .) A B © 2025 HMMT Proposed by: Sebastian Attlan Answer: 254 Solution: First, suppose Alexandrimitrov initially walks to the right i ≥ 0 steps, then walks either up or down. Afterwards, he must walk left and around the starting cell in order to visit every cell exactly once, and arrives at the last cell i ≥ 0 steps to the right. Symmetrically, Alexandrimitrov walks in this way in the reverse direction at the end of his path, ending by walking j ≥ 0 steps to the right to cell B . In particular, the start and the end of the path must look like the following diagram. · · · After this start section, if a path continues by moving to the right for k cells and then moves to the center row, it must snake left to the starting column and back right along the third row to cover all cells left of the k + 1st column. In particular, it must look like one the following diagrams. Continuing the argument, we see that Alexandrimitrov’s path must decompose into blocks that look like one of the following. From here, there are two approaches. Approach 1 (Direct Bijection). We know that Alexandrimitrov’s path is partitioned into several rectangular blocks. To build such a nd th partition, we place dividers between two consecutive blocks. From the 2 to the 9 column, there are 7 dividers between two consecutive columns. We choose a nonempty subset of these dividers, which 7 there are 2 − 1 = 127 ways. There are 2 ways to pick the orientation of the start block. Then the rest of the path is uniquely determined. In total, there are 2 · 127 = 254 ways. The following diagram shows two examples of converting dividers to the path. © 2025 HMMT Approach 2 (Recursion). We separate Alexandrimitrov’s path into three sections: these start and end sections, and a path from a left corner to a right corner of a 3 × (6 − i − j ) subgrid visiting each cell exactly once. Let S be the n number of ways to do this in a 3 × n grid with the starting and ending corners on the same side, and let T be the the number of ways to do this with them on different sides. n We proceed recursively: for n ≥ 2, we may observe that if a path begins by moving to the right for k cells and then moves to the center row, it must snake left to the starting column and back right along the third row to cover all cells left of the k + 1st column. Summing over all k , we have that S = T + · · · + T + T and T = S + · · · + S + S . n n − 1 1 0 n n − 1 1 0 n − 2 Using S = 1, T = 0, S = 0, T = 1, we may compute S = T = 2 for n ≥ 2. 0 0 1 1 n n There are 7 − n choices of i and j resulting in a 3 × n middle subgrid, so there are a total of " # 6 X n − 2 2 · 7 · (1 + 0) + 6 · (0 + 1) + 2 · (7 − n ) · 2 = 254 n =2 paths.