HMMT 二月 2026 · COMB 赛 · 第 10 题
HMMT February 2026 — COMB Round — Problem 10
题目详情
- Let S be the set of all ordered pairs ( x, y ) of nonnegative integers 0 ≤ x ≤ 19 and 0 ≤ y ≤ 2 . Compute the number of permutations ( x , y ) , ( x , y ) , . . . , ( x , y ) of the elements of S such that 1 1 2 2 60 60 ©2026 HMMT • y = 2 and y = 0 ; 1 60 • for all nonnegative integers 1 ≤ i ≤ 59 , exactly one of the following holds: ◦ x = x and | y − y | = 1 , i i +1 i i +1 ◦ y = y and x − x is − 1 or 19 . i i +1 i i +1 ©2026 HMMT
解析
- Let S be the set of all ordered pairs ( x, y ) of nonnegative integers 0 ≤ x ≤ 19 and 0 ≤ y ≤ 2 . Compute the number of permutations ( x , y ) , ( x , y ) , . . . , ( x , y ) of the elements of S such that 1 1 2 2 60 60 • y = 2 and y = 0 ; 1 60 • for all nonnegative integers 1 ≤ i ≤ 59 , exactly one of the following holds: – x = x and | y − y | = 1 , i i +1 i i +1 – y = y and x − x is − 1 or 19 . i i +1 i i +1 Proposed by: Jackson Dryg Answer: 20460 Solution: Without loss of generality, Mark starts at (0 , 2) ; we’ll multiply by 20 at the end. Here is an example path: A B A B A B A C 0 0 1 1 2 2 3 2 D C C E 0 1 0 1 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 Note that the two red segments adjacent to point C must be part of any path. Let A , B , A , B . . . , A , B = 0 0 1 1 n n C denote the corners of the path that lie on the line y = 2 . The B are points where the path goes i down from the line y = 2 , and the A are points where it comes back up. Terminology: i • Let the entire path between A and C be a ridge (abbreviated as ridge A C ), and let the length 0 0 of the ridge be the length A C . 0 • Let the head of the ridge be segment A B . (The head may have length 0 , if the path goes down 0 0 immediately from point A .) 0 • Let a valley be the segment of the path between B and A . Let the depth of a valley be the i i +1 number of units below line B A the valley reaches (so depth is either 1 or 2). Let the length of i i +1 a valley be the length B A . i i +1 • Let a hill be segment A B for i > 0 . i i Because of the position of ridge A C , the two red segments adjacent to station E must also be part of 0 the path. Consider the section of the path between C and E ; it lies on or below the line y = 1 . Let 0 C , D , C , D , . . . , C , D = E denote the corners of the path that lie on the line y = 1 . We can also 0 0 1 1 n n consider this section of the path from C to E a ridge, with the same terminology. 0 The following claims apply to both ridges A C and C E . 0 0 Claim 1. All valleys have width 1 . Proof. Suppose not; then any vertex on the line y = 2 between B and A (or D and C ) is i i +1 i i +1 isolated from the path, contradiction. Claim 2. Hills that are part of ridge A C have odd length; hills that are part of ridge C E have 0 0 length 1 . Proof. For the first part, see the diagram below. Consider any hill of A C (in black). The red segments 0 are forced to be part of the path. By considering vertices labeled 1 , 2 , 3 , . . . , in order, the path between the red segments is uniquely determined, and is only possible when the hill has odd length. For the second part, see the diagram on the right. If the hill has length greater than 1 , then there is an isolated vertex. ©2026 HMMT 1 2 3 Claim 3. The head of a ridge has odd length. Proof. Note that ridge A C has length 19 . Because all valleys and hills have odd length, all segments 0 B B for i ≥ 0 have even length. Since A C = 19 = A B + B B + B B + · · · + B C , A B i i +1 0 0 0 0 1 1 2 n − 1 0 0 must have odd length. Next, note that C E has the same length as A B , the head of A C , so it has odd length. By a similar 0 0 0 0 argument, all D D have even length, so C D has odd length. i i +1 0 0 This claim means that the green segment attached to C must be part of any path, since the head 0 C D of ridge C E has length at least 1 . 0 0 0 Claim 4. All valleys have depth 1 . Proof. Suppose a valley had depth 2 . Consider the two circled vertices: These two circled vertices force the next hill to have width 1, and the next valley to have depth 2. This forces the next hill to have width 1 and the next valley to have depth 2, and so on. This continues until C . (All hills and valleys have odd length; this ensures the sequence of valleys hits C in this 0 0 way.) But then the path doesn’t contain the green segment: This is a contradiction. Claim 5. Once ridges A C and C E are chosen, the rest of the path is uniquely determined. 0 0 Proof. This is clear from the picture at the beginning; the rest of the path is shown in blue. Now we can start counting. First consider the possibilities for ridge A C . Each choice of the lengths 0 ( A B , B B , . . . , B C ) corresponds to exactly one possible ridge. Since all valleys have width 1 and 0 0 0 1 n − 1 all hills have odd length, each length B B must be even. i i +1 Suppose the head A B has length 19 − 2 k . Then the number of ways to fill in the remaining lengths 0 0 k − 1 is the number of partitions of 2 k into even numbers, which is 1 if k = 0 and 2 if k ≥ 1 . Next, given a ridge A C , we must choose a ridge C E . Note that C E has the same length as 0 0 0 A B , so 19 − 2 k . Each choice of the lengths ( C D , D D , . . . , D E ) corresponds to exactly one 0 0 0 0 0 1 n − 1 possible ridge. Since all hills and valleys have length 1 , each D D is 2 . The possibilities are i i +1 (19 − 2 k ) , (17 − 2 k, 2) , (15 − 2 k, 2 , 2) , . . . , (1 , 2 , 2 , . . . , 2) ; there are 10 − k possibilities. ©2026 HMMT So the number of ways to choose both A C and C E , where the head of A C has length 19 − 2 k , is 10 0 0 0 k − 1 if k = 0 and (10 − k )2 if k ≥ 1 . Summing over all possible head lengths, 9 8 ∑ ∑ k − 1 k 10 + (10 − k )2 = 10 + (9 − k )2 k =1 k =0 8 8 − k ∑ ∑ k = 10 + 2 k =0 ℓ =0 8 8 − ℓ ∑ ∑ k = 10 + 2 ℓ =0 k =0 8 ∑ 9 − ℓ = 10 + 2 − 1 ℓ =0 9 ∑ ℓ = 10 − 9 + 2 ℓ =1 10 10 = 1 + 2 − 2 = 2 − 1 = 1023 . The final answer is 20 · 1023 = 20460 . ©2026 HMMT