HMMT 二月 2025 · COMB 赛 · 第 4 题

HMMT February 2025 — COMB Round — Problem 4

Sophie is at (0 , 0) on a coordinate grid and would like to get to (3 , 3). If Sophie is at ( x, y ), in a single step she can move to one of ( x + 1 , y ), ( x, y + 1), ( x − 1 , y + 1), or ( x + 1 , y − 1). She cannot revisit any points along her path, and neither her x -coordinate nor her y -coordinate can ever be less than 0 or greater than 3. Compute the number of ways for Sophie to reach (3 , 3).

解析

Sophie is at (0 , 0) on a coordinate grid and would like to get to (3 , 3). If Sophie is at ( x, y ), in a single step she can move to one of ( x + 1 , y ), ( x, y + 1), ( x − 1 , y + 1), or ( x + 1 , y − 1). She cannot revisit any points along her path, and neither her x -coordinate nor her y -coordinate can ever be less than 0 or greater than 3. Compute the number of ways for Sophie to reach (3 , 3). Proposed by: Derek Liu Answer: 2304 Solution: Let a lateral move refer to one which is either up or right. Then the lateral moves are the only ones which increase Kelvin’s sum of coordinates by 1, while all other moves do not change the sum, so Kelvin must make 6 of them, one to increase this sum from i to i + 1 for each i ∈ [0 , 5]. 4 2 4 6 6 2 We claim there exists a unique path corresponding to each set of 6 lateral moves chosen in this way. Indeed, the diagonal moves allow Kelvin to get from any point on x + y = i to any second point on x + y = i in exactly one way. Observe that when i ≤ 2, the number of lateral moves that increase the sum of coordinates from i to i +1 is 2 i , as is the number that increase it from 5 − i to 6 − i . Thus the answer is 2 · 4 · 6 · 6 · 4 · 2 = 2304 .