HMMT 十一月 2023 · 团队赛 · 第 10 题
HMMT November 2023 — Team Round — Problem 10
题目详情
- [65] Compute the number of ways a non-self-intersecting concave quadrilateral can be drawn in the plane such that two of its vertices are (0 , 0) and (1 , 0) , and the other two vertices are two distinct lattice points ( a, b ) , ( c, d ) with 0 ≤ a, c ≤ 59 and 1 ≤ b, d ≤ 5 . ◦ (A concave quadrilateral is a quadrilateral with an angle strictly larger than 180 . A lattice point is a point with both coordinates integers.)
解析
- [65] Compute the number of ways a non-self-intersecting concave quadrilateral can be drawn in the plane such that two of its vertices are (0 , 0) and (1 , 0), and the other two vertices are two distinct lattice points ( a, b ) , ( c, d ) with 0 ≤ a, c ≤ 59 and 1 ≤ b, d ≤ 5. ◦ (A concave quadrilateral is a quadrilateral with an angle strictly larger than 180 . A lattice point is a point with both coordinates integers.) Proposed by: Julia Kozak Answer: 366 Solution: We instead choose points (0 , 0) , (1 , 0) , ( a, b ) , ( c, d ) with 0 ≤ a, c ≤ 59 and 0 ≤ b, d ≤ 5 with ( c, d ) in the interior of the triangle formed by the other three points. Any selection of these four points may be connected to form a concave quadrilateral in precisely three ways. Apply Pick’s theorem to this triangle. If I is the count of interior points, and B is the number of boundary lattice points, we have that the triangle’s area is equal to b B = I + − 1 . 2 2 Let’s first compute the number of boundary lattice points on the segment from (0 , 0) to ( a, b ), not counting (0 , 0). This is just gcd( a, b ). Similarly, there are gcd( a − 1 , b ) boundary lattice points from (1 , 0) to ( a, b ). Adjusting for the overcounting at ( a, b ), we have B = gcd( a, b ) + gcd( a − 1 , b ) − 1 and thus b − gcd( a, b ) − gcd( a − 1 , b ) + 1 I = 2 which we notice is periodic in a with period b . That is, the count of boundary points does not change between choices ( a, b ) and ( a + b, b ). We wanted to find the sum across all ( a, b ) of I , the number of interior points ( c, d ). Using casework on b , the periodicity allows us to just check I across points with 0 ≤ a < b , and then multiply the 60 count by to get the sum of I across the entire row of points. b For b = 1 , 2, we always have I = 0. For b = 3, we have I = 0 at (0 , 3) , (1 , 3) and I = 1 for (2 , 3). Using periodicity, this y -coordinate has a total a total of 60 (0 + 0 + 1) · = 20 . 3 For b = 4, we have I = 0 at (0 , 4) and (1 , 4), and I = 1 at both (2 , 4) and (3 , 4). Using periodicity, this y -coordinate has a total of 60 (0 + 0 + 1 + 1) · = 30 . 4 For b = 5, we have I = 0 at (0 , 5) , (1 , 5) and I = 2 at (2 , 5) , (3 , 5) , (4 , 5). Using periodicity, this y -coordinate has a total of 60 (0 + 0 + 2 + 2 + 2) · = 72 . 5 Adding our cases, we have 20 + 30 + 72 = 122 ways to choose the four points. Multiplying back by the number of ways to connect the quadrilateral gives an answer of 122 · 3 = 366 .