HMMT 二月 2022 · COMB 赛 · 第 7 题

HMMT February 2022 — COMB Round — Problem 7

Let S = { ( x, y ) ∈ Z | 0 ≤ x ≤ 11 , 0 ≤ y ≤ 9 } . Compute the number of sequences ( s , s , . . . , s ) of 0 1 n elements in S (for any positive integer n ≥ 2) that satisfy the following conditions: • s = (0 , 0) and s = (1 , 0), 0 1 • s , s , . . . , s are distinct, 0 1 n ◦ ◦ • for all integers 2 ≤ i ≤ n , s is obtained by rotating s about s by either 90 or 180 in the i i − 2 i − 1 clockwise direction.

解析

Let S = { ( x, y ) ∈ Z | 0 ≤ x ≤ 11 , 0 ≤ y ≤ 9 } . Compute the number of sequences ( s , s , . . . , s ) of 0 1 n elements in S (for any positive integer n ≥ 2) that satisfy the following conditions: • s = (0 , 0) and s = (1 , 0), 0 1 • s , s , . . . , s are distinct, 0 1 n ◦ ◦ • for all integers 2 ≤ i ≤ n , s is obtained by rotating s about s by either 90 or 180 in the i i − 2 i − 1 clockwise direction. Proposed by: Gabriel Wu Answer: 646634 ◦ Solution: Let a be the number of such possibilities where there n 90 turns. Note that a = 10 and n 0 a = 11 · 9. 1 Now suppose n = 2 k with k ≥ 1. The path traced out by the s is uniquely determined by a choice i of k + 1 nonnegative x -coordinates and k positive y -coordinates indicating where to turn and when to stop. If n = 2 k + 1, the path is uniquely determined by a choice of k + 1 nonnegative x -coordinates and k + 1 positive y -coordinates. As a result, our final answer is 12 9 12 9 12 9 12 9 12 9 10 + 11 · 9 + + + · · · = − 12 + + + + · · · . 2 1 2 2 0 0 1 0 1 1 One can check that 9 9 X X 12 9 12 9 21 = = k k k 9 − k 9 k =0 k =0 by Vandermonde’s identity. Similarly, 9 9 X X 12 9 12 9 21 = = . k + 1 k k + 1 9 − k 10 k =0 k =0 Thus our final answer is 22 22 · 21 · 2 · 19 · 2 · 17 · 2 · 15 · 2 · 13 − 12 = − 12 + 10 6! 5 2 2 · 3 · 5 · 19 · 17 = − 12 + 7 · 11 · 13 · 4 2 2 · 3 · 5 = − 12 + 1001 · 2 · 17 · 19 = 646646 − 12 = 646634 .