HMMT 十一月 2025 · GEN 赛 · 第 10 题
HMMT November 2025 — GEN Round — Problem 10
题目详情
- Jacob and Bojac each start in a cell of the same 8 × 8 grid (possibly different cells). They listen to the same sequence of cardinal directions (North, South, East, and West). When a direction is called out, ◦ Jacob always walks one cell in that direction, while Bojac always walks one cell in the direction 90 counterclockwise of the called direction. If either person cannot make their move without leaving the grid, that person stays still instead. Over all possible starting positions and sequences of instructions, compute the maximum possible number of distinct ordered pairs (Jacob’s position , Bojac’s position) that they could have reached. © 2025 HMMT
解析
- Jacob and Bojac each start in a cell of the same 8 × 8 grid (possibly different cells). They listen to the same sequence of cardinal directions (North, South, East, and West). When a direction is called out, ◦ Jacob always walks one cell in that direction, while Bojac always walks one cell in the direction 90 counterclockwise of the called direction. If either person cannot make their move without leaving the grid, that person stays still instead. Over all possible starting positions and sequences of instructions, compute the maximum possible number of distinct ordered pairs (Jacob’s position , Bojac’s position) that they could have reached. Proposed by: Sebastian Attlan Answer: 372 Solution: C B J © 2025 HMMT ◦ Suppose there is a third person, Caboj, who starts at the cell which is a 90 clockwise rotation of Bojac’s position about the grid’s center, and always moves in the called direction (unless doing so would leave ◦ the grid). Notice that Caboj’s path is precisely the 90 clockwise rotation of Bojac’s path about the center. Therefore, to maximize the number of ordered pairs (Jacob’s position , Bojac’s position), it suffices to maximize the number of ordered pairs (Jacob’s position , Caboj’s position). Consider the (possibly degenerate) rectangle with opposite vertices at Jacob’s and Caboj’s positions. When Jacob and Caboj both move, this rectangle gets translated by 1 unit in some direction, and when only only one of Jacob and Caboj moves, this rectangle shrinks by 1 unit in some dimension. In particular, both side lengths of this rectangle, and hence the taxicab distance between Jacob and Caboj, are nonincreasing. Suppose this taxicab distance is currently d , and the rectangle has dimensions x × y , where x + y = d +2. There are (9 − x )(9 − y ) distinct translations of this rectangle within the grid, all of which are achievable without shrinking the rectangle. Therefore, there are at most (9 − x )(9 − y ) ordered pairs of positions with the rectangle having size x × y . This quantity is maximized when x and y are as close as possible, i.e., x = y = d/ 2 + 1 when d is even and { x, y } = { ( d + 1) / 2 , ( d + 3) / 2 } when d is odd. Since the side lengths of the rectangle cannot increase, only one rectangle size can be reached for each taxicab distance d . Summing over all possible taxicab distances, we get an upper bound of (1)(1) + (1)(2) + (2)(2) + (2)(3) + (3)(3) + (3)(4) + · · · + (7)(8) + (8)(8) 2 2 2 2 = 2(1 + 2 + · · · + 7 ) + (1 + 2 + · · · + 7) + 8 7 · 8 · 15 7 · 8 = 2 + + 64 6 2 = 372 . We can construct this by first having a 8 × 8 rectangle and achieving 1 · 1 position, then shrinking to a 7 × 8 rectangle and achieving 1 · 2 positions, then shrinking to a 7 × 7 rectangle and achieving 2 · 2 positions, and so on (alternating which dimension we shrink), until we have a 1 × 1 rectangle and achieve 8 · 8 positions. © 2025 HMMT