HMMT 十一月 2025 · 冲刺赛 · 第 14 题
HMMT November 2025 — Guts Round — Problem 14
题目详情
- [9] Marin starts on the bottom-left square of a 6 × 7 grid and walks to the top-right square by taking steps one square either up or to the right. Given that the set of squares Marin visits on his walk can be partitioned into L-trominoes, compute the number of ways that Marin can complete his walk. An L-tromino is a set of three squares formed by removing exactly one square from a 2 × 2 grid of squares. One example of a valid path is shown below:
解析
- [9] Marin starts on the bottom-left square of a 6 × 7 grid and walks to the top-right square by taking steps one square either up or to the right. Given that the set of squares Marin visits on his walk can be partitioned into L-trominoes, compute the number of ways that Marin can complete his walk. An L-tromino is a set of three squares formed by removing exactly one square from a 2 × 2 grid of squares. One example of a valid path is shown below: Proposed by: Andrew Brahms Answer: 48 Solution: Note first that each of the L-trominoes must be oriented in one of the following two pictured configurations: This is because each of the other two types of L-tromino would induce either a leftward or downward movement, as shown below, which is forbidden by the problem statement. © 2025 HMMT Additionally note that because the grid has 7 columns and 6 rows, Marin will move right 6 times and up 5 times to get to the top-right corner, passing through a total of 12 squares. This additionally implies that we will use a total of 4 L-trominoes when tiling his path. Each L-tromino will correspond to Marin moving one unit to the right and one unit up, and we have either an up or a right move connecting every pair of consecutive L-trominoes along Marin’s path. Because Marin moves to the right a total of 6 times and up a total of 5, and because one of each move type occurs within each of the 4 L-trominoes, we therefore have a total of 6 − 4 = 2 right moves and 5 − 4 = 1 up move between pairs of consecutive L-trominoes. Since each of our 4 L-trominoes can be positioned in one of 2 ways, and there are 3 ways to arrange 4 the up and right moves between consecutive L-trominoes, we thus have a total of 2 · 3 = 48 possible paths.