HMMT 二月 2024 · COMB 赛 · 第 4 题
HMMT February 2024 — COMB Round — Problem 4
题目详情
- Sally the snail sits on the 3 × 24 lattice of points ( i, j ) for all 1 ≤ i ≤ 3 and 1 ≤ j ≤ 24 . She wants to visit every point in the lattice exactly once. In a move, Sally can move to a point in the lattice exactly one unit away. Given that Sally starts at (2 , 1) , compute the number of possible paths Sally can take.
解析
- Sally the snail sits on the 3 × 24 lattice of points ( i, j ) for all 1 ≤ i ≤ 3 and 1 ≤ j ≤ 24 . She wants to visit every point in the lattice exactly once. In a move, Sally can move to a point in the lattice exactly one unit away. Given that Sally starts at (2 , 1) , compute the number of possible paths Sally can take. Proposed by: Isabella Zhu Answer: 4096 Solution 1: On her first turn, Sally cannot continue moving down the middle row. She must turn either to the bottom row or the top row. WLOG, she turns to the top row, and enters the cell (3 , 1) and we will multiply by 2 later. Then, we can see that the path must finish in (1 , 1) . So, we will follow these two branches of the path, one for the start and one for the end. These branches must both move one unit up, and then one of the paths must move into the center row. Both branches move up one unit, and then the path in the middle row must go back to fill the corner. After this, we have exactly the same scenario as before, albeit with two fewer rows. So, for each additional two rows, we have a factor of 12 two and thus there are 2 = 4096 paths. Solution 2: We solve this problem for a general 3 by 2 n grid. On her first turn, Sally cannot continue moving down the middle row. She must turn either to the topmost row or the bottommost row. WLOG, she turns to the top row. Suppose Sally returns to the middle row k times. There are k ”blocks”. However, 2 k of the squares are already occupied by Sally’s row shifts. Thus, we are solving 2( x + x + . . . x ) = 2( n − k ) . 1 2 k There are ( ) n ∑ n − k + k − 1 n − 1 = 2 k − 1 k =1 n solutions. We multiply by 2 to get 2 . 12 For n = 12 , this evaluates to 2 = 4096 .